Exact solutions for the carrier-vehicle traveling salesman problem

Claudio Gambella, Andrea Lodi, Daniele Vigo

Research output: Contribution to JournalArticleAcademicpeer-review

81 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)320-330
Number of pages11
JournalTransportation Science
Issue number2
Early online date11 Sept 2017
Publication statusPublished - Apr 2018


  • Mission planning
  • Mixed-integer
  • Path planning
  • Second-order conic programming
  • Traveling salesman problem


Dive into the research topics of 'Exact solutions for the carrier-vehicle traveling salesman problem'. Together they form a unique fingerprint.

Cite this