IDEAS home Printed from https://ideas.repec.org/a/eee/jaitra/v124y2025ics0969699724002011.html

MILP-based cost and time-competitive vehicle routing problem for last-mile delivery service using a swarm of UAVs and UGVs

Author

Listed:
  • Jung, Sunghun

Abstract

There are numerous studies on the unmanned vehicle routing problem (VRP) considering battery constraints in the areas of 1) path-planning problem based on intelligent task allocation and 2) determination of routes according to defined objectives and constraints. However, in most previous literature, only a simple linear approximation of battery energy consumption is considered, producing unrealistic results. In this study, a cost and time-competitive VRP is established and solved using mixed-integer linear programming (MILP), considering the relationship between the cost and electricity consumption of unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs). In particular, the maximum flyable and drivable ranges of the UAV and UGV were calculated by setting a linear capacity degradation equation based on the state of health, considering a limited number of (dis)charge cycles. This approach guarantees more realistic optimization results due to the adaptation of the detailed characteristics of battery-related information. Numerical analyses using two solvers based on MILP, 1) COIN-OR Branch and Cut (CBC) and 2) Gurobi, were performed with four different scenarios and four corresponding cases for each scenario by varying the number of demanders. The results show that using a combination of UAVs and UGVs slightly reduces the cost by approximately 1% but significantly reduces the delivery completion time by approximately 79%. The simulation running time was approximately 1.1Â s for all the cases, and the CBC solver operates faster than the Gurobi solver by approximately 0.93%.

