Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows
- 1 May 2020
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 54 (3) , 703-720
Abstract
We present a new solution approach for the time-dependent traveling salesman problem with time windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a predetermined period of time, and then, returns home. The problem allows for travel times that can depend on the time of departure. We consider two objectives for the problem: (1) a makespan objective that seeks to return the salesman to his home as early as possible and (2) a duration objective that seeks to minimize the amount of time that he is away from his home. The solution approach is based on an integer programming formulation of the problem on a time-expanded network, because doing so enables time dependencies to be embedded in the definition of the network. However, because such a time-expanded network (and thus, the integer programming formulation) can rapidly become prohibitively large, the solution approach uses a dynamic discretization discovery framework, which has been effective in other contexts. Our computational results indicate that the solution approach outperforms the best-known methods on benchmark instances and is robust with respect to instance parameters.Keywords
This publication has 29 references indexed in Scilit:
- The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristicsTransportation Research Part E: Logistics and Transportation Review, 2012
- An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformationEuropean Journal of Operational Research, 2008
- A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup timesComputers & Operations Research, 2008
- Vehicle dispatching with time-dependent travel timesEuropean Journal of Operational Research, 2003
- A classification of formulations for the (time-dependent) traveling salesman problemEuropean Journal of Operational Research, 1995
- Chapter 2 Time constrained routing and scheduling1995
- A two‐commodity flow formulation for the traveling salesman and the makespan problems with time windowsNetworks, 1993
- Time‐dependent traveling salesman problem–the deliveryman caseNetworks, 1990
- Local search in routing problems with time windowsAnnals of Operations Research, 1985
- State‐space relaxation procedures for the computation of bounds to routing problemsNetworks, 1981