Abstract

Given a graph whose arc traversal times vary over time, the Time-Dependent Travelling Salesman Problem (TDTSP) consists in finding a Hamiltonian tour of least total duration covering the vertices of the graph. The contribution of this paper is twofold. First, we describe a lower and upper bounding procedure that requires the solution of a simpler (yet NP-hard) Asymmetric Travelling Salesman Problem (ATSP). In addition, we prove that this ATSP solution is optimal for the TDTSP if all the arcs share a common congestion pattern. Second, we formulate the TDTSP as an integer linear programming model for which valid inequalities are devised. These inequalities are then embedded into a branch-and-cut algorithm that is able to solve instances with up to 40 vertices.

Autore Pugliese

• Guerriero Emanuela , Ghiani Gianpaolo

Tutti gli autori

• E.Guerriero , G. Ghiani , J.F. Cordeau

Titolo volume/Rivista

TRANSPORTATION SCIENCE

Anno di pubblicazione

2014

ISSN

0041-1655

ISBN

Non Disponibile

Numero di citazioni Wos

10

Ultimo Aggiornamento Citazioni

28/04/2018

Numero di citazioni Scopus

15

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile