Exact solutions for the carrier-vehicle traveling salesman problem
| Autor: | Claudio Gambella, Andrea Lodi, Daniele Vigo |
|---|---|
| Přispěvatelé: | Gambella C., Lodi A., Vigo D., Logistics, Amsterdam Business Research Institute |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Traveling purchaser problem
0209 industrial biotechnology Mathematical optimization Sequence 021103 operations research 0211 other engineering and technologies Transportation 02 engineering and technology 2-opt Travelling salesman problem Traveling salesman problem 020901 industrial engineering & automation Second-order conic programming Mixed-integer Range (aeronautics) A priori and a posteriori Motion planning Mission planning Bottleneck traveling salesman problem Path planning Civil and Structural Engineering Mathematics |
| Zdroj: | Gambella, C, Lodi, A & Vigo, D 2018, ' Exact solutions for the carrier-vehicle traveling salesman problem ', Transportation Science, vol. 52, no. 2, pp. 320-330 . https://doi.org/10.1287/trsc.2017.0771 Transportation Science, 52(2), 320-330. INFORMS Inst.for Operations Res.and the Management Sciences |
| ISSN: | 0041-1655 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|