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

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

0.00 Avg rating0 Votes
Article ID: iaor1999425
Country: Netherlands
Volume: 90
Issue: 1
Start Page Number: 45
End Page Number: 55
Publication Date: Apr 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: dynamic
Abstract:

Dynamic programming (DP) algorithms for the traveling saleman 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.

Reviews

Required fields are marked *. Your email address will not be published.