A branch-and-cut algorithm for the generalized traveling salesman problem with time...

Studied the generalized traveling salesman problem with time windows (GTSPTW).•Proposed two MILP formulations and several valid inequalities for the GTSPTW. Proposed the first exact algorithm (branch-and-cut) for the GTSPTW.•Developed a simple and fast heuristic for the GTSPTW. Solved instances with up to 30 clusters to optimality within one hour. The generalized traveling salesman problem with time windows (GTSPTW) is defined on a directed graph where the vertex set is partitioned into clusters. One cluster contains only the depot. Each vertex is associated with a time interval, the time window, during which the visit must take place if the vertex is visited. The objective is to find a minimum cost tour starting and ending at the depot such that each cluster is visited exactly once and time constraints are respected, i.e., for each cluster, one vertex is visited during its time window. In this paper, two integer linear programming formulations for GTSPTW are provided as well as several problem-specific valid inequalities. A branch-and-cut algorithm is developed in which the inequalities are separated dynamically. To reduce the computation times, an initial upper bound is provided by a simple and fast heuristic. We propose different sets of instances characterized by their time window structures. Experimental results show that our algorithm is effective and instances including up to 30 clusters can be solved to optimality within one hour.

Английский

European Journal of Operational Research. – 2020. – Vol. 286, № 3. – P. 849–866.