Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints
成果类型：
Article
署名作者：
Mingozzi, A; Bianco, L; Ricciardelli, S
署名单位：
University of Rome Tor Vergata
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.3.365
发表日期：
1997
页码：
365-377
关键词：
摘要：
The Traveling Salesman Problem with Time Window and Precedence Constraints (TSP-TWPC) is to find an Hamiltonian tour of minimum cost in a graph G = (X,A) of n vertices, starting at vertex 1, visiting each vertex i is an element of X during its time window and after having visited every vertex that must precede i, and returning to vertex 1. The TSP-TWPC is known to be NP-hard and has applications in many sequencing and distribution problems. In this paper we describe an exact algorithm to solve the problem that is based on dynamic programming and makes use of bounding functions to reduce the state space graph. These functions are obtained by means of a new technique that is a generalization of the ''State Space Relaxation'' for dynamic programming introduced by Christofides et al. (1981b). Computational results are given for randomly generated test problems.