A Benders Decomposition Approach for the Symmetric TSP with Generalized Latency Arising in the Design of Semiflexible Transit Systems

We present the symmetric traveling salesman problem with generalized latency (TSP-GL) a new problem arising in the planning of the important class of semiflexible transit systems. The TSP-GL can be seen as a very challenging variant of the symmetric traveling salesman problem (S-TSP), where the objective function combines the usual cost of the circuit with a routing component accounting for the passenger travel times. The main contributions of the paper include the formulation of the problems in terms of mul- ticommodity flows, the study of its mathematical properties, and the introduction of a branch-and-cut approach based on Benders reformulation taking advantage of properties that relate the feasible region of the TSP-GL and the S-TSP polyhedron. An extensive com- putational experimentation compares a number of variants of the proposed algorithm, as well as a commercial solver. These experiments show that the method we propose signif- icantly outperforms a well-known commercial solver and obtains good-quality solutions to realistically sized instances within short computational times.