The Robust Traveling Salesman Problem with Interval Data

R. Montemanni (), J. Barta (), M. Mastrolilli () and L. M. Gambardella ()
Additional contact information
R. Montemanni: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
J. Barta: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
M. Mastrolilli: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland
L. M. Gambardella: Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Lugano-Manno, Switzerland

Transportation Science, 2007, vol. 41, issue 3, 366-381

Abstract: 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.

Keywords: traveling salesman problem; robust optimization; interval data; exact algorithms; heuristic algorithms (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1060.0181 (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:ortrsc:v:41:y:2007:i:3:p:366-381

Access Statistics for this article

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