This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Montemanni, R. Articles by Gambardella, L. M. Search for Related Content

The Robust Traveling Salesman Problem with Interval Data

Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
roberto{at}idsia.ch
janos.barta{at}supsi.ch
monaldo{at}idsia.ch
luca{at}idsia.ch

The traveling salesman problem is one of the most famous combinatorial optimization problems and has been intensively studied. Many extensions to the basic problem have also been proposed, with the aim of making the resulting mathematical models as realistic as possible. We present a new extension to the basic problem, where travel times are specified as a range of possible values. This model reflects the intrinsic difficulties of estimating travel times in reality. We apply the robust deviation criterion to drive optimization over the interval data problem so obtained. Some interesting theoretical properties of the new optimization problems are identified and discussed, together with a new mathematical formulation and some exact and heuristic algorithms. Computational experiments are finally presented.

Key Words: traveling salesman problem; robust optimization; interval data; exact algorithms; heuristic algorithms
History: Received: February 2006; revised: July 2006; accepted: October 2006.