Tektürel zaman pencereli araç rotalama problemi için eniyilenmiş altın oran sarmalı başlangıç çözümlü uyarlanmış büyük komşuluk arama algoritması

Yıl 2024, Cilt: 39 Sayı: 2, 797 - 810, 30.11.2023

Alperen Ekrem Çelikdin

https://doi.org/10.17341/gazimmfd.1120447

Öz

Zaman pencereli tektürel sığalı araç rotalama problemlerinde, müşteri taleplerini zamanında ve en düşük maliyetle karşılamak amaçlanmaktadır. NP-Zor olarak tanımlanan bu problem tipinde optimal çözümü bulmak her zaman mümkün olmadığından sezgisel yöntemlerle en makul çözüm aranmaktadır. Uygulama kolaylığı ve çeşitli yerel arama araçları nedeniyle sıklıkla tercih edilen bu buluşsal çözümlerden biri de büyük komşuluk arama algoritmasıdır.
Genellikle müşterilerin araçlara ilk ataması rastlantısal yapılır ve ardından yerel arama operatörleri ile iyileştirmeler sağlanır. Çağın ihtiyaçlarına bağlı olarak karmaşıklık düzeyi arttıkça, komşuluk yerel arama alanının belirli bir algoritmaya göre başlatılması çözüm hızını ve kalitesini artırmada önem taşımaktadır. Belirtilen sebeplerle, bu çalışma ile daha çok mimarlık ve sanatsal alanda kullanımıyla daha sık karşılaşılan altın oran yaklaşımı yenilikçi bir buluşsal yönteme eklenerek ARP alan yazınına katkıda bulunmak amaçlandı. Altın oran sarmalının müşterilere en yakın noktalardan dönüş yapacak şekilde eniyilenmiş sarmalı ile ilk çözümün başlatıldığı bir uyarlama yapıldı. Müşterilerin araçlara ilk ataması, bu yenilikçi yöntemde kümeleme ile başlamaktadır ve güzergahlar yerel arama operatörleri tarafından iyileştirilmektedir. Bu uyarlama ile alan yazında sıklıkla tercih edilen Solomon test problemlerinin en iyi bilinen sonuçlarında %6,53 e varan önemli iyileşmeler sağlanmıştır.

Anahtar Kelimeler

Zaman pencereli araç rotalama problemi, eniyilenmiş altın oran sarmalı kümelemesi, uyarlanmış büyük komşuluk arama, sezgisel algoritma

Kaynakça

• J.H. Dantzig, G. B., and Ramser, The truck dispatching problem, Manage. Sci. 80–91, 1959.
• G. Laporte, Fifty years of vehicle routing, Transp. Sci. 43, 408–416, 2009.
• X. Huang, B. Cao, Research on contract logistics mathematical model and system based on Lindo and Baidu map, Adv. Mater. Res. 452–453, 894–899, 2012.
• Ş.T. Yildiz, B. Çiçekdeş, A Genetic Algorithm Approach for a Real Life Fleet Size and Mix Vehicle Routing Problem : A Case Study in an Automotive Company, 5, 29–46, 2019.
• O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, T. Monteiro, The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity To cite this version : HAL Id : hal-01619103 The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity, 2017.
• I. Rodríguez-Martín, J.J. Salazar-González, H. Yaman, The periodic vehicle routing problem with driver consistency, Eur. J. Oper. Res. 273, 575–584, 2019.
• H. Küçükaydın, Column generation based matheuristics for a vehicle routing problem with time windows and variable start time, Journal of the Faculty of Engineering and Architecture of Gazi University, 34, 2061–2078, 2019.
• D. Zhang, S. Cai, F. Ye, Y.W. Si, T.T. Nguyen, A hybrid algorithm for a vehicle routing problem with realistic constraints, Inf. Sci. (Ny). 394–395, 167–182, 2017.
• R. Liu, Z. Jiang, A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints, Appl. Soft Comput. J. 80, 18–30, 2019.
• Y. Kuo, Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem, Comput. Ind. Eng. 59, 157–165, 2010.
• Ç.K. Karaoğlan, A mathematical model for the time-dependent vehicle routing problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 29, 549–558, 2014.
• A.H.G. Lenstra, J. K.; Rinnooy Kan, Complexity of Vehicle Routing and Scheduling Problems, Networks. 11, 221–227, 1979.
• P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 1520, 417–431, 1998.
• S. Ropke, D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci. 40, 455–472, 2006.
• J.Y. Potvin, J.M. Rousseau, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, Eur. J. Oper. Res. 66, 331–340, 1993.
• C.E. Miller, R.A. Zemlin, A.W. Tucker, Integer Programming Formulation of Traveling Salesman Problems, J. ACM. 7, 1960.
• T. College, M. Journal, Misconceptions about the Golden Ratio Author ( s ): George Markowsky Source : The College Mathematics Journal , Vol . 23 , No . 1 ( Jan ., 1992 ), pp . 2-19 Published by : Mathematical Association of America Stable URL : http://www.jstor.org/stable/268619, 23 2–19, 2010.
• B. Keçeci, F. Altiparmak, İ. Kara, heterogeneous vehicle routing problem with simultaneous pickup and delivery: mathematical formulations and a heuristic algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 30 (2), 185–195, 2015.
• M. Demir, Sezgisel yöntemlerde altın oran, Doktora Tezi, İnönü Üniversitesi, Fen Bilimleri Enstitüsü, Malatya, 2015.
• M.M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problems With Time Window Constraints., Oper. Res. 35, 254–265, 1987.
• R. Bent, P. Van Hentenryck, A two-stage hybrid local search for the vehicle routing problem with time windows, Transp. Sci. 38, 515–530, 2004.
• M. Chen, L. Gao, Q. Chen, Z. Liu, Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search, 1–10, 19 Mayıs 2020, http://arxiv.org/abs/2005.09330 adresinden 19 Mayıs 2022 tarihinde erişildi.
• O.M. Gonzalez, C. Segura, S.I.V. Pena, C. Leon, A memetic algorithm for the Capacitated Vehicle Routing Problem with Time Windows, in: 2017 IEEE Congr. Evol. Comput. CEC 2017 - Proc., 2582–2589, 2017.
• N.A. Kyriakakis, M. Marinaki, Y. Marinakis, A hybrid ant colony optimization-variable neighborhood descent approach for the cumulative capacitated vehicle routing problem, Comput. Oper. Res. 134, 105397, 2021.
• X. Song, D. Jones, N. Asgari, T. Pigden, Multi-objective vehicle routing and loading with time window constraints: a real-life application, Ann. Oper. Res. 291, 799–825, 2020.
• C. Groër, B. Golden, E. Wasil, A library of local search heuristics for the vehicle routing problem, Math. Program. Comput. 2, 79–101, 2010.
• D. Rezgui, J. Chaouachi Siala, W. Aggoune-Mtalaa, H. Bouziri, Application of a variable neighborhood search algorithm to a fleet size and mix vehicle routing problem with electric modular vehicles, Comput. Ind. Eng. 130, 537–550, 2019.
• A. Hoff, H. Andersson, M. Christiansen, G. Hasle, A. Løkketangen, Industrial aspects and literature survey: Fleet composition and routing, Comput. Oper. Res. 37, 2041–2061, 2010.