Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints

Aristide Mingozzi, Lucio Bianco and Salvatore Ricciardelli
Additional contact information
Aristide Mingozzi: University of Bologna, Bologna, Italy
Lucio Bianco: University “Tor Vergata”, Rome, Italy
Salvatore Ricciardelli: University “Tor Vergata”, Rome, Italy

Operations Research, 1997, vol. 45, issue 3, 365-377

Abstract: 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 ∈ 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. (Christofides, N., A. Mingozzi, P. Toth. 1981b. State space relaxation for the computation of bounds to routing problems. Networks 11 145–164.). Computational results are given for randomly generated test problems.

Keywords: networks/graphs; traveling salesman with additional constraints; dynamic programming/optimal control; state space relaxation strategies (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.3.365 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:3:p:365-377

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().