Development of Particle Swarm Optimization and Simulated Annealing Algorithms to Solve Vehicle Routing Problems with Drones
Pengembangan Algoritma Particle Swarm Optimization dan Simulated Annealing untuk Menyelesaikan Vehicle Routing Problem with Drone
-
(1) * Hasan Aji Prawira
Institut Teknologi Sepuluh Nopember
Indonesia
(2) Budi Santosa Institut Teknologi Sepuluh Nopember
Indonesia
(*) Corresponding Author
Abstract
Vehicle Routing Problem with Drone (VRPD) is a problem of determining the number of routes for delivery of goods from the depot to a number of customers using trucks and drones. Drones are an alternative delivery tool besides trucks, each truck can be equipped with a support drone. Drones can be used to make a delivery while the truck is making others. By combining a truck and a drone, the truck can act as a tool for drone launch and landing so that the drones can reach long distances from the depot. The purpose of this problem is to minimize the cost of sending goods by trucks and drones. In this study, the Particle Swarm Optimization (PSO) and the Simulated Annealing (SA) are proposed to solve these problems. The Route Drone algorithm are used to help change the structure of the PSO and SA solutions into a VRPD solution. The proposed algorithm has been applied to 24 different scenarios ranging from 6 customers to 100 customers. The PSO and SA algorithms are able to find solutions that are close to optimal. The SA is able to find a better solution than the PSO.References
Rao, B., Gopi, A. G., & Maione, R. (2016). The societal impact of commercial drones. Technology in Society, 45, 83–90. https://doi.org/10.1016/j.techsoc.2016.02.009
Wohlsen, M. (2014). The Next Big Thing You Missed: Amazon’s Delivery Drones Could Work—They Just Need Trucks. Retrieved from https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/
Rose, C. (2013). Amazon’s Jeff Bezos looks to the future. Retrieved from https://www.cbsnews.com/news/amazons-jeff-bezos-looks-to-the-future/
Bryan, V. (2014). Drone delivery: DHL “parcelcopter” flies to German isle. Retrieved from https://www.reuters.com/article/us-deutsche-post-drones/drone-delivery-dhl-parcelcopter-flies-to-german-isle-idUSKCN0HJ1ED20140924
Mulia, K. (2019). JD warms Indonesia up to drone deliveries with first government-endorsed test flight. Retrieved from https://kr-asia.com/jd-warms-indonesia-up-to-drone-deliveries-with-first-government-endorsed-test-flight
Trop, J. (2016). Drone Delivery is About to Disrupt the Trucking Industry. Retrieved from https://www.trucks.com/2016/06/21/drone-delivery-reshape-trucking/
Toth, P., & Vigo, D. (2002). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM - Society for Industrial and Applied Mathematics.
Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 102(March), 289–315. https://doi.org/10.1016/j.trc.2019.02.018
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
Ponza, A. (2016). Optimization of Drone-Assisted Parcel Delivery. 80.
Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H. (2018). On the min-cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, 86(May 2016), 597–621. https://doi.org/10.1016/j.trc.2017.11.015
Wang, Z., & Sheu, J. B. (2019). Vehicle routing problem with drones. Transportation Research Part B: Methodological, 122, 350–364. https://doi.org/10.1016/j.trb.2019.03.005
Ham, A. M. (2018). Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transportation Research Part C: Emerging Technologies, 91(March), 1–14. https://doi.org/10.1016/j.trc.2018.03.025
Santosa, B., & Ai, T. J. (2017). Pengantar Metaheuristik - Implementasi dengan Matlab (1st ed.). Surabaya: ITS Tekno Sains.
Poli, R., Kennedy, J., & Blackwell, T. (2007). Particle swarm optimization: An overview. Swarm Intelligence, 1(1), 33–57. https://doi.org/10.1007/s11721-007-0002-0
Ai, T. J., & Kachitvichyanukul, V. (2009). Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Computers and Industrial Engineering, 56(1), 380–387. https://doi.org/10.1016/j.cie.2008.06.012
Schermer, D., Moeini, M., & Wendt, O. (2018). Algorithms for Solving the Vehicle Routing Problem with Drones. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10751 LNAI, 352–361. https://doi.org/10.1007/978-3-319-75417-8_33
Kennedy, J., & Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of the IEEE International Conference on Neural Networks, 4, 1942–1948. https://doi.org/10.1109/TST.2016.7442504
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671
Copyright (c) 2021 PROZIMA (Productivity, Optimization and Manufacturing System Engineering)
This work is licensed under a Creative Commons Attribution 4.0 International License.
