Last mile delivery Optimisation model for drone-enabled Vehicle Routing Problem

Ismail Tausif

doi:10.59973/emjsr.11

Authors

Ismail Tausif University of Portsmouth

DOI:

https://doi.org/10.59973/emjsr.11

Abstract

In light of e-commerce's exponential growth trajectory over recent years, it has never been more critical to evaluate the last-mile delivery segment for its efficiency and cost-effectiveness. Autonomous vehicles (drones) offer considerable promise as potential solutions with ongoing investigations into emerging technologies in this context. To address problems related to last mile-delivery in logistics operations, the practicality of adopting a hybrid truck-drone delivery system is examined through this study. The researchers utilized Mixed-integer linear programming (MILP)and Gurobi optimization solvers both for optimizing performance as well as facilitating execution. While testing a drone dataset of a well-known logistics company as part of their research using an optimization model, the findings suggested that were remarkable competitive advantages including significant gains in reduction of timing. Nevertheless, there are several constraints like maintenance, recharging, difficult weather conditions & traffic congestion-necessitating focused innovative AI-based approaches. In spite of these impediments, a hybrid truck-drone’s potential applicability can remarkably boost the efficiency of last-mile delivery operations.

References

Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981. https://doi.org/10.1287/trsc.2017.0806 DOI: https://doi.org/10.1287/trsc.2017.0791

Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2006). The Traveling Salesman Problem. Princeton University Press.

Aurambout, J.-P., Gkoumas, K., & Ciuffo, B. (2019). Last mile delivery by drones: An estimation of viable market potential and access to citizens across European cities. European Transport Research Review, 11(1), 30. https://doi.org/10.1186/s12544-019-0368-2 DOI: https://doi.org/10.1186/s12544-019-0368-2

Bakir, I. and Tiniç, G.Ö., 2020. Optimizing drone-assisted last-mile deliveries: The vehicle routing problem with flexible drones. Optimization-Ouline. Org, pp.1-28.

Bamburry, D. (2015). Drones: Designed for product delivery. Design Management Review, 26(1), 40-48.

Bellman, R. (1957). Dynamic Programming. Princeton University Press.

Bloomberg. (2019, June 5). Amazon Unveils Futuristic Helicopter-Plane Hybrid Drone for Deliveries. Bloomberg.Com. https://www.bloomberg.com/news/articles/2019- 06-05/amazon-poised-to-test-chopper-plane-mashup-for-drone-deliveries

CAA. (2020). Drone and model aircraft code. Civil Aviation Authority.

Choi, Y. K., Kim, H., Lee, K., & Kim, Y. (2019). Drone flight path planning for safe and efficient delivery in wind. IEEE Access, 7, 19816-19827.

Clarke, R. (2014). Understanding the drone epidemic. Computer Law & Security Review, 30(3), 230-246. DOI: https://doi.org/10.1016/j.clsr.2014.03.002

Clothier, R. A., Greer, D. A., Greer, D. G., & Mehta, A. M. (2015). Risk perception and the public acceptance of drones. Risk Analysis, 35(6), 1167-1183. DOI: https://doi.org/10.1111/risa.12330

Cordeau, J. F., Laporte, G., Savelsbergh, M. W., & Vigo, D. (2007). Vehicle routing. In Handbooks in operations research and management science (Vol. 14, pp. 367-428). Elsevier. DOI: https://doi.org/10.1016/S0927-0507(06)14006-2

DHL. (2014). UNMANNED AERIAL VEHICLE IN LOGISTICS: A DHL perspective on implications and use cases for the logistics industry (p. 24).

DHL. (2019, May 16). DHL launches its first regular fully-automated and intelligent urban drone delivery service. Deutsche Post DHL Group. https://www.dpdhl.com/en/media-relations/press-releases/2019/dhl-launches-itsfirst-regular-fully-automated-and-intelligent-urban-drone-delivery-service.html

Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press. DOI: https://doi.org/10.7551/mitpress/1290.001.0001

Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2017). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85. https://doi.org/10.1109/TSMC.2016.2582742 DOI: https://doi.org/10.1109/TSMC.2016.2582745

Du, L., Li, X., Gan, Y. and Leng, K., 2022. Optimal Model and Algorithm of Medical Materials Delivery Drone Routing Problem under Major Public Health Emergencies. Sustainability, 14(8), p.4651. DOI: https://doi.org/10.3390/su14084651

Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4), 1472-1483. https://doi.org/10.1016/j.cie.2009.05.009 DOI: https://doi.org/10.1016/j.cie.2009.05.009

Faiz, T.I., Vogiatzis, C. and Noor-E-Alam, M., 2020. Robust two-echelon vehicle and drone routing for post-disaster humanitarian operations. arXiv preprint arXiv:2001.06456.

Farajzadeh, F., Moadab, A., Valilai, O.F. and Houshmand, M., 2020. A novel mathematical model for a cloud-based drone-enabled vehicle routing problem considering multi-echelon supply chain. IFAC-PapersOnLine, 53(2), pp.15035-15040. DOI: https://doi.org/10.1016/j.ifacol.2020.12.2004

Floether, K. (2018) Truck – drone delivery, Department of Civil & Mineral Engineering. Available at: https://civmin.utoronto.ca/breaking-new-ground-and-taking-to-the-skies/truck-drone-delivery/ (Accessed: 25 May 2023).

Francis, P., Smilowitz, K., & Tzur, M. (2008). The period vehicle routing problem and its extensions. In Vehicle Routing: Problems, Methods, and Applications (pp. 73-102). Society for Industrial and Applied Mathematics. DOI: https://doi.org/10.1007/978-0-387-77778-8_4

Gendreau, M., Hertz, A., & Laporte, G. (2002). New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40(6), 1086-1094. DOI: https://doi.org/10.1287/opre.40.6.1086

Gendreau, M., Laporte, G., & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12. DOI: https://doi.org/10.1016/0377-2217(95)00050-X

Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549. DOI: https://doi.org/10.1016/0305-0548(86)90048-1

Gómez-Lagos, J., Candia-Véjar, A. and Encina, F., 2021. A new truck-drone routing problem for parcel delivery services aided by parking lots. IEEE Access, 9, pp.11091-11108. DOI: https://doi.org/10.1109/ACCESS.2021.3050658

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

Huang, Y., Savkin, A. V., & Ding, M. (2018). Mission-aware unmanned aerial vehicle path planning for urban wireless data collection. IEEE Transactions on Vehicular Technology, 67(6), 5486-5491.

Intelligent Living. (n.d.). UPS Teams Up With German Startup Wingcopter To Expand Drone Deliveries. Retrieved March 17, 2023, from https://www.intelligentliving.co/ups-wingcopter-drone-deliveries/

Jeong, H.Y. and Lee, S., 2019. Optimization of Vehicle-Carrier Routing: Mathematical Model and Comparison with Related Routing Models. Procedia Manufacturing, 39, pp.307-313. DOI: https://doi.org/10.1016/j.promfg.2020.01.337

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of IEEE International Conference on Neural Networks (Vol. 4, pp. 1942-1948).

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680. DOI: https://doi.org/10.1126/science.220.4598.671

Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. DOI: https://doi.org/10.1016/0377-2217(92)90192-C

Levin, S., Toh, J., & Meggers, F. (2020). Delivery drones: Energy consumption and environmental implications. Journal of Industrial Ecology, 24(5), 955-968.

Liang, K. H., & Smith, J. (2004). An ant colony optimization algorithm integrated with a rule-based system for the protein folding problem. In Proceedings of the 2004 Congress on Evolutionary Computation (CEC2004) (Vol. 2, pp. 2068-2074).

Liu, Y., 2019. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research, 111, pp.1-20. DOI: https://doi.org/10.1016/j.cor.2019.05.024

Liu, Y., Liu, Z., Shi, J., Wu, G. and Pedrycz, W., 2020. Two-echelon routing problem for parcel delivery by cooperated truck and drone. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(12), pp.7450-7465. DOI: https://doi.org/10.1109/TSMC.2020.2968839

Moadab, A., Farajzadeh, F. and Fatahi Valilai, O., 2022. Drone routing problem model for last-mile delivery using the public transportation capacity as moving charging stations. Scientific Reports, 12(1), pp.1-16. DOI: https://doi.org/10.1038/s41598-022-10408-4

Moshref-Javadi, M., Hemmati, A. and Winkenbach, M. (2020) “A truck and drones model for last-mile delivery: A mathematical model and heuristic approach,” Applied Mathematical Modelling, 80, pp. 290–318. Available at: https://doi.org/10.1016/j.apm.2019.11.020. DOI: https://doi.org/10.1016/j.apm.2019.11.020

Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109. https://doi.org/10.1016/j.trc.2015.03.005 DOI: https://doi.org/10.1016/j.trc.2015.03.005

Nguyen, M.A., Dang, G.T.H., Hà, M.H. and Pham, M.T., 2022. The min-cost parallel drone scheduling vehicle routing problem. European Journal of Operational Research, 299(3), pp.910-930. DOI: https://doi.org/10.1016/j.ejor.2021.07.008

Nhan, J., Huey, R., & Brolliar, S. (2020). Drone technology: The good, the bad and the horrid. Journal of Transportation Security, 13, 85-102.

Nikkei Asian Review. (2019, January 26). Rakuten’s package delivery drones to take flight soon. Nikkei Asian Review. https://asia.nikkei.com/Business/Companies/Rakuten-s-package-delivery-dronesto-take-flight-soo

Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(1), 421-451. DOI: https://doi.org/10.1007/BF02023004

Pachayappan, M. and Sudhakar, V., 2021. A solution to drone routing problems using docking stations for pickup and delivery services. Transportation Research Record, 2675(12), pp.1056-1074. DOI: https://doi.org/10.1177/03611981211032219

Pasha, J., Dulebenets, M.A., Kavoosi, M., Abioye, O.F., Wang, H. and Guo, W., 2020. An optimization model and solution algorithms for the vehicle routing problem with a “factory-in-a-box”. Ieee Access, 8, pp.134743-134763. DOI: https://doi.org/10.1109/ACCESS.2020.3010176

Pham, D. T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., & Zaidi, M. (2005). The bees algorithm. In Proceedings of the Manufacturing Engineering Society International Conference (pp. 454-459). DOI: https://doi.org/10.1016/B978-008045157-2/50081-X

Popović, D., Kovač, M. and Bjelić, N., 2019, May. A MIQP model for solving the vehicle routing problem with drones. In Proceedings of 4th Logistics International Conference–LOGIC (pp. 52-62).

Rahman, M., How, J. P., & Vian, J. (2017). System identification and control of rotorcraft-based unmanned aerial vehicles. Journal of Guidance, Control, and Dynamics, 40(5), 1051-1066.

Redi, A.P., Jewpanya, P., Kurniawan, A.C., Persada, S.F., Nadlifatin, R. and Dewi, O.A.C., 2020. A simulated annealing algorithm for solving a two-echelon vehicle routing problem with locker facilities. Algorithms, 13(9), p.218. DOI: https://doi.org/10.3390/a13090218

Sacramento, D., Pisinger, D. and Ropke, S., 2019. An adaptive large neighbourhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102, pp.289-315. DOI: https://doi.org/10.1016/j.trc.2019.02.018

Sajid, M., Mittal, H., Pare, S. and Prasad, M., 2022. Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach. Applied Soft Computing, 126, p.109225. DOI: https://doi.org/10.1016/j.asoc.2022.109225

Schermer, D., Moeini, M. and Wendt, O., 2019. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, 109, pp.134-158. DOI: https://doi.org/10.1016/j.cor.2019.04.021

Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265. DOI: https://doi.org/10.1287/opre.35.2.254

Souza, I.P., Boeres, M.C. and Moraes, R.E. (2023) “A robust algorithm based on differential evolution with local search for the capacitated vehicle routing problem,” Swarm and Evolutionary Computation, 77, p. 101245. Available at: https://doi.org/10.1016/j.swevo.2023.101245. DOI: https://doi.org/10.1016/j.swevo.2023.101245

Thibbotuwawa, A., Bocewicz, G., Nielsen, P. and Banaszak, Z., 2020. Unmanned aerial vehicle routing problems: a literature review. Applied sciences, 10(13), p.4504. DOI: https://doi.org/10.3390/app10134504

Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: Problems, methods, and applications. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973594 DOI: https://doi.org/10.1137/1.9781611973594

Wing. (n.d.). Wing. Retrieved March 17, 2023, from https://wing.com/

Wolsey, L. A. (1998). Integer Programming. Wiley.

Workhorse. (n.d.). Workhorse | HorseFly. Retrieved March 17, 2023, from https://workhorse.com/horsefly.html

Yoo, S. J., & Kim, H. (2017). Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing CO2 emissions in the delivery service industry. Transportation Research Part D: Transport and Environment, 61, 58-67. DOI: https://doi.org/10.1016/j.trd.2017.02.017

Zeng, F., Chen, Z., Clarke, J.P. and Goldsman, D., 2022. Nested vehicle routing problem: Optimizing drone-truck surveillance operations. Transportation Research Part C: Emerging Technologies, 139, p.103645. DOI: https://doi.org/10.1016/j.trc.2022.103645