Exact Solutions for the Carrier–Vehicle Traveling Salesman Problem

Claudio Gambella (), Andrea Lodi () and Daniele Vigo ()
Additional contact information
Claudio Gambella: Department of Electrical, Electronic and Information Engineering, University of Bologna, 40126 Bologna, Italy; IBM Research Ireland, Dublin 15, Ireland
Andrea Lodi: Department of Mathematical and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T 1J4, Canada
Daniele Vigo: Department of Electrical, Electronic and Information Engineering, University of Bologna, 40126 Bologna, Italy

Transportation Science, 2018, vol. 52, issue 2, 320-330

Abstract: Carrier–vehicle systems generally consist of a slow carrier (e.g., a ship) with a long operational range and a faster vehicle (e.g., an aircraft) with a limited operational range. The carrier has the role of transporting the faster vehicle and of deploying, recovering, and servicing it. The goal of the carrier–vehicle traveling salesman problem (CVTSP) is to permit the faster vehicle to visit a given collection of targets in the shortest time while using the carrier as a base for possible multiple trips. As a consequence, the carrier and vehicle should be synchronized. The visiting sequence of the targets is not given a priori. We present a mixed-integer, second-order conic programming (MISOCP) formulation for the CVTSP. Computational results are shown for the resolution of the model with commercial solvers. The MISOCP structure and the relationship to the traveling salesman problem are exploited for developing a ranking-based solution algorithm that outperforms the commercial solvers.

Keywords: mixed-integer; second-order conic programming; path planning; mission planning; traveling salesman problem (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0771 (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:52:y:2018:i:2:p:320-330

Access Statistics for this article

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