SpringerLink
Log in

Integrated Path Planning and Task Assignment Model for On-Demand Last-Mile UAV-Based Delivery

  • Conference paper
  • First Online:
Computational Logistics (ICCL 2022)

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

Included in the following conference series:

  • 1206 Accesses

Abstract

Recent technological advancements and investments have transformed Unmanned Aerial Vehicles (UAVs) into a credible and reliable tool for the provision of on-demand last-mile logistics services. Nevertheless, few studies have developed integrated task assignment and path planning models that consider dynamic environments and stochastic demand generation. This paper addresses this research gap by develo** a reinforcement learning path planning approach, coupled with a task assignment model formulated as a mixed-integer programming problem. The performance of task assignment model is evaluated against a dynamic programming method, and a First-In-First-Out heuristic which serves as the baseline. A case study based on the City of London is proposed to demonstrate the applicability of the integrated model. Results demonstrate the effectiveness of the mixed-integer approach in coordinating the UAV fleet compared to the other methods, with the dynamic programming providing higher returns for large fleet sizes.

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
EUR 32.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
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    PSO is a metaheuristic that utilises agents to search the solution-space through the manipulation of their position and their velocity.

References

  1. Biswas, S., Anavatti, S., Garratt, M.: A time-efficient co-operative path planning model combined with task assignment for multi-agent systems. Robotics 8(35), 1–16 (2019)

    Google Scholar 

  2. Cai, W., Zhang, M., Zheng, Y.R.: Task assignment and path planning for multiple autonomous underwater vehicles using 3D Dubins curves. Sensors (Switz.) 17(7) (2017). https://doi.org/10.3390/s17071607

  3. Chang, H., Chen, Y., Zhang, B., Doermann, D.: Multi-UAV mobile edge computing and path planning platform based on reinforcement learning. IEEE Trans. Emerging Topics Comput. Intell. 6(3), 489–498 (2022). https://doi.org/10.1109/TETCI.2021.3083410

    Article  Google Scholar 

  4. Chen, Z., Alonso-Mora, J., Bai, X., Harabor, D.D., Stuckey, P.J.: Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robot. Autom. Lett. 6(3), 5816–5823 (2021). https://doi.org/10.1109/LRA.2021.3074883

    Article  Google Scholar 

  5. David, J., Philippsen, R.: Task assignment and trajectory planning in dynamic environments for multiple vehicles. Frontiers Artif. Intell. Appl. 278, 179–181 (2015). https://doi.org/10.3233/978-1-61499-589-0-179

    Article  Google Scholar 

  6. Dorling, K., Heinrichs, J., Messier, G.G., Magierowski, S.: Vehicle routing problems for drone delivery. IEEE Trans. Syst. Man Cybern. Syst. 47(1), 70–85 (2017). https://doi.org/10.1109/TSMC.2016.2582745

    Article  Google Scholar 

  7. Escribano Macias, J., Angeloudis, P., Ochieng, W.: Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles. Transp. Res. Part C Emerging Technol. 110(November 2019), 56–80 (2020). https://doi.org/10.1016/j.trc.2019.11.002

  8. Grippa, P.: Decision making in a UAV-based delivery system with impatient customers. In: IEEE International Conference on Intelligent Robots and Systems, November 2016, pp. 5034–5039 (2016). https://doi.org/10.1109/IROS.2016.7759739

  9. Hader, M.: Advanced air mobility: market study for APAC. Technical report, Roland Berger, Munich, Germany (2022)

    Google Scholar 

  10. Huang, H., Zhu, D., Ding, F.: Dynamic task assignment and path planning for multi-AUV system in variable ocean current environment. J. Intell. Robot. Syst. 999–1012 (2013). https://doi.org/10.1007/s10846-013-9870-2

  11. Huo, L., Zhu, J., Wu, G., Li, Z.: A novel simulated annealing based strategy for balanced UAV task assignment and path planning. Sensors (Switz.) 20(17), 1–21 (2020). https://doi.org/10.3390/s20174769

    Article  Google Scholar 

  12. Kuru, K., Ansell, D., Khan, W., Yetgin, H.: Analysis and optimization of unmanned aerial vehicle swarms in logistics: an intelligent delivery platform. IEEE Access 7, 15804–15831 (2019). https://doi.org/10.1109/ACCESS.2019.2892716

    Article  Google Scholar 

  13. Macias, J.J.E., Angeloudis, P., Ochieng, W.: Integrated trajectory-location-routing for rapid humanitarian deliveries using unmanned aerial vehicles. In: 2018 Aviation Technology, Integration, and Operations Conference, pp. 1–20 (2018). https://doi.org/10.2514/6.2018-3045

  14. Moon, S., Oh, E., Shim, D.H.: An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments. J. Intell. Robot. Syst. Theory Appl. 70(1–4), 303–313 (2013). https://doi.org/10.1007/s10846-012-9740-3

    Article  Google Scholar 

  15. Morgan Stanley Research: eVTOL/Urban air mobility TAM update: a slow take-off. But sky’s the limit. Technical report, Morgan Stanley (2021)

    Google Scholar 

  16. Rojas Viloria, D., Solano-Charris, E.L., Muñoz-Villamizar, A., Montoya-Torres, J.R.: Unmanned aerial vehicles/drones in vehicle routing problems: a literature review. Int. Trans. Oper. Res. 28(4), 1626–1657 (2021). https://doi.org/10.1111/itor.12783

    Article  Google Scholar 

  17. Thibbotuwawa, A., Bocewicz, G., Nielsen, P., Banaszak, Z.: Unmanned aerial vehicle routing problems: a literature review. Appl. Sci. (Switz.) 10(13) (2020). https://doi.org/10.3390/app10134504

  18. Zhang, B., Liu, W., Mao, Z., Liu, J., Shen, L.: Cooperative and Geometric Learning Algorithm (CGLA) for path planning of UAVs with limited information. Automatica 50(3), 809–820 (2014)

    Article  Google Scholar 

  19. Zhu, D., Huang, H., Yang, S.X.: Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace. IEEE Trans. Cybern. 43(2), 504–514 (2013). https://doi.org/10.1109/TSMCB.2012.2210212

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Imperial College London, London, SW7 2AZ, UK

    Jose Escribano, Huan Chang & Panagiotis Angeloudis

Authors
  1. Jose Escribano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Huan Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Panagiotis Angeloudis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jose Escribano .

Editor information

Editors and Affiliations

  1. Universitat Pompeu Fabra, Barcelona, Spain

    Jesica de Armas

  2. Universitat Pompeu Fabra, Barcelona, Spain

    Helena Ramalhinho

  3. Universität Hamburg, Hamburg, Germany

    Stefan Voß

Rights and permissions

Reprints and permissions

Copyright information

© 2022 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

Escribano, J., Chang, H., Angeloudis, P. (2022). Integrated Path Planning and Task Assignment Model for On-Demand Last-Mile UAV-Based Delivery. In: de Armas, J., Ramalhinho, H., Voß, S. (eds) Computational Logistics. ICCL 2022. Lecture Notes in Computer Science, vol 13557. Springer, Cham. https://doi.org/10.1007/978-3-031-16579-5_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-16579-5_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-16578-8

  • Online ISBN: 978-3-031-16579-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation