Last mile delivery Optimisation model for drone-enabled Vehicle Routing Problem
DOI:
https://doi.org/10.59973/emjsr.11Abstract
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
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
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.
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.
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.
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.
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
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.
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
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.
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.
Gendreau, M., Hertz, A., & Laporte, G. (2002). New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40(6), 1086-1094.
Gendreau, M., Laporte, G., & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
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.
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.
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.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358.
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.
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.
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.
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.
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
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.
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.
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.
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.
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).
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.
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.
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.
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.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265.
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.
Thibbotuwawa, A., Bocewicz, G., Nielsen, P. and Banaszak, Z., 2020. Unmanned aerial vehicle routing problems: a literature review. Applied sciences, 10(13), p.4504.
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
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.
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.
Downloads
Published
Versions
- 2023-07-11 (2)
- 2023-07-11 (1)
How to Cite
Issue
Section
License
Copyright (c) 2023 Ismail Tausif
This work is licensed under a Creative Commons Attribution 4.0 International License.
