Heuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem

The Time-Dependent Traveling Salesman Problem (TDTSP) is a generalization of the Traveling Salesman Problem (TSP) in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. There exists a number of applications of the TDTSP in the fields of distribution and scheduling. We present a new mixed-integer linear programming (MILP) formulation for the TDTSP. A directed multi-partite graph representation of this model facilitates the development of a local search heuristic which extends the well known Lin-Kernighan tour improvement heuristic to the TDTSP. A second upper bound is derived by applying a Benders-decomposition-based heuristic to the MILP formulation. The Benders master problem is further approximately solved to provide a lower bound. We also develop a method for generating TDTSP instances with known optimal solutions. Finally, computational experience with the heuristics and problem generator is presented for problems with up to 100 cities. The results demonstrate that the heuristics can achieve optimal or very good near-optimal solutions on a variety of problem classes with minimal computational effort.