Optimization Online


Time Dependent Traveling Salesman Problem with Time Windows: Properties and an Exact Algorithm

Anna Arigliano(anna.arigliano***at***unisalento.it)
Gianpaolo Ghiani(gianpaolo.ghiani***at***unisalento.it)
Antonio Grieco(antonio.grieco***at***unisalento.it)
Emanuela Guerriero(emanuela.guerriero***at***unisalento.it)

Abstract: In this paper, we deal with the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW). Firstly, we prove that under special conditions the TDTSPTW can be solved as an Asymmetric Traveling Salesman Problem with Time Windows (ATSPTW), with suitable-defined time windows and (constant) travel times. Secondly, we show that, if the special conditions do not hold, the ATSPTW optimal solution provides both a lower bound and (eventually) an upper bound with a worst-case guarantee for the original TDTSPTW. Finally an integer linear programming model is presented and valid inequalities are embedded into a branch-and-cut algorithm. Computational results show that the proposed algorithm is able to solve instances with up to 40 vertices.

Keywords: traveling salesman problem \sep time dependence \sep time windows; lower and upper bounds; branch-and-cut

Category 1: Applications -- OR and Management Sciences (Transportation )

Citation: Technical Report 001 Dipartimento di Ingegneria dell'Innovazione August/2011

Download: [PDF]

Entry Submitted: 03/13/2015
Entry Accepted: 03/13/2015
Entry Last Modified: 03/13/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society