Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming

Lucio Bianco, Aristide Mingozzi, Salvatore Ricciardelli, Massimo Spadoni

INFOR Information Systems and Operational Research · 1994 · 52 citations · 0 references

Concepts

Abstract

The Traveling Salesman Problem with Precedence Constraints is to find an hamiltonian tour of minimum cost in a graph G = (X,A) of n vertices, starting from vertex 1, visiting every vertex that must precede i before i (i = 2,3,..., n) and returning to vertex 1. This problem is NP-hard and arises in practical transportation and sequencing problems. In this paper we describe a new bounding procedure and a new optimal algorithm, based on dynamic programming. Computational results are given for randomly generated test problems, including the dial-a-ride problem with the classical TSP objective function.