A GREY WOLF OPTIMIZER ALGORITHM FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS AND SIMULTANEOUS PICK-UPS AND DELIVERIES

Yıl 2023, , 141 - 160, 31.08.2023

Milad Faramarzzadeh , Şener Akpınar

https://doi.org/10.46465/endustrimuhendisligi.1232511

Öz

The vehicle routing problem with time windows and simultaneous pick-ups and deliveries (VRPTWSPD) is one of the main distribution planning problems. VRPTWSPD aims to find the best distribution plan that minimizes the number of vehicle used and the total travelled distance. Due to the NP-Hard nature of the VRPTWSPD, practical large-scale instances cannot be solved to optimality within acceptable computational times. Therefore, it is necessary to develop approximation algorithms to tackle the VRPTWSPD as effectively as possible, as we try to do within the context of this study. Accordingly, a Grey Wolf Optimizer (GWO) algorithm is designed to solve the VRPTWSPD. The designed algorithm starts its search with a group of solutions constructed through the K-means algorithm. Additionally, the algorithm has been enhanced by incorporating the Variable Neighbourhood Search (VNS) algorithm as a local search algorithm. The performance evaluation tests of the developed GWO algorithm was done on the standard benchmark sets which is taken from the related literature. Computational results indicate that the proposed GWO algorithm has a satisfactory performance in solving VRPTWSPD instances.

Anahtar Kelimeler

Vehicle routing problem with pick-ups and deliveries and time windows, Grey Wolf Optimizer algorithm, K-means algorithm, Variable Neighbourhood Search algorithm

ZAMAN PENCERELI VE TOPLAMALI VE DAĞITIMLI ARAÇ ROTALAMA PROBLEMI IÇIN BIR GRI KURT OPTIMIZASYON ALGORITMASI

Öz

Zaman pencereli ve toplamalı ve dağıtımlı araç rotalama problemi (ZPTDARP) ana dağıtım planlama problemlerinden biridir. ZPTDARP, kullanılan araç sayısını ve toplam seyahat mesafesini en aza indiren en iyi dağıtım planını bulmayı amaçlar. ZPTDARP’nin NP-Zor doğası nedeniyle, pratik büyük ölçekli örnekler, kabul edilebilir hesaplama süreleri içinde optimal olarak çözülemezler. Bu nedenle, bu çalışma kapsamında yapmaya çalıştığımız gibi, ZPTDARP’yi mümkün olduğunca etkin bir şekilde çözmek için yaklaşım algoritmaları geliştirmek gerekmektedir. Buna göre, ZPTDARP’yi çözmek için bir Gri Kurt Optimizasyon (GKO) algoritması tasarlanmıştır. Tasarlanan algoritma, aramaya K-ortalamalar algoritması aracılığıyla oluşturulan bir grup çözümle başlar. Ayrıca, yerel bir arama algoritması olarak Değişken Komşuluk Arama (DKAS) algoritması dahil edilerek algoritma geliştirilmiştir. Geliştirilen Gri Kurt Optimizasyon algoritmasının performans değerlendirme testleri, ilgili literatürden alınan standart kıyaslama setleri üzerinde yapılmıştır. Hesaplamalı sonuçlar, önerilen GKO algoritmasının ZPTDARP örneklerini çözmede tatmin edici bir performansa sahip olduğunu göstermektedir.

Anahtar Kelimeler

Zaman pencereli ve toplamalı ve dağıtımlı araç rotalama problemi, gri kurt optimizasyon algoritması, k-ortalamalar algoritması, değişken komşuluk arama algoritması

Kaynakça

• Angelelli, E., & Mansini, R. (2002). The vehicle routing problem with time windows and simultaneous pick-up and delivery. In Quantitative approaches to distribution logistics and supply chain management (pp. 249-267). Springer, Berlin, Heidelberg. Doi: https://doi.org/10.1007/978-3-642-56183-2_15
• Angelelli, E., & Mansini, R. (2003). A branch-and-price algorithm for a simultaneous pick-up and delivery problem. In Quantitative approaches to distribution logistics and supply chain management (pp. 249-267). Springer, Berlin, Heidelberg. Retrieved from: https://www.academia.edu/es/29065016/A_Branch_and_Price_Algorithm_for_a_Simultaneous_Pick_up_and_Delivery_Problem.
• Barbosa, N. D. P., Christo, E. D. S., & Costa, K. A. (2015). Demand forecasting for production planning in a food company. ARPN Journal of Engineering and Applied Sciences, 10(16), 7137-7141. Retrieved from: http://www.arpnjournals.com/jeas/research_papers/rp_2015/jeas_0915_2531.pdf.
• Boubahri, L., Addouche, S. A., & El Mhamedi, A. (2011, March). Multi-ant colonies algorithms for the VRPSPDTW. In 2011 International Conference on Communications, Computing and Control Applications (CCCA) (pp. 1-6). IEEE. Doi: https://doi.org/10.1109/CCCA.2011.6031488.
• Cao, E., & Lai, M. (2007, August). An improved differential evolution algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. In Third international conference on natural computation (ICNC 2007) (Vol. 3, pp. 436-440). IEEE. Doi: https://doi.org/10.1109/ICNC.2007.209
• Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey wolf optimizer: a review of recent variants and applications. Neural Computing and Applications, 30, 413-435. Doi: https://doi.org/10.1007/s00521-017-3272-5.
• Hansen, P., & Mladenović, N. (2003). Variable neighborhood search. In Handbook of metaheuristics (pp. 145-184). Springer, Boston, MA. Doi: https://doi.org/10.1007/978-3-319-91086-4_3.
• Hansen, P., Mladenović, N., & Moreno Pérez, J. A. (2010). Variable neighbourhood search: methods and applications. Annals of Operations Research, 175, 367-407. Doi: https://doi.org/10.1007/s10479-009-0657-6.
• Hof, J., & Schneider, M. (2019). An adaptive large neighborhood search with path relinking for a class of vehicle‐routing problems with simultaneous pickup and delivery. Networks, 74(3), 207-250. Doi: https://doi.org/10.1002/net.21879.
• Kapil, S., Chawla, M., & Ansari, M. D. (2016, December). On K-means data clustering algorithm with genetic algorithm. In 2016 Fourth International Conference on Parallel, Distributed and Grid Computing (PDGC) (pp. 202-206). IEEE. Doi: https://doi.org/10.1109/PDGC.2016.7913145.
• Korayem, L., Khorsid, M., & Kassem, S. S. (2015, May). Using grey wolf algorithm to solve the capacitated vehicle routing problem. In IOP conference series: materials science and engineering (Vol. 83, No. 1, p. 012014). IOP Publishing. Doi: https://doi.org/10.1088/1757-899X/83/1/012014.
• Li, S., & Wang, F. (2020). Research on Optimization of Improved Gray Wolf Optimization-Extreme Learning Machine Algorithm in Vehicle Route Planning. Discrete Dynamics in Nature and Society, 2020, Article ID 8647820, 7 pages,. Doi: https://doi.org/10.1155/2020/8647820.
• MacQueen, J. (1967, June). Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability (Vol. 1, No. 14, pp. 281-297). Retrieved from: https://digitalassets.lib.berkeley.edu/math/ucb/text/math_s5_v1_ article-17.pdf.
• Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46-61. Doi: https://doi.org/10.1016/ j.advengsoft.2013.12.007.
• Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002. Doi: https://doi.org/10.1016/S0305-0548(03)00158-8 .
• Semet, F., Toth, P., & Vigo, D. (2014). Classical exact algorithms for the capacitated vehicle routing problem. Vehicle routing: problems, methods, and applications, 37–57. Doi: https://doi.org/10.1137/1.9781611973594.ch2.
• Shi, Y., Boudouh, T., & Grunder, O. (2018). An efficient tabu search based procedure for simultaneous delivery and pick-up problem with time window. IFAC-PapersOnLine, 51(11), 241-246. Doi: https://doi.org/10.1016/j.ifacol.2018.08.278.
• Shi, Y., Zhou, Y., Boudouh, T., & Grunder, O. (2020). A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup–delivery and time window. Engineering Applications of Artificial Intelligence, 95, 103901. Doi: https://doi.org/10.1016/j.engappai.2020.103901.
• Subramanian, A., Uchoa, E., & Ochi, L. S. (2010, May). New lower bounds for the vehicle routing problem with simultaneous pickup and delivery. In International Symposium on Experimental Algorithms (pp. 276-287). Springer, Berlin, Heidelberg. Doi: https://doi.org/10.1007/978-3-642-13193-6_24.
• Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J. Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2), 170-186. Doi: https://doi.org/10.1287/trsc.31.2.170.
• Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111-122. Doi: https://doi.org/10.1016/j.cie.2015.02.005.
• Wang, H. F., & Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 62(1), 84-95. Doi: https://doi.org/10.1016/j.cie.2011.08.018.