IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v181y2024ics1366554523003654.html
   My bibliography  Save this article

Optimization of the drone-assisted pickup and delivery problem

Author

Listed:
  • Mulumba, Timothy
  • Diabat, Ali

Abstract

The proposition of utilizing unmanned aerial vehicles (UAVs), colloquially known as drones, for the purpose of delivery was ushered into the mainstream by Amazon in 2013. Since then, UAVs have quickly gained traction as a feasible option for last-mile operations in transport and logistics. In the context of this research, we construct a mathematical framework aiming to depict the collaborative interaction between trucks and drones in coordinating pickup and delivery tasks with the objective of minimizing operational costs. The drone-assisted pickup and delivery problem (DAPDP) is a variant of the problem in which a single truck departs a depot with parcels and a UAV on board. As the truck picks up packages and makes deliveries, the UAV can also be used to make deliveries to customers near the truck’s position. As the unmanned aerial vehicle (UAV) embarks on its delivery task, the truck continues on its route, making further deliveries along the way and retrieving the UAV at another customer location different from the launch point. The model is presented as a mixed integer linear program (MILP), and a novel heuristic solution approach based on the classic Clarke–Wright savings heuristic is proposed. Our heuristic’s efficacy is evaluated in comparison to a scenario involving only trucks, with a comprehensive series of numerical experiments conducted to underscore the advantages of incorporating UAVs into the pickup and delivery problem. Finally, we perform a comprehensive sensitivity analysis of key drone parameters in order to demonstrate their impact.

Suggested Citation

  • Mulumba, Timothy & Diabat, Ali, 2024. "Optimization of the drone-assisted pickup and delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    • Handle: RePEc:eee:transe:v:181:y:2024:i:c:s1366554523003654
    DOI: 10.1016/j.tre.2023.103377
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554523003654
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2023.103377?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. Xiangyi Zhang & Lu Chen & Michel Gendreau & André Langevin, 2022. "Learning-Based Branch-and-Price Algorithms for the Vehicle Routing Problem with Time Windows and Two-Dimensional Loading Constraints," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1419-1436, May.
    2. 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.
    3. Voudouris, Christos & Tsang, Edward, 1999. "Guided local search and its application to the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 113(2), pages 469-499, March.
    4. Nguyen, Minh Anh & Dang, Giang Thi-Huong & Hà, Minh Hoàng & Pham, Minh-Trien, 2022. "The min-cost parallel drone scheduling vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 299(3), pages 910-930.
    5. Doole, Malik & Ellerbroek, Joost & Hoekstra, Jacco, 2020. "Estimation of traffic density from drone-based delivery in very low level urban airspace," Journal of Air Transport Management, Elsevier, vol. 88(C).
    6. Merkert, Rico & Bushell, James, 2020. "Managing the drone revolution: A systematic literature review into the current use of airborne drones and future strategic directions for their effective control," Journal of Air Transport Management, Elsevier, vol. 89(C).
    7. 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.
    8. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    9. Gao, Jiajing & Zhen, Lu & Laporte, Gilbert & He, Xueting, 2023. "Scheduling trucks and drones for cooperative deliveries," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 178(C).
    Full references (including those not matched with items on IDEAS)

    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. Derigs, U. & Kaiser, R., 2007. "Applying the attribute based hill climber heuristic to the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 177(2), pages 719-732, March.
    2. Kloster, Konstantin & Moeini, Mahdi & Vigo, Daniele & Wendt, Oliver, 2023. "The multiple traveling salesman problem in presence of drone- and robot-supported packet stations," European Journal of Operational Research, Elsevier, vol. 305(2), pages 630-643.
    3. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    4. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    5. Jamal Ouenniche & Prasanna K. Ramaswamy & Michel Gendreau, 2017. "A dual local search framework for combinatorial optimization problems with TSP application," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1377-1398, November.
    6. Meng, Shanshan & Guo, Xiuping & Li, Dong & Liu, Guoquan, 2023. "The multi-visit drone routing problem for pickup and delivery services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    7. Büyüközkan, Gülçin & Ilıcak, Öykü, 2022. "Smart urban logistics: Literature review and future directions," Socio-Economic Planning Sciences, Elsevier, vol. 81(C).
    8. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    9. Chiang, Wen-Chyuan & Li, Yuyu & Shang, Jennifer & Urban, Timothy L., 2019. "Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization," Applied Energy, Elsevier, vol. 242(C), pages 1164-1175.
    10. Aldana-Galván, I. & Catana-Salazar, J.C. & Díaz-Báñez, J.M. & Duque, F. & Fabila-Monroy, R. & Heredia, M.A. & Ramírez-Vigueras, A. & Urrutia, J., 2020. "On optimal coverage of a tree with multiple robots," European Journal of Operational Research, Elsevier, vol. 285(3), pages 844-852.
    11. Palhazi Cuervo, Daniel & Goos, Peter & Sörensen, Kenneth & Arráiz, Emely, 2014. "An iterated local search algorithm for the vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 237(2), pages 454-464.
    12. Zhao, Lei & Bi, Xinhua & Li, Gendao & Dong, Zhaohui & Xiao, Ni & Zhao, Anni, 2022. "Robust traveling salesman problem with multiple drones: Parcel delivery under uncertain navigation environments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    13. Muyldermans, L. & Pang, G., 2010. "On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm," European Journal of Operational Research, Elsevier, vol. 206(1), pages 93-103, October.
    14. Yin, Yunqiang & Yang, Yongjian & Yu, Yugang & Wang, Dujuan & Cheng, T.C.E., 2023. "Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    15. 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).
    16. Kim Seongheon & Kim Suhwan, 2022. "VRP of Drones Considering Power Consumption Rate and Wind Effects," LOGI – Scientific Journal on Transport and Logistics, Sciendo, vol. 13(1), pages 210-221, January.
    17. Chen, Cheng & Demir, Emrah & Huang, Yuan, 2021. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1164-1180.
    18. 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.
    19. Gong, Manlin & Hu, Yucong & Chen, Zhiwei & Li, Xiaopeng, 2021. "Transfer-based customized modular bus system design with passenger-route assignment optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 153(C).
    20. Smith, John Paul, 1974. "A Lockset analysis of farm to plant milk assembly," ISU General Staff Papers 1974010108000018144, Iowa State University, Department of Economics.

    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:transe:v:181:y:2024:i:c:s1366554523003654. 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/600244/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.