Branch-and-Bound for the Precedence Constrained Generalized Traveling Salesman Problem

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Extended Abstracts

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12-26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 hours.

10.1609/socs.v11i1.18520