#### Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem

Yıl: 2019 Cilt: 0 Sayı: 0 Sayfa Aralığı: 185 - 192 Metin Dili: İngilizce İndeks Tarihi: 22-09-2020

Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem

Öz:
Over the past few years, drones also known as unmanned aerial vehicles (UAV), have been adopted as a part of transportation activitiesin logistic sector. This paper investigates a new version of traveling salesman problem called as flying sidekick traveling salesmanproblem(FSTSP) in which trucks and drones serve the customers in coordination with the objective of minimizing the total deliverydistance of trucks at the depot after completing the deliveries. Clarke & Wright's savings algorithm is a well-known heuristics approachin literature, which gives better solution for classical vehicle routing problem. In this paper, a hybrid approach based on Clarke &Wright's savings algorithm and genetic algorithm is proposed for solving the new version of travelling salesman problem. In theproposed hybrid algorithm, which is the sequential use of genetic algorithm and Clarke & Wright’s savings algorithm, is used forassignment of the truck, drone or both of them to serve the customer. The solution of the genetic algorithm, which is the well-knownmetaheuristic approach, is enhanced with Clarke & Wright's savings algorithm. The aim of the problem is to minimize the total deliverydistance according to the assignment decisions. This is the first hybrid approach in the literature including Clarke & Wright’s savingsalgorithm and genetic algorithm that applies for FSTSP problem. The hypothetical experiments conducted on various instances andresults confirm the efficiency of the approach and give some insights on this drone delivery system.
Anahtar Kelime:

Clarke & Wright Tasarruf Algoritması ve Genetik Algoritmaya Dayalı Uçan Yardımcılı Gezgin Satıcı Problemi

Öz:
Son yıllarda, insansız hava aracı olarak da bilinen drone’lar lojistik sektöründeki ulaştırma faaliyetlerinin bir parçası olarak kabul edilmiştir. Bu çalışmada gezgin satıcı probleminin yeni bir versiyonu olan uçan yardımcılı gezgin satıcı problemine bir çözüm önerisi geliştirilmiştir. Çalışmanın amacı kamyon ve drone’ların koordineli bir şekilde kullanımı ile teslimat yaparak, teslimatlar tamamlanana kadar kamyon tarafından kat edilen toplam teslimat mesafesinin minimize edilmesidir. Clarke & Wright tasarruf algoritması literatürde sıklıkla kullanılan, klasik araç rotalama problemlerinde iyi sonuç veren sezgisel algoritmalardandır. Önerilen yaklaşım ile genetik algoritma ve Clarke & Wright tasarruf algoritmasının sıralı kullanımı ile drone, kamyon ya da her ikisinin eş zamanlı olarak müşterilere atanması amaçlanmaktadır. Clarke & Wright tasarruf algoritması sonuçları, iyi bilinen meta sezgisel algoritmalardan olan genetik algoritma ile iyileştirilmiştir. Bu problemin amacı atama kararlarına göre teslimat mesafesini en aza indirmektir. Bu çalışma Clarke & Wright tasarruf algoritması ve genetik algoritmanın uçan yardımcılı gezgin satıcı problemine uygulandığı ilk çalışmadır. Çeşitli örnek problem setleri üzerine yapılan hipotetik analizler yaklaşımın etkinliğini onaylamakta ve drone teslimat sistemine bir bakış açısı geliştirmektedir.
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
5
6
6
• [1]. Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization Approaches for the Traveling Salesman Problem with Drone Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, 52(4), 965–981.
• [2]. Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787–800. https://doi.org/10.1016/S0305-0548(02)00051-5
• [3]. Bouman, P., Agatz, N., & Schmidt, M. (2018). Dynamic programming approaches for the traveling salesman problem with drone, (October), 528–542. https://doi.org/10.1002/net.21864
• [4]. Boysen, N., Briskorn, D., Fedtke, S., & Schwerdfeger, S. (2018). Drone delivery from trucks: Drone scheduling for given truck routes. Networks, 72(4), 506–527. https://doi.org/10.1002/net.21847
• [5]. Caccetta, L., Alameen, M., & Abdul-Niby, M. (2013). An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem. Technology & Applied Science Research, 3(2), 413–415. https://doi.org/10.2306/scienceasia1513- 1874.2012.38.307
• [6]. Campbell, J. F., Sweeney, D., & Zhang, J. (2017). Strategic Design for Delivery with Trucks and Drones. Supply Chain Analytics Report SCMA (04 2017).
• [7]. Di, L., Pugliese, P., & Guerriero, F. (2017). Last-Mile Deliveries by Using Drones and Classical Vehicles. In International Conference on Optimization and Decision Science (pp. 557–565). https://doi.org/10.1007/978-3-319-67308-0
• [8]. Fan, S. S., Liang, Y., & Zahara, E. (2006). A genetic algorithm and a particle swarm optimizer hybridized with Nelder-Mead simplex search. Computers & Industrial Engineering, 50(4), 401–425. https://doi.org/10.1016/j.cie.2005.01.022
• [9]. Ferrandez, Sergio Mourelo Harbison, T., Weber, T., Sturges, R., & Rich, R. (2016). Optimization of a Truck-drone in Tandem Delivery Network Using K-means and Genetic Algorithm. Journal of Industrial Engineering and Management, 9(2), 374–388.
• [10]. 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, 86(November 2017), 597–621. https://doi.org/10.1016/j.trc.2017.11.015
• [11]. Huachi, P., & Penna, V. (2018). A Randomized Variable Neighborhood Descent Heuristic to Solve the Flying Sidekick Traveling Salesman Problem, 66, 95–102. https://doi.org/10.1016/j.endm.2018.03.013
• [12]. Jeong, H. Y., Lee, S., & Song, B. D. (2019). Truck-Drone Hybrid Delivery Routing: Payload-Energy dependency and No-Fly Zones. International Journal of Production Economics, 214, 220–233. https://doi.org/10.1016/j.ijpe.2019.01.010
• [13]. Kim, S., & Moon, I. (2018). Traveling Salesman Problem With a Drone Station. In IEEE Transactions on Systems, Man, and Cybernetics: Systems (Vol. 49, pp. 42–52).
• [14]. Kitjacharoenchai, P., Ventresca, M., Moshref-javadi, M., Lee, S., Tanchoco, J. M. A., Brunese, P. A., Engineering, I., Lafayette, W., & States, U. (2019). Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering, 129, 14–30. https://doi.org/10.1016/j.cie.2019.01.020
• [15]. Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem : Optimization of drone-assisted parcel delivery. TRANSPORTATION RESEARCH PART C, 54, 86–109. https://doi.org/10.1016/j.trc.2015.03.005
• [16]. Pichpibul, T., & Kawtummachai, R. (2012). New Enhancement for Clarke-Wright Savings Algorithm to Optimize the Capacitated Vehicle Routing Problem. European Journal of Scientific Research, 78(1), 119–134. Retrieved from https://www.researchgate.net/publication/267406368%0Ahttp://www.europeanjournalofscientificresearch.com
• [17]. Razali, N. M., & Geraghty, J. (2014). Genetic Algorithm Performance with Different Selection Strategies in Solving TSP. Proceedings of the World Congress on Engineering, 2(1), 1–6.
• [18]. Saleu, R. G. M., Grangeon, N., Deroussi, L., Feillet, D., & Quilliot, A. (2018). An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem. Networks, 72(4), 1–16. https://doi.org/10.1002/net.21846
• [19]. Yoon, J. J. (2018). The Traveling Salesman Problem with Multiple Drones: An Optimization Model for Last-Mile Delivery. (Doctoral Dissertation, Massachusetts Institute of Technology).
• [20]. Yurek, E. E., & Ozmutlu, H. C. (2018). A decomposition-based iterative optimization algorithm for traveling salesman problem with drone ☆. Transportation Research Part C, 91(July 2017), 249–262. https://doi.org/10.1016/j.trc.2018.04.009
 APA Ezici B, Cakmak E, KOÇ T (2019). Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. , 185 - 192. 10.31590/ejosat.637816 Chicago Ezici Busra,Cakmak Emre,KOÇ Tuğçe Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. (2019): 185 - 192. 10.31590/ejosat.637816 MLA Ezici Busra,Cakmak Emre,KOÇ Tuğçe Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. , 2019, ss.185 - 192. 10.31590/ejosat.637816 AMA Ezici B,Cakmak E,KOÇ T Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. . 2019; 185 - 192. 10.31590/ejosat.637816 Vancouver Ezici B,Cakmak E,KOÇ T Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. . 2019; 185 - 192. 10.31590/ejosat.637816 IEEE Ezici B,Cakmak E,KOÇ T "Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem." , ss.185 - 192, 2019. 10.31590/ejosat.637816 ISNAD Ezici, Busra vd. "Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem". (2019), 185-192. https://doi.org/10.31590/ejosat.637816
 APA Ezici B, Cakmak E, KOÇ T (2019). Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. Avrupa Bilim ve Teknoloji Dergisi, 0(0), 185 - 192. 10.31590/ejosat.637816 Chicago Ezici Busra,Cakmak Emre,KOÇ Tuğçe Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. Avrupa Bilim ve Teknoloji Dergisi 0, no.0 (2019): 185 - 192. 10.31590/ejosat.637816 MLA Ezici Busra,Cakmak Emre,KOÇ Tuğçe Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. Avrupa Bilim ve Teknoloji Dergisi, vol.0, no.0, 2019, ss.185 - 192. 10.31590/ejosat.637816 AMA Ezici B,Cakmak E,KOÇ T Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. Avrupa Bilim ve Teknoloji Dergisi. 2019; 0(0): 185 - 192. 10.31590/ejosat.637816 Vancouver Ezici B,Cakmak E,KOÇ T Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem. Avrupa Bilim ve Teknoloji Dergisi. 2019; 0(0): 185 - 192. 10.31590/ejosat.637816 IEEE Ezici B,Cakmak E,KOÇ T "Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem." Avrupa Bilim ve Teknoloji Dergisi, 0, ss.185 - 192, 2019. 10.31590/ejosat.637816 ISNAD Ezici, Busra vd. "Clarke & Wright's Savings Algorithm and Genetic Algorithms Based Hybrid Approach for Flying Sidekick Traveling Salesman Problem". Avrupa Bilim ve Teknoloji Dergisi 0 (2019), 185-192. https://doi.org/10.31590/ejosat.637816