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
Article Sidebar
Picture in here are illustration from public domain image or provided by the author, as part of their works
Published:
Jul 6, 2021
Keywords:
Vehicle Routing Problem, Drone, Particle Swarm Optimization, Simulated Annealing, Metaheuristic, Vehicle Routing Problem with Drone
Main Article Content
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.
Article Details
How to Cite
Prawira, H. A., & Santosa, B. (2021). Development of Particle Swarm Optimization and Simulated Annealing Algorithms to Solve Vehicle Routing Problems with Drones. PROZIMA (Productivity, Optimization and Manufacturing System Engineering), 5(1), 1-12. https://doi.org/10.21070/prozima.v5i1.1398
Issue
Section
Articles
Copyright (c) 2021 PROZIMA (Productivity, Optimization and Manufacturing System Engineering)
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
[1] 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
[2] 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/
[3] 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/
[4] 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
[5] 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
[6] 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/
[7] Toth, P., & Vigo, D. (2002). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM - Society for Industrial and Applied Mathematics.
[8] 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
[9] 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
[10] Ponza, A. (2016). Optimization of Drone-Assisted Parcel Delivery. 80.
[11] 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
[12] 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
[13] 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
[14] Santosa, B., & Ai, T. J. (2017). Pengantar Metaheuristik - Implementasi dengan Matlab (1st ed.). Surabaya: ITS Tekno Sains.
[15] 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
[16] 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
[17] 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
[18] 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
[19] 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
[2] 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/
[3] 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/
[4] 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
[5] 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
[6] 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/
[7] Toth, P., & Vigo, D. (2002). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM - Society for Industrial and Applied Mathematics.
[8] 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
[9] 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
[10] Ponza, A. (2016). Optimization of Drone-Assisted Parcel Delivery. 80.
[11] 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
[12] 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
[13] 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
[14] Santosa, B., & Ai, T. J. (2017). Pengantar Metaheuristik - Implementasi dengan Matlab (1st ed.). Surabaya: ITS Tekno Sains.
[15] 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
[16] 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
[17] 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
[18] 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
[19] 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