Optimization Online


Solving Time Dependent Traveling Salesman Problems with Time Windows

Duc Minh Vu (dvu3***at***luc.edu)
Mike Hewitt (mhewitt3***at***luc.edu)
Natashia Boland (natashia.boland***at***gmail.com)
Martin Savelsbergh (martin.savelsbergh***at***isye.gatech.edu)

Abstract: We present a new solution approach for the Time Dependent Traveling Salesman Prob- lem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a pre-determined period of time, and then returns home. The problem allows for travel times that can depend on the time of departure. The solution approach is based on an integer programming formulation of the problem on a time expanded network, as doing so enables time dependencies to be embedded in the definition of the network. However, as such a time expanded network (and thus the integer programming formulation) can rapidly become prohibitively large, the solution approach employs a dynamic discretization discovery framework, which has been effective in other contexts. Our computational results indicate that the so- lution approach outperforms the best-known methods on benchmark instances and is robust with respect to instance parameters.

Keywords: Traveling Salesman Problem, time windows, time dependent travel times, dynamic discretization discovery

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


Download: [PDF]

Entry Submitted: 05/30/2018
Entry Accepted: 05/30/2018
Entry Last Modified: 06/02/2018

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