A branch-and-cut algorithm for the generalized traveling salesman problem with time windows (GTSPTW)

This work presents a branch-and-cut algorithm for the generalized traveling salesman problem with time windows (GTSPTW). GTSPTW can be 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. Two integer linear programming formulations for GTSPTW and several problem-specific valid inequalities are presented. These inequalities are separated dynamically within a branch-and-cut algorithm. To speed-up the computation 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 with up to 32 clusters and 101 vertices can be solved to optimality within one hour.