Solving Time Dependent Traveling Salesman Problems with Time Windows

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.

Article

Download

View Solving Time Dependent Traveling Salesman Problems with Time Windows