Publications of A. Mingozzi

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Mingozzi A., in the category IASI Research Reports (or show them all):


IASI Research Report n. 353  (Previous    Next)


Bianco L., Mingozzi A., Ricciardelli S.

Dynamic programming strategies and reduction techniques for the traveling salesman problem with time window and precedence constraints

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 iEX 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, Mingozzi and Toth (1981). Computational results are given for randomly generated test problems.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -