Software for solving the precedence constrained generalized traveling salesman problem

The paper considers the generalized problem of the precedence constraint traveling salesman (PCGTSP). Like the classical traveling salesman problem (TSP), the authors search a minimum cost closed cycle in this problem, while the set of vertices is divided into nonempty pairwise disjoint sub-sets that are clusters; each feasible route must visit each cluster in a single vertex. In addition, the set of valid routes is constrained by an additional restriction on the order of visiting clusters, that is, some clusters must be visited earlier than others. In contrast to the TSP and the generalized traveling sales-man problem (GTSP), this problem is poorly studied both theoretically and from the point of view of algorithm design and implementation. The paper proposes the first specialized branch-and-bound algorithms using the solutions obtained using the recently developed PCGLNS heuristic as an initial guess. The original PCGTSP problem un-dergoes several relaxations, therefore there are several lower bounds for the original problem; the larg-est of them is used to cut off the branches of the search tree and thereby reduce the enumeration. The algorithms are implemented as open source software in the Python 3 programming language using the specialized NetworkX library. The performance of the proposed algorithms is evaluated on test exam-ples from the PCGTSPLIB public library in comparison with the state-of-the-art Gurobi solver using the MILP model recently proposed by the authors, and seems to be quite competitive even in the cur-rent implementation. The developed algorithms can be used in a wide class of practical problems, for example, for opti-mal tool routing for CNC sheet cutting machines, as well as for assessing the quality of solutions ob-tained using other methods.