IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v168y2023icp81-123.html
   My bibliography  Save this article

Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones

Author

Listed:
  • Tiniç, Gizem Ozbaygin
  • Karasan, Oya E.
  • Kara, Bahar Y.
  • Campbell, James F.
  • Ozel, Aysu

Abstract

Deployment of drones in delivery operations has been attracting growing interest from the commercial sector due to its prospective advantages for a range of distribution systems. Motivated by the widespread adoption of drones in last-mile delivery, we introduce the minimum cost traveling salesman problem with multiple drones, where a truck and multiple drones work in synchronization to deliver parcels to customers. In this problem, we aim to find an optimal delivery plan for the truck and drones operating in tandem with the objective of minimizing the total operational cost including the vehicles’ operating and waiting costs. Unlike most studies in the literature where the objective is to minimize completion time, which means one needs to know only the arrival time of the latest arriving vehicle (truck or drone) at each synchronization point, we need to keep track of all the individual waiting times of the truck and the drones to properly account for waiting costs, which makes it more challenging to handle the synchronization. We provide a flow based and two cut based mixed integer linear programming formulations strengthened with valid inequalities. For non-compact models, we devise a variety of branch-and-cut schemes to solve our problem to optimality. To compare our formulations/algorithms and to demonstrate their competitiveness, we conduct computational experiments on a range of instances. The results indicate the superiority of utilizing branch-and-cut methodology over a flow based formulation. We also use our model to conduct sensitivity analyses with several problem parameters and to explore the benefits of launch and retrieval at the same node, the tradeoff between the number of drones and the operational cost, and the special case with a minimize completion objective with one drone. We also document very low waiting times for drones in optimal solutions and show solutions from minimizing cost have much lower cost than those from minimizing makespan.

Suggested Citation

  • Tiniç, Gizem Ozbaygin & Karasan, Oya E. & Kara, Bahar Y. & Campbell, James F. & Ozel, Aysu, 2023. "Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 81-123.
    • Handle: RePEc:eee:transb:v:168:y:2023:i:c:p:81-123
    DOI: 10.1016/j.trb.2022.12.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261522002090
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2022.12.007?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Quang Minh Ha & Yves Deville & Quang Dung Pham & Minh Hoàng Hà, 2020. "A hybrid genetic algorithm for the traveling salesman problem with drone," Journal of Heuristics, Springer, vol. 26(2), pages 219-247, April.
    2. Yang, Weibo & Ke, Liangjun & Wang, David Z.W. & Lam, Jasmine Siu Lee, 2021. "A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    3. Mauro Dell’Amico & Roberto Montemanni & Stefano Novellani, 2020. "Matheuristic algorithms for the parallel drone scheduling traveling salesman problem," Annals of Operations Research, Springer, vol. 289(2), pages 211-226, June.
    4. Stefan Poikonen & Bruce Golden & Edward A. Wasil, 2019. "A Branch-and-Bound Approach to the Traveling Salesman Problem with a Drone," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 335-346, April.
    5. Amro M. El-Adle & Ahmed Ghoniem & Mohamed Haouari, 2021. "Parcel delivery by vehicle and drone," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(2), pages 398-416, February.
    6. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    7. Salama, Mohamed R. & Srinivas, Sharan, 2022. "Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    8. Tamke, Felix & Buscher, Udo, 2021. "A branch-and-cut algorithm for the vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 174-203.
    9. Wang, Zheng & Sheu, Jiuh-Biing, 2019. "Vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 350-364.
    10. Roberto Roberti & Mario Ruthmair, 2021. "Exact Methods for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 55(2), pages 315-335, March.
    11. Dell’Amico, Mauro & Montemanni, Roberto & Novellani, Stefano, 2021. "Algorithms based on branch and bound for the flying sidekick traveling salesman problem," Omega, Elsevier, vol. 104(C).
    12. Jeong, Ho Young & Song, Byung Duk & Lee, Seokcheon, 2019. "Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones," International Journal of Production Economics, Elsevier, vol. 214(C), pages 220-233.
    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. Liu, Wenqian & Liu, Lindong & Qi, Xiangtong, 2024. "Drone resupply with multiple trucks and drones for on-time delivery along given truck routes," European Journal of Operational Research, Elsevier, vol. 318(2), pages 457-468.
    2. Teena Thomas & Sharan Srinivas & Chandrasekharan Rajendran, 2024. "Collaborative truck multi-drone delivery system considering drone scheduling and en route operations," Annals of Operations Research, Springer, vol. 339(1), pages 693-739, August.
    3. Niu, Baozhuang & Zhang, Jianhua & Xie, Fengfeng, 2024. "Drone logistics’ resilient development: impacts of consumer choice, competition, and regulation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 185(C).
    4. Zhang, Juan & Campbell, James F. & Sweeney, Donald C., 2024. "A continuous approximation approach to integrated truck and drone delivery systems," Omega, Elsevier, vol. 126(C).
    5. Zhu, Waiming & Hu, Xiaoxuan & Pei, Jun & Pardalos, Panos M., 2024. "Minimizing the total travel distance for the locker-based drone delivery: A branch-and-cut-based method," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).

    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. Ren, Xuan & Froger, Aurélien & Jabali, Ola & Liang, Gongqian, 2024. "A competitive heuristic algorithm for vehicle routing problems with drones," European Journal of Operational Research, Elsevier, vol. 318(2), pages 469-485.
    2. Zhu, Waiming & Hu, Xiaoxuan & Pei, Jun & Pardalos, Panos M., 2024. "Minimizing the total travel distance for the locker-based drone delivery: A branch-and-cut-based method," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    3. Madani, Batool & Ndiaye, Malick & Salhi, Said, 2024. "Hybrid truck-drone delivery system with multi-visits and multi-launch and retrieval locations: Mathematical model and adaptive variable neighborhood search with neighborhood categorization," European Journal of Operational Research, Elsevier, vol. 316(1), pages 100-125.
    4. Zhou, Hang & Qin, Hu & Cheng, Chun & Rousseau, Louis-Martin, 2023. "An exact algorithm for the two-echelon vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 124-150.
    5. Jiang, Jie & Dai, Ying & Yang, Fei & Ma, Zujun, 2024. "A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services," European Journal of Operational Research, Elsevier, vol. 312(1), pages 125-137.
    6. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.
    7. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    8. Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2024. "Electric van-based robot deliveries with en-route charging," European Journal of Operational Research, Elsevier, vol. 317(3), pages 806-826.
    9. Dell’Amico, Mauro & Montemanni, Roberto & Novellani, Stefano, 2021. "Algorithms based on branch and bound for the flying sidekick traveling salesman problem," Omega, Elsevier, vol. 104(C).
    10. Salama, Mohamed R. & Srinivas, Sharan, 2022. "Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    11. 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.
    12. Archetti, Claudia & Peirano, Lorenzo & Speranza, M. Grazia, 2022. "Optimization in multimodal freight transportation problems: A Survey," European Journal of Operational Research, Elsevier, vol. 299(1), pages 1-20.
    13. Deng, Menghua & Li, Yuanbo & Ding, Jianpeng & Zhou, Yanlin & Zhang, Lianming, 2024. "Stochastic and robust truck-and-drone routing problems with deadlines: A Benders decomposition approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 190(C).
    14. Morandi, Nicola & Leus, Roel & Yaman, Hande, 2024. "The orienteering problem with drones," Other publications TiSEM 593f31f0-7b7b-4069-84ca-8, Tilburg University, School of Economics and Management.
    15. Xia, Yang & Zeng, Wenjia & Zhang, Canrong & Yang, Hai, 2023. "A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones," Transportation Research Part B: Methodological, Elsevier, vol. 171(C), pages 80-110.
    16. Morandi, Nicola & Leus, Roel & Matuschke, Jannik & Yaman, Hande, 2023. "The traveling salesman problem with drones: The benefits of retraversing the arcs," Other publications TiSEM 09f54df0-875e-40af-a43d-5, Tilburg University, School of Economics and Management.
    17. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2020. "Drone routing with energy function: Formulation and exact algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 364-387.
    18. Vincent F. Yu & Shih-Wei Lin & Panca Jodiawan & Yu-Chi Lai, 2023. "Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic," Mathematics, MDPI, vol. 11(20), pages 1-21, October.
    19. Mahmoudinazlou, Sasan & Kwon, Changhyun, 2024. "A hybrid genetic algorithm with type-aware chromosomes for Traveling Salesman Problems with Drone," European Journal of Operational Research, Elsevier, vol. 318(3), pages 719-739.
    20. Giuseppe Aiello & Rosalinda Inguanta & Giusj D’Angelo & Mario Venticinque, 2021. "Energy Consumption Model of Aerial Urban Logistic Infrastructures," Energies, MDPI, vol. 14(18), pages 1-19, September.

    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:eee:transb:v:168:y:2023:i:c:p:81-123. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.