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.

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

NONATO, Maddalena
Ultimo
2017

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.
2017
Errico, Fausto; Crainic, Teodor Gabriel; Malucelli, Federico; Nonato, Maddalena
File in questo prodotto:
File Dimensione Formato  
ErricoCrainicMalucelliNonato_revision1_april2015.pdf

accesso aperto

Descrizione: Pre-print
Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 322.63 kB
Formato Adobe PDF
322.63 kB Adobe PDF Visualizza/Apri
7275ffeab2277266cc1ffbc31335efd47144.pdf

accesso aperto

Tipologia: Post-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 335.19 kB
Formato Adobe PDF
335.19 kB Adobe PDF Visualizza/Apri
11392_2365854_FULL_Nonato.pdf

solo gestori archivio

Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 335.23 kB
Formato Adobe PDF
335.23 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2365854
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact