Experimental Analysis of Meta-Heuristic Algorithms for Moving Customer Vehicle Routing Problem

Öz

Unmanned Combat Aerial Vehicles are defense systems based on artificial intelligence which is intensively used by many countries to provide national security on military operations. By means of these systems, moving or non-moving threat factors in the operation field could be destroyed under harsh and challenging geographical conditions without requiring a pilot with the help of a control center. In fleet operations, the necessity of destroying moving targets successfully under constraints of the endurance, munition capacity, time window and fuel cost of unmanned combat aerial vehicles brings out the moving customer-vehicle routing problem. In this study, Heterogeneous Fleet-Moving Customer Vehicle Routing Problem with Time Windows under constraint of vehicle capacity (endurance) has been aimed to be solved considering the minimum operation time and cost. In order to solve the problem, heuristic algorithms (ÇARA, RASA)   were developed and metaheuristic algorithms (Genetic Algorithm, NSGA-II and Simulated Annealing) were used. The effectiveness of the proposed algorithms was tested on 30 different experimental sets with the number of pursuers ranging from 5-10 and the number of targets ranging from 10-35. Taguchi method was used to determine the appropriate parameter set for the algorithms. As a result of the analysis, it has been found that Genetic Algorithm produces much better results than other algorithms.

Anahtar Kelimeler

• Moving Customer Vehicle Routing Problem,Simulated Annealing,Pareto Optimization,Genetic Algorithm,NSGA-II

Hareketli müşterili araç rotalama problemi için Meta-Sezgisel algoritmaların deneysel analizi

Öz

Silahlı İnsansız Hava Araçları, birçok ülkenin ulusal güvenliğini sağlamak adına askeri operasyonlarda yoğun bir şekilde kullandıkları yapay zekâya dayalı savunma sistemleridir. Bu sistemler sayesinde operasyon alanındaki hareketli ve hareketsiz hedefler, zorlu coğrafik koşullar altında pilot kullanılmaksızın kumanda merkezi yardımıyla imha edilebilmektedir. İnsansız hava aracı filosu tarafından, seyir süresi, mühimmat kapasitesi, yakıt maliyeti ve zaman penceresi kısıtlamaları dikkate alınarak sistemdeki hareketli hedeflerin başarılı bir şekilde imha edilmesi gereksinimi, Hareketli Müşterili Araç Rotalama Problemini ortaya çıkarmaktadır. Bu çalışmada Heterojen Filolu-Zaman Pencereli-Kapasite Kısıtlı Hareketli Müşterili Araç Rotalama Problemi, minimum görev süresi ve görev maliyeti amaçları doğrultusunda çözülmesi amaçlanmıştır. Problemin çözümü için sezgisel algoritmalar(ÇARA, RASA)  geliştirilmiş ve metasezgisel algoritmalar (Genetik Algoritma, NSGA-II ve Tavlama Benzetimi Algoritması) kullanılmıştır. Önerilen algoritmaların etkinliği vurucu sayısının 5-10, hedef sayısının 10-35 arasında değiştiği 30 farklı deney seti üzerinde test edilmiştir. Algoritmalar için uygun parametre setinin belirlenmesinde Taguchi yönteminden yararlanılmıştır. Analiz sonucunda Genetik Algoritmanın diğer algoritmalara kıyasla daha başarılı sonuçlar ürettiği tespit edilmiştir.

Anahtar Kelimeler

• Hareketli müşterili araç rotalama problemi,Tavlama Benzetimi,Pareto Optimizasyonu,Genetik Algoritma,NSGA-II

Kaynakça

1. [1]. Psaraftis, H. N., Dynamic vehicle routing: status and prospects, Annals Of Operations Research, 61(1), 143-164, 1995.
2. [2]. Bertsimas, D. J., Van Ryzin, G., A stochastic and dynamic vehicle routing problem in the Euclidean plane, Operations Research, 39(4), 601-615, 1991.
3. [3]. Bertsimas, D. J., Van Ryzin, G., Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles, Operations Research, 41(1), 60-76, 1993.
4. [4]. Liao, T. Y., On‐line vehicle routing problems for carbon emissions reduction, Computer‐Aided Civil and Infrastructure Engineering, 2017.
5. [5]. Haghani, A., Jung, S., A dynamic vehicle routing problem with time-dependent travel times, Computers & operations research, 32(11), 2959-2986, 2005.
6. [6]. Novoa, C., Storer, R., An approximate dynamic programming approach for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 196(2), 509-515, 2009.
7. [7]. Haghani, A., Jung, S., A dynamic vehicle routing problem with time-dependent travel times, Computers & operations research, 32(11), 2959-2986, 2005.
8. [8]. Potvin, J. Y., Xu, Y., Benyahia, I., Vehicle routing and scheduling with dynamic travel times, Computers & Operations Research, 33(4), 1129-1137, 2006.

9. [9]. Van Woensel, T., Kerbache, L., Peremans, H., Vandaele, N., Vehicle routing with dynamic travel times: A queueing approach, European Journal of Operational Research, 186(3), 990-1007, 2008.
10. [10]. Taniguchi, E., Shimamoto, H., Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times, Transportation Research Part C: Emerging Technologies, 12(3-4), 235-250, 2004.
11. [11]. Ning, T., Guo, C., Chen, R., A novel method for dynamic vehicle routing problem, The Open Cybernetics & Systemics Journal, 9(1), 2015.
12. [12]. Chen, S., Chen, R., Gao, J., A Monarch Butterfly Optimization for the Dynamic Vehicle Routing Problem, Algorithms, 10(3), 107, 2017.
13. [13]. Kilby, P., Prosser, P., Shaw, P., Dynamic VRPs: A study of scenarios, University of Strathclyde Technical Report, 1-11, 1998.
14. [14] Ritzinger, U., Puchinger, J., Hartl, R. F. A survey on dynamic and stochastic vehicle routing problems, International Journal of Production Research, 54(1), 215-231, 2016.
15. [15]. Ries, J., Ishizaka, A., A Multi-Criteria Support System for Dynamic Aerial Vehicle Routing Problems, In Communications, Computing and Control Applications (CCCA), 2012 2nd International Conference on (pp. 1-4). IEEE, December, 2012.
16. [16]. Karakaya, M. En Az Sayıda İnsansız Hava Aracı Kullanarak Sabit Hedeflerin Gözetlenmesinin Planlanması. https://docplayer.biz.tr/4654060-En-az-sayida-insansiz-hava-araci-kullanarak-sabit-hedeflerin-gozetlenmesinin-planlanmasi.html Erişim tarihi Ağustos 9, 2019.
17. [17]. Innocenti, M., Pollini, L., Turra, D., A fuzzy approach to the guidance of unmanned air vehicles tracking moving targets. IEEE Transactions on Control Systems Technology, 16(6), 1125-1137, 2008.
18. [18]. Morris, S., Frew, E. W., Jones, H., Cooperative tracking of moving targets by teams of autonomous unmanned air vehicles, MLB CO MOUNTAIN VIEW CA, 2005.
19. [19]. Ramirez-Atencia, C., Bello-Orgaz, G., R-Moreno, M. D., Camacho, D., Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms, Soft Computing, 21(17), 4883-4900, 2017.
20. [20]. Savuran, H., & Karakaya, M., Efficient route planning for an unmanned air vehicle deployed on a moving carrier, Soft Computing, 20(7), 2905-2920, 2016.
21. [21]. Shima, T., Schumacher, C., Assignment of Cooperating UAVs to Simultaneous Tasks using Genetic Algorithms, In AIAA Guidance, Navigation, and Control Conference and Exhibit (p. 5829), (2005, August)..
22. [22]. Kim, J., Morrison, J. R., On the concerted design and scheduling of multiple resources for persistent UAV operations, Journal of Intelligent & Robotic Systems, 74(1-2), 479-498, 2014.
23. [23]. Helvig, C. S., Robins, G., & Zelikovsky, A., Moving-target TSP and related problems, In European Symposium on Algorithms (pp. 453-464), Springer Berlin Heidelberg, (1998, August).
24. [24]. Fügenschuh, A., Knapp, M., Rothe, H., The multiple traveling salesmen problem with moving targets. Helmut-Schmidt-Univ., Professur für Angewandte Mathematik, 2014.
25. [25]. Stieber, A., Fügenschuh, A., Epp, M., Knapp, M., & Rothe, H., The multiple traveling salesmen problem with moving targets, Optimization Letters, 9(8), 1569-1583, 2015.
26. [26]. Stieber, A., Fügenschuh, A., Variants in Modeling Time Aspects for the Multiple Traveling Salesmen Problem with Moving Targets, 2016.
27. [27]. Jiang, Q., Sarker, R., Abbass, H., Tracking moving targets and the non-stationary traveling salesman problem, Complexity International, 11(2005), 171-179, 2005.
28. [28]. Jindal, P., Kumar, A., Multiple Target Intercepting Traveling Salesman Problem, International Journal of Computer Science and Technology, 2(2), 327-331, 2011.
29. [29]. Englot, B., Sahai, T., Cohen, I., Efficient Tracking and Pursuit of Moving Targets by Heuristic Solution of the Traveling Salesman Problem, In Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on (pp. 3433-3438). IEEE, December, 2013.
30. [30]. Jindal, P., Kumar, A., Kumar, S., Dynamic version of Traveling Salesman Problem, International Journal of Computer Applications (0975–8887), 19(1), 2011.
31. [31]. Khosravi, M., Aghdam, A. G., Cooperative Receding Horizon Control for Multi-Target İnterception in Uncertain Environments, In Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on (pp. 4497-4502). IEEE, December, 2014.
32. [32]. Zhou, A., Kang, L., Yan, Z. Solving Dynamic TSP with Evolutionary Approach in Real Time, In Evolutionary Computation, 2003. CEC'03. The 2003 Congress on (Vol. 2, pp. 951-957). IEEE, December, 2013.
33. [33]. Choubey, N. S., Moving Target Travelling Salesman Problem using genetic algorithm, International Journal of Computer Applications, 70(2), 2013.
34. [34]. Lee, Z. J., Lee, C. Y., Su, S. F., An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem Applied Soft Computing, 2(1), 39-47, 2002.
35. [35]. Agharkar, P., Bullo, F., Vehicle routing algorithms to intercept escaping targets. In American Control Conference (ACC), 2014 (pp. 952-957). IEEE, June, 2014.
36. [36]. Knapp, M., Rothe, H., Concept for simulating engagement strategies for C-RAM systems using laser weapons. Proceedings of the DMMS, 2012.
37. [37]. Hammar, M., Nilsson, B. J., Approximation results for kinetic variants of TSP, In International Colloquium on Automata, Languages, and Programming (pp. 392-401). Springer Berlin Heidelberg, (1999, July).
38. [38]. Bengt, J., Approximation Results for Kinetic Variants of TSP, Discrete & Computational Geometry, 4(27), (2002).
39. [39]. Bourjolly, J. M., Gurtuna, O., Lyngvi, A., On‐orbit servicing: a time‐dependent, moving‐target traveling salesman problem, International Transactions in Operational Research, 13(5), 461-481, 2006.
40. [40]. Blough, O. P., Farrington, T. K., Hudson, J., Trojan Asteroid Mission Design: Target Selection And Sequencing Optimization, 2016.
41. [41]. Mei, G., Ran, X., Fang, D., & Zhang, C. (2015), Improved Satellite Scheduling Algorithm for Moving Target, In Proceedings of The fourth International Conference on Information Science and Cloud Computing (ISCC2015). 18-19 December, 2015. Guangzhou, China. Online at http://pos. sissa. it/cgi-bin/reader/conf. cgi? confid= 264, id. 58.
42. [42]. Groba, C., Sartal, A., Vázquez, X. H., Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices, Computers & Operations Research, 56, 22-32, 2015.
43. [43]. Mercer, G., Barry, S. I., Marlow, D. O., Kilby, P., Investigating the effect of detection and classification range and aircraft dynamics on a, ANZIAM Journal, 49, 475-492, 2008.
44. [44]. Kilby, P., Tobin, P., Luscombe, R., Barry, S. I., Hickson, R., The maritime surveillance problem, 2007.
45. [45]. Marlow, D. O., Kilby, P., & Mercer, G. N., The Travelling Salesman Problem in Maritime Surveillance–Techniques, Algorithms and Analysis, In Proceedings of the International Congress on Modelling and Simulation (pp. 684-690), December, 2007.
46. [46]. Fang, F., Jiang, A. X., Tambe, M., Protecting moving targets with multiple mobile resources, Journal of Artificial Intelligence Research, 48, 583-634, 2013.
47. [47]. Cross, M., Marlow, D., Looker, J. Application of the non-stationary travelling salesman problem to maritime Surveillance, Proceedings of MISG, 1-4, 2007.
48. [48]. Shuttleworth, R., Golden, B. L., Smith, S., Wasil, E., Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network, In The Vehicle Routing Problem: Latest Advances and New Challenges (pp. 487-501). Springer US, 2008.
49. [49]. Del Bimbo, A., & Pernici, F., Distant targets identification as an on-line dynamic vehicle routing problem using an active-zooming camera. In Visual Surveillance and Performance Evaluation of Tracking and Surveillance, 2005. 2nd Joint IEEE International Workshop on (pp. 97-104). IEEE, October, 2005.
50. [50]. Bimbo, A. D., & Pernici, F., Saccades Planning with Kinetic TSP for Distant Targets İdentification, In Imaging for Crime Detection and Prevention, 2005. ICDP 2005. The IEE International Symposium on (pp. 145-149). IET, June, 2005.
51. [51]. Ilavarasi, K., & Joseph, K. S., Variants of travelling salesman problem: A survey. In Information Communication and Embedded Systems (ICICES), 2014 International Conference on (pp. 1-7). IEEE, February, 2004.
52. [52]. Asahiro, Y., Horiyama, T., Makino, K., Ono, H., Sakuma, T., Yamashita, M, How to collect balls moving in the Euclidean plane, Electronic Notes in Theoretical Computer Science, 91, 229-245, 2004.
53. [53]. Asahiro, Y., Miyano, E., Shimoirisa, S., Grasp and delivery for moving objects on broken lines, Theory of Computing Systems, 42(3), 289-305, 2008.
54. [54]. Chalasani, P., Motwani, R., Rao, A. N. I. L., Algorithms for robot grasp and delivery, In 2nd International Workshop on Algorithmic Foundations of Robotics, (1996, July).
55. [55]. Uçar, U , İşleyen, S., A New Solution Approach for UAV Routing Problem with Moving Target – Heterogeneous Fleet. Journal of Polytechnic, (), 0-0, 2019. DOI: 10.2339/politeknik.466393
56. [56]. Uçar, U.Ü., Işleyen, S.K., A solution approach based on simulated annealing for the destruction of moving targets in time window by air operations, 8th InternationalAdvanced Technologies Symposium(IATS) 19-22 October 2017.
57. [57]. Isleyen, S. K., Uçar, U., Balo, F., A New Solution Approach for Maritime Surveillance Operation: The Case of Aegean Sea, Mathematical Problems in Engineering. 2019, 1-16, 2019.
58. [58]. Papadakos, N., Tzallas-Regas, G., Rustem, B., Thoms, J., Risky traveling salesman problem. European Journal of Operational Research, 212(1), 69-73, 2011.
59. [59]. Bullo, F., Frazzoli, E., Pavone, M., Savla, K., & Smith, S. L., Dynamic Vehicle Routing for Robotic Systems. Proceedings of the IEEE, 99(9), 1482-1504, 2011.
60. [60]. Ries, J., & Ishizaka, A., A multi-criteria support system for dynamic aerial vehicle routing problems. In Communications, Computing and Control Applications (CCCA), 2012 2nd International Conference on (pp. 1-4). IEEE, December, 2012.
61. [61]. Enright, J., Frazzoli, E., Savla, K., & Bullo, F., On multiple UAV routing with stochastic targets: Performance bounds and algorithms. In AIAA Guidance, Navigation, and Control Conference and Exhibit (p. 5830), August, 2005.
62. [62]. Karakaya, M., A local optimization technique for assigning new targets to the planned routes of unmanned aerial vehicles, Balkan Journal of Electrical and Computer Engineering, 2(2), 2014.
63. [63]. Ercan, C., & Gencer, C., Dinamik insansız hava sistemleri rota planlaması literatür araştırması ve insansız hava araçları çalışma alanları, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 19(2), 104-111, 2013.
64. [64]. Psaraftis, H. N., Wen, M., Kontovas, C. A., Dynamic vehicle routing problems: Three decades and counting, Networks, 67(1), 3-31, 2016.
65. [65]. Murray, C. C., Karwan, M. H., An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations, Naval Research Logistics (NRL), 57(7), 634-652, 2010.
66. [66]. O'Rourke, K. P., Dynamic unmanned aerial vehicle (UAV) routing with a Java-encoded reactive tabu search metaheuristic (No. AFIT/GOA/ENS/99M-06). Aır Force Inst Of Tech Wrıght-Pattersonafb Oh School Of Engıneerıng, 1999.
67. [67]. Murray, C. C., Dynamic reassignment and rerouting in cooperative airborne operations, State University of New York at Buffalo, 2010.
68. [68]. Mufalli, F., Batta, R., Nagi, R., Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans, Computers & Operations Research, 39(11), 2787-2799, 2012.
69. [69]. Scioletti, M. S., A heuristic algorithm for optimized routing of unmanned aerial systems for the interdiction of improvised explosive devices (Doctoral dissertation, Monterey, California. Naval Postgraduate School), 2008.
70. [70]. Vidal, R., Rashid, S., Sharp, C., Shakernia, O., Kim, J., & Sastry, S., Pursuit-evasion games with unmanned ground and aerial vehicles. In Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE International Conference on (Vol. 3, pp. 2948-2955). IEEE, 2001.
71. [71]. Pavone, M., Bisnik, N., Frazzoli, E., Isler, V., A stochastic and dynamic vehicle routing problem with time windows and customer impatience. Mobile Networks and Applications, 14(3), 350, 2009.
72. [72]. Groba, C., Sartal, A., Vázquez, X. H., Integrating forecasting in metaheuristic methods to solve dynamic routing problems: Evidence from the logistic processes of tuna vessels, Engineering Applications of Artificial Intelligence, 76, 55-66, 2018.
73. [73]. Holland, J. H., Adaption in natural and artificial systems. An Introductory Analysis with Application to Biology, Control and Artificial Intelligence, 1975.
74. [74]. Şahin, M., Kellegöz, T., An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate, Memetic Computing, 9(3), 213-229, 2017.
75. [75]. Gözütok, S., Özdemir, O. N., Refinement of hydraulic calibration for water supply networks with genetic algorithms, Journal of the Faculty of Engineering and Architecture of Gazi University, 19(2), 2004.
76. [76]. Temiz, İ., Erol, S., Multıobjectıve genetıc algorıthm for fuzzy flowshop schedulıng problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 22(4), 2007.
77. [77]. Lokman, B., Çok amaçlı tamsayı programlama problemleri için temsili çözüm üreten yaklaşımların ve kalite ölçülerinin incelenmesi, Journal of Industrial Engineering (Turkish Chamber of Mechanical Engineers), 28(1), 2017.
78. [78]. Durmaz, E. D., Çok amaçlı tek sıra tesis düzenleme probleminin çözümü için NSGA II ve hedef programlama yaklaşımı, Yüksek Lisans Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, 2016.
79. [79]. Sağ, T., Çok kriterli optimizasyon için genetik algoritma yaklaşımları, Yüksek Lisans Tezi, Selçuk Üniversitesi, Fen Bilimleri Enstitüsü, (2018).
80. [80]. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. A. M. T., A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197, 2002.
81. [81]. Mafarja, M. M., Mirjalili, S., Hybrid Whale Optimization Algorithm with simulated annealing for feature selection, Neurocomputing, 2017.
82. [82]. Ingber, L., Simulated annealing: Practice versus theory, Mathematical and Computer Modelling, 18(11), 29-57, 1993.
83. [83]. Talbi, El-Ghazali, Metaheuristics: From Design to İmplementation. John Wiley & Sons, 2009.