iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-031-62922-8_3
Optimization of a Last Mile Delivery Model with a Truck and a Drone Using Mathematical Formulation and a VNS Algorithm | SpringerLink
Skip to main content
Springer Nature Link
Log in

Optimization of a Last Mile Delivery Model with a Truck and a Drone Using Mathematical Formulation and a VNS Algorithm

  • Conference paper
  • First Online:
Metaheuristics (MIC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14754))

Included in the following conference series:

  • 213 Accesses

Abstract7

The use of drones in last-mile delivery services has attained significant interest due to the need for fast delivery. In addition, drones have the potential to reduce the cost associated with last-mile deliveries. However, restrictions such as payload capacity, range limits, and legal regulations have restricted the effective operational range of drones. To assist in alleviating these operational limitations, integrating a conventional delivery truck with drones to form a truck-drone delivery system, has received significant attention in the literature. This paper presents a scenario in which a single drone works in tandem with a single truck to serve customers. The drone can perform multiple deliveries in a single route, and the objective is to minimize the total traveling costs of both vehicles. An integer linear programming (ILP) model is developed and solved to optimality for small instances using the exact solution method. Considering the complexity of the ILP model, a variable neighborhood search (VNS) algorithm is introduced and assessed using small and large instances. In addition, a modified VNS algorithm involving a new neighborhood selection strategy is proposed and compared to the basic VNS. Both algorithms generate solutions in a short computational time for instances with up to 100 customer nodes.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 74.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Chen, C., Pan, S.: Using the Crowd of Taxis to Last Mile Delivery in E-Commerce: methodological research. Federal Reserve Bank of St Louis, St. Louis (2016)

    Google Scholar 

  2. Gevaers, R., Van de Voorde, E., Vanelslander, T.: Cost modelling and simulation of last-mile characteristics in an innovative B2C supply chain environment with implications on urban areas and cities. Procedia Soc. Behav. Sci. 125, 398–411 (2014)

    Article  Google Scholar 

  3. Boysen, N., Fedtke, S., Schwerdfeger, S.: Last-mile delivery concepts: a survey from an operational research perspective. OR Spectrum 43(1), 1–58 (2021)

    Article  MathSciNet  Google Scholar 

  4. Agatz, N., Bouman, P., Schmidt, M.: Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52(4), 965–981 (2018)

    Article  Google Scholar 

  5. Mazareanu, E.: Projected global drone delivery service market size in 2023, by region (2020). https://www.statista.com/statistics/1136500/global-drone-delivery-service-market-size/. Accessed 13 Feb 2021

  6. Ross, S.: Seven Last-mile delivery challenges, and how to solve them (2021). https://www.supplychainbrain.com/blogs/1-think-tank/post/32800-last-mile-delivery-challenges-andhow-to-solve-them. Accessed 15 June 2021

  7. Murray, C.C., Chu, A.G.: The flying sidekick traveling salesman problem: optimization of drone assisted parcel delivery. Transp. Res. Part C 54, 86–109 (2015)

    Article  Google Scholar 

  8. Madani, B., Ndiaye, M.: Hybrid truck-drone delivery systems: a systematic literature review. IEEE Access. 10, 92854–92878 (2022)

    Article  Google Scholar 

  9. Poikonen, S., Wang, X., Golden, B.: The vehicle routing problem with drones: extended models and connections. Networks 70(1), 34–43 (2017)

    Article  MathSciNet  Google Scholar 

  10. Wang, X., Poikonen, S., Golden, B.: The vehicle routing problem with drones: several worst-case results. Optim. Lett. 11(4), 679–697 (2017)

    Article  MathSciNet  Google Scholar 

  11. Schermer, D., Moeini, M., Wendt, O.: A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Comput. Oper. Res. 109, 134–158 (2019)

    Article  MathSciNet  Google Scholar 

  12. Marinelli, M., Caggiani, L., Ottomanelli, M., Dell’Orco, M.: En route truck-drone parcel delivery for optimal vehicle routing strategies. IET Intel. Transp. Syst. 12(4), 253–261 (2018)

    Article  Google Scholar 

  13. Karak, A., Abdelghany, K.: The hybrid vehicle-drone routing problem for pick-up and delivery services. Transp. Res. Part C 102, 427–449 (2019)

    Article  Google Scholar 

  14. Poikonen, S., Golden, B.: The mothership and drone routing problem. INFORMS J. Comput. 32, 249–262 (2020)

    Article  MathSciNet  Google Scholar 

  15. The HorseFly UAV.: Workhorse. https://workhorse.com/horsefly.html. Accessed 15 Mar 2021

  16. Poikonen, S., Golden, B.: Multi-visit drone routing problem. Comput. Oper. Res. 113, 104802 (2020)

    Article  MathSciNet  Google Scholar 

  17. Kitjacharoenchai, P., Min, B.-C., Lee, S.: Two echelon vehicle routing problem with drones in last mile delivery. Int. J. Prod. Econ. 225, 107598 (2020)

    Article  Google Scholar 

  18. Wang, Z., Sheu, J.-B.: Vehicle routing problem with drones. Transport. Res. Part B: Methodol. 122, 350–364 (2019)

    Article  Google Scholar 

  19. Meng, S., Guo, X., Li, D., Liu, G.: The multi-visit drone routing problem for pickup and delivery services. Transport. Res. Part E: Logist. Transport. Rev. 169, 102990 (2023)

    Article  Google Scholar 

  20. Gu, R., Poon, M., Luo, Z., Liu, Y., Liu, Z.: A hierarchical solution evaluation method and a hybrid algorithm for the vehicle routing problem with drones and multiple visits. Transport. Res. Part C 141, 103733 (2022)

    Article  Google Scholar 

  21. Luo, Z., Gu, R., Poon, M., Liu, Z., Lim, A.: A last-mile drone-assisted one-to-one pickup and delivery problem with multi-visit drone trips. Comput. Oper. Res. 148, 106015 (2022)

    Article  MathSciNet  Google Scholar 

  22. Wang, Z., Sheu, J.-B.: Vehicle routing problem with drones. Transp. Res. Part B 122, 350–364 (2019)

    Article  Google Scholar 

  23. Tamke, F., Buscher, U.: A branch-and-cut algorithm for the vehicle routing problem with drones. Transp. Res. Part B 144, 174–203 (2021)

    Article  Google Scholar 

  24. Sacramento, D., Pisinger, D., Ropke, S.: An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transp. Res. Part C 102, 289–315 (2019)

    Article  Google Scholar 

  25. Salama, M.R., Srinivas, S.: Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites. Transport. Res. Part E 164, 102788 (2022)

    Article  Google Scholar 

  26. Kuo, R.J., Lu, S.-H., Lai, P.-Y., Mara, S.T.W.: Vehicle routing problem with drones considering time windows. Expert Syst. Appl. 191, 116264 (2022)

    Article  Google Scholar 

  27. Elshaer, R., Awad, H.: A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Comput. Ind. Eng. 140, 106242 (2020)

    Article  Google Scholar 

  28. de Freitas, J.C., Penna, P.H.V.: A variable neighborhood search for flying sidekick traveling salesman problem. Int. Trans. Oper. Res. 27(1), 267–290 (2020)

    Article  MathSciNet  Google Scholar 

  29. Campbell, J.F., Sweeney, D., II, Z.J.: Strategic design for delivery with trucks and drones. In: Technical Report (2017)

    Google Scholar 

  30. Madani, B., Ndiaye, M., Salhi, S.: Hybrid truck-drone delivery system with multi-visits and multi-launch and retrieval locations: Mathematical model and adaptive variable neighborhood search with neighborhood categorization. Eur. J. Oper. Res. 316, 100–125 (2024)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. American University of Sharjah, Sharjah, UAE

    Batool Madani & Malick Ndiaye

  2. Khalifa University, Abu Dhabi, UAE

    Said Salhi

  3. University of Kent, Canterbury, UK

    Said Salhi

Authors
  1. Batool Madani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Malick Ndiaye
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Said Salhi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Batool Madani .

Editor information

Editors and Affiliations

  1. Centre de Recherche, Université Bretagne Sud, Lorient, France

    Marc Sevaux

  2. Centre de Recherche, Université Bretagne Sud, LORIENT, France

    Alexandru-Liviu Olteanu

  3. Universidad Rey Juan Carlos, Móstoles, Spain

    Eduardo G. Pardo

  4. University of Macedonia, Thessaloniki, Greece

    Angelo Sifaleras

  5. Université de Technologie de Troyes, Troyes Cedex, France

    Salma Makboul

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Madani, B., Ndiaye, M., Salhi, S. (2024). Optimization of a Last Mile Delivery Model with a Truck and a Drone Using Mathematical Formulation and a VNS Algorithm. In: Sevaux, M., Olteanu, AL., Pardo, E.G., Sifaleras, A., Makboul, S. (eds) Metaheuristics. MIC 2024. Lecture Notes in Computer Science, vol 14754. Springer, Cham. https://doi.org/10.1007/978-3-031-62922-8_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-62922-8_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-62921-1

  • Online ISBN: 978-3-031-62922-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation