IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v52y2018i2p320-330.html
   My bibliography  Save this article

Exact Solutions for the Carrier–Vehicle Traveling Salesman Problem

Author

Listed:
  • 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)

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.

Suggested Citation

  • Claudio Gambella & Andrea Lodi & Daniele Vigo, 2018. "Exact Solutions for the Carrier–Vehicle Traveling Salesman Problem," Transportation Science, INFORMS, vol. 52(2), pages 320-330, March.
    • Handle: RePEc:inm:ortrsc:v:52:y:2018:i:2:p:320-330
    DOI: 10.1287/trsc.2017.0771
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2017.0771
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2017.0771?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Brian J. Griggs & Gregory S. Parnell & Lee J. Lehmkuhl, 1997. "An Air Mission Planning Algorithm Using Decision Analysis and Mixed Integer Programming," Operations Research, INFORMS, vol. 45(5), pages 662-676, October.
    2. Ruth Misener & Christodoulos Floudas, 2014. "ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations," Journal of Global Optimization, Springer, vol. 59(2), pages 503-526, July.
    3. Michael Held & Richard M. Karp, 1970. "The Traveling-Salesman Problem and Minimum Spanning Trees," Operations Research, INFORMS, vol. 18(6), pages 1138-1162, December.
    4. Eugene L. Lawler, 1972. "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem," Management Science, INFORMS, vol. 18(7), pages 401-405, March.
    5. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Güneş Erdoğan & E. Alper Y?ld?r?m, 2021. "Exact and Heuristic Algorithms for the Carrier–Vehicle Traveling Salesman Problem," Transportation Science, INFORMS, vol. 55(1), pages 101-121, 1-2.
    2. Li, Hongqi & Chen, Jun & Wang, Feilong & Bai, Ming, 2021. "Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1078-1095.
    3. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2020. "Two-echelon vehicle routing problem with time windows and mobile satellites," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 179-201.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    2. Schuijbroek, J. & Hampshire, R.C. & van Hoeve, W.-J., 2017. "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, Elsevier, vol. 257(3), pages 992-1004.
    3. Martinhon, Carlos & Lucena, Abilio & Maculan, Nelson, 2004. "Stronger K-tree relaxations for the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(1), pages 56-71, October.
    4. de Klerk, E. & Pasechnik, D.V. & Sotirov, R., 2007. "On Semidefinite Programming Relaxations of the Travelling Salesman Problem (Replaced by DP 2008-96)," Discussion Paper 2007-101, Tilburg University, Center for Economic Research.
    5. Elena Nechita & Gloria Cerasela Crişan & Laszlo Barna Iantovics & Yitong Huang, 2020. "On the Resilience of Ant Algorithms. Experiment with Adapted MMAS on TSP," Mathematics, MDPI, vol. 8(5), pages 1-20, May.
    6. Ghosh, Diptesh & Sumanta Basu, 2011. "Diversified Local Search for the Traveling Salesman Problem," IIMA Working Papers WP2011-01-03, Indian Institute of Management Ahmedabad, Research and Publication Department.
    7. Vivek Bagaria & Jian Ding & David Tse & Yihong Wu & Jiaming Xu, 2020. "Hidden Hamiltonian Cycle Recovery via Linear Programming," Operations Research, INFORMS, vol. 68(1), pages 53-70, January.
    8. de Klerk, E. & Pasechnik, D.V. & Sotirov, R., 2008. "On Semidefinite Programming Relaxations of the Traveling Salesman Problem (revision of DP 2007-101)," Other publications TiSEM ea23cd70-a3b1-401a-aa3f-0, Tilburg University, School of Economics and Management.
    9. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    10. Sascha Wörz, 2017. "On global integer extrema of real-valued box-constrained multivariate quadratic functions," Journal of Combinatorial Optimization, Springer, vol. 34(3), pages 964-986, October.
    11. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    12. Stuart M. Harwood & Paul I. Barton, 2017. "How to solve a design centering problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(1), pages 215-254, August.
    13. Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.
    14. Jaromił Najman & Alexander Mitsos, 2019. "On tightness and anchoring of McCormick and other relaxations," Journal of Global Optimization, Springer, vol. 74(4), pages 677-703, August.
    15. Letchford, Adam N. & Nasiri, Saeideh D. & Theis, Dirk Oliver, 2013. "Compact formulations of the Steiner Traveling Salesman Problem and related problems," European Journal of Operational Research, Elsevier, vol. 228(1), pages 83-92.
    16. Lingxun Kong & Christos T. Maravelias, 2020. "On the Derivation of Continuous Piecewise Linear Approximating Functions," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 531-546, July.
    17. Friberg, Christian & Haase, Knut, 1996. "An exact algorithm for the vehicle and crew scheduling problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 416, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. Roel G. van Anholt & Leandro C. Coelho & Gilbert Laporte & Iris F. A. Vis, 2016. "An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines," Transportation Science, INFORMS, vol. 50(3), pages 1077-1091, August.
    19. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    20. Gábor Braun & Samuel Fiorini & Sebastian Pokutta & David Steurer, 2015. "Approximation Limits of Linear Programs (Beyond Hierarchies)," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 756-772, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:52:y:2018:i:2:p:320-330. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.