A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem

Dynamic programming (DP) algorithms for the traveling salesman problem (TSP) can easily incorporate time dependent travel times, time windows, and precedence relationships which present difficulties for algorithms based on linear or nonlinear programming formulations and for many TSP heuristics. However, exact DP algorithms for the TSP have exponential storage and computational time requirements and can solve only very small problems. We present a restricted DP heuristic (a generalization of the nearest-neighbor heuristic) that can include all the above considerations but solves much larger problems. The heuristic cannot guarantee optimality because only a user-specified number of partial tours is retained at each stage. In this paper, the heuristic is implemented for the time dependent traveling salesman problem and is tested on a personal computer on randomly generated problems. The quality of the solutions improves, on average, as more computational time is permitted.