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

Fausto Errico (), Teodor Gabriel Crainic (), Federico Malucelli () and Maddalena Nonato ()
Additional contact information
Fausto Errico: Department de génie de la construction, École de technologie supérieure, Montréal, Québec H3C 1K3, Canada; and Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Université de Montréal, Montréal, Québec H3C 3J7, Canada
Teodor Gabriel Crainic: Department management et technologie, École des sciences de la gestion, Université du Québec á Montréal, Montréal, Québec H3C 3P8, Canada; and Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Université de Montréal, Montréal, Québec H3C 3J7, Canada
Federico Malucelli: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milano, Italy
Maddalena Nonato: School of Engineering, Università degli Studi di Ferrara, 44122 Ferrara, Italy

Transportation Science, 2017, vol. 51, issue 2, 706-722

Abstract: 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 multicommodity 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 computational experimentation compares a number of variants of the proposed algorithm, as well as a commercial solver. These experiments show that the method we propose significantly outperforms a well-known commercial solver and obtains good-quality solutions to realistically sized instances within short computational times.

Keywords: symmetric TSP with generalized latency; semiflexible transit; traveling salesperson problem; latency; Benders decomposition; branch and cut (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2015.0636 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:51:y:2017:i:2:p:706-722

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().