Suggested Citation

  • Jung, Sunghun, 2025. "MILP-based cost and time-competitive vehicle routing problem for last-mile delivery service using a swarm of UAVs and UGVs," Journal of Air Transport Management, Elsevier, vol. 124(C).
    • Handle: RePEc:eee:jaitra:v:124:y:2025:i:c:s0969699724002011
    DOI: 10.1016/j.jairtraman.2024.102736
    as

    Download full text from publisher

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

    for a different version of it.

    References listed on IDEAS

    as
    1. Valeska Engesser & Evy Rombaut & Lieselot Vanhaverbeke & Philippe Lebeau, 2023. "Autonomous Delivery Solutions for Last-Mile Logistics Operations: A Literature Review and Research Agenda," Sustainability, MDPI, vol. 15(3), pages 1-17, February.
    2. Kyriakakis, Nikolaos A. & Marinaki, Magdalene & Matsatsinis, Nikolaos & Marinakis, Yannis, 2022. "A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning," European Journal of Operational Research, Elsevier, vol. 300(3), pages 992-1004.
    3. 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).
    4. Sunghun Jung & Heon Jeong, 2017. "Extended Kalman Filter-Based State of Charge and State of Power Estimation Algorithm for Unmanned Aerial Vehicle Li-Po Battery Packs," Energies, MDPI, vol. 10(8), pages 1-13, August.
    5. Sunghun Jung, 2020. "Development and Verification of Hybrid Power Controller Using Indoor HIL Test for the Solar UAV," Energies, MDPI, vol. 13(8), pages 1-11, April.
    6. 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).
    7. Brennan Borlaug & Matteo Muratori & Madeline Gilleran & David Woody & William Muston & Thomas Canada & Andrew Ingram & Hal Gresham & Charlie McQueen, 2021. "Heavy-duty truck electrification and the impacts of depot charging on electricity distribution systems," Nature Energy, Nature, vol. 6(6), pages 673-682, June.
    8. Robin Lovelace, 2021. "Open source tools for geographic analysis in transport planning," Journal of Geographical Systems, Springer, vol. 23(4), pages 547-578, October.
    9. Lemardelé, Clément & Estrada, Miquel & Pagès, Laia & Bachofner, Mónika, 2021. "Potentialities of drones and ground autonomous delivery devices for last-mile logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(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. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    2. Cui, Shaohua & Yang, Ying & Gao, Kun & Cui, Heqi & Najafi, Arsalan, 2024. "Integration of UAVs with public transit for delivery: Quantifying system benefits and policy implications," Transportation Research Part A: Policy and Practice, Elsevier, vol. 183(C).
    3. Pang, Bizhao & Hu, Xinting & Dai, Wei & Low, Kin Huat, 2024. "Stochastic route optimization under dynamic ground risk uncertainties for safe drone delivery operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).
    4. 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).
    5. Yang, Xin & Cao, Wenjie & Wang, Kai & Yin, Haodong & Wu, Jianjun & Wu, Lingxiao, 2025. "Integrated scheduling of truck and drone fleets for cargo transportation in post-disaster relief: A two-stage stochastic optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 196(C).
    6. Samani, Ali Riahi & Talebian, Ahmadreza & Mishra, Sabyasachee & Golias, Mihalis, 2025. "Evaluating consumer shopping, delivery demands, and last-mile preferences: An integrated MDCEV-HCM approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 197(C).
    7. Wenming Liu & Jingjing Li, 2025. "RETRACTED ARTICLE: Knowledge Dynamics in Rural Tourism Supply Chains: Challenges, Innovations, and Cross-Sector Applications," Journal of the Knowledge Economy, Springer;Portland International Center for Management of Engineering and Technology (PICMET), vol. 16(2), pages 6732-6764, June.
    8. Higgins, Christopher D. & Páez, Antonio & Kim, Gyoorie & Wang, Jue, 2021. "Changes in accessibility to emergency and community food services during COVID-19 and implications for low income populations in Hamilton, Ontario," Social Science & Medicine, Elsevier, vol. 291(C).
    9. Antonio Páez, 2021. "Open spatial sciences: an introduction," Journal of Geographical Systems, Springer, vol. 23(4), pages 467-476, October.
    10. He, Xinyu & Li, Lishuai & Mo, Yanfang & Sun, Zhankun & Qin, S. Joe, 2025. "Air Corridor Planning for Urban Drone Delivery: Complexity Analysis and Comparison via Multi-Commodity Network Flow and Graph Search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    11. Ghoniem, Ahmed & Boz, Semih & El-Adle, Amro M., 2025. "Parcel delivery by vehicle and drone in ordered customer neighborhoods," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 197(C).
    12. 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.
    13. He, Xinyu & He, Fang & Li, Lishuai & Zhang, Lei & Xiao, Gang, 2022. "A route network planning method for urban air delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    14. Wan, Yuchun & He, Zhenggang & Gao, Yufan & Xue, Yujia, 2024. "Long-haul truck charging planning problem considering time flexibility and energy flexibility," Energy, Elsevier, vol. 306(C).
    15. Chen, Enming & Zhou, Zhongbao & Li, Ruiyang & Chang, Zhongxiang & Shi, Jianmai, 2024. "The multi-fleet delivery problem combined with trucks, tricycles, and drones for last-mile logistics efficiency requirements under multiple budget constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 187(C).
    16. 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).
    17. Elise Desjardins & Christopher D. Higgins & Darren M. Scott & Emma Apatu & Antonio Páez, 2022. "Correlates of bicycling trip flows in Hamilton, Ontario: fastest, quietest, or balanced routes?," Transportation, Springer, vol. 49(3), pages 867-895, June.
    18. Kai Ma & YongJian Tan & Zhong Xie & Qinjun Qiu & Siqiong Chen, 2022. "Chinese toponym recognition with variant neural structures from social media messages based on BERT methods," Journal of Geographical Systems, Springer, vol. 24(2), pages 143-169, April.
    19. Tian, Xuelin & An, Chunjiang & Chen, Zhikun, 2023. "The role of clean energy in achieving decarbonization of electricity generation, transportation, and heating sectors by 2050: A meta-analysis review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 182(C).
    20. Aston, Laura & Currie, Graham & Kamruzzaman, Md. & Delbosc, Alexa & Brands, Ties & van Oort, Niels & Teller, David, 2021. "Multi-city exploration of built environment and transit mode use: Comparison of Melbourne, Amsterdam and Boston," Journal of Transport Geography, Elsevier, vol. 95(C).

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:jaitra:v:124:y:2025:i:c:s0969699724002011. 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.journals.elsevier.com/journal-of-air-transport-management/ .

    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.