Zaman pencereli araç rotalama problemi çözümü için çok amaçlı genetik algoritma yaklaşımı

Bu çalışmada, talepleri bilinen müşterilerin, konumu bilinen bir deponun ve belirli sayıda aynı kapasiteye ve özelliklere sahip özdeş araçların bulunduğu klasik Araç Rotalama Probleminin (ARP) bir çeşidi olan Zaman Pencereli Araç Rotalama Problemi (ZPARP) ele alınmıştır. Müşterilere belirli bir zaman aralığında hizmet verilebilen ZPARP için toplam yolu ve araç sayısını minimize etmek amaç fonksiyonları olarak belirlenmiştir. ZPARP’ye etkin çözümler üretilmesi amacı ile meta-sezgisel bir yöntem olan genetik algoritmanın sezgisel metotlarla melezleştirilmiş bir uyarlaması önerilmiştir. Genetik algoritmanın başlangıç popülasyonu oluşturma aşamasında süpürme algoritması ve en yakın komşu tabanlı bir algoritma kullanılarak üretilen kaliteli çözüm kümeleriyle aramaya başlaması, böylece optimum sonuçlara daha hızlı ulaşması planlanmıştır. Genetik algoritmada başlangıç popülasyonları oluşturmada farklı sezgisel yöntemlerin kullanılmasının istenilen sonuca bir etkisi olup olmadığı test edilmiştir. Literatürde var olan bir veri problemi çözülmüş, süpürme algoritmasını kullanan genetik algoritma ile daha etkin sonuçlara ulaşıldığı görülmüştür.

Anahtar Kelimeler:

Araç rotalama, çok-amaçlı optimizasyon, genetik algoritma, NSGA-II

PDF

___

J. K. Lenstra, A. H. G. Kan, Complexity of vehicle routing and scheduling problems. Networks, 11:2 (1981) 221-227.
S. Çolak, H. Güler, Dağıtım rotaları optimizasyonu için meta sezgisel bir yaklaşım. Gazi Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 11 (2009) 171-189.
Y. Şahin, A. Eroğlu, Kapasite kısıtlı araç rotalama problemi için metasezgisel yöntemler: Bilimsel yazın taraması. Süleyman Demirel Üniversitesi İ.İ.B.F. Dergisi, 19:4 (2014) 337-355.
G. Laporte, The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59:3 (1992) 345-358.
N. A. El-Sherbeny, Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University-Science, 22:3 (2010) 123-131.
P. Toth, D. Vigo (Eds.), Vehicle routing: problems, methods, and applications, Society for Industrial and Applied Mathematics, 2014.
B. M. Baker, M. A. Ayechew, A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30 (2003) 787-800.
D. Mester, O. Braysy, Active-guided evolution strategies for large-scale capacitated vehicle routing problems. Computers & Operations Research, 34:10 (2007) 2964-2975.
J. Berger, M. Barkaoui, A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 31:12 (2004) 2037-2053.
S. R. Thangiah, K E. Nygard, P. L. Juell, Gideon: A Genetic Algorithm System For Vehicle Routing With Time Windows, 7th IEEE Conference on Artificial Intelligence Applications, Miami Beach-Florida, 322–325, 24-28 Şubat, 1991.
M. F. Ibrahim, I. Masudin, T. E. Saputro, A hybrid genetic algorithm implementation for vehicle routing problem with time windows. Jurnal Ilmiah Teknik Industri, 14:2 (2016) 196-204.
C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31:12 (2004) 1985-2002.Y. Chang, L. Chen, Solve the vehicle routing problem with time windows via a genetic algorithm. Discrete and continuous dynamical systems supplement, (2007) 240-249.
B. Ombuki, B. J. Ross, F. Hanshar, Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence, 24:1 (2006) 17-30.
S. A. Haddadene, N. Labadie, C. Prodhon, NSGAII enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints. IFAC-PapersOnLine, 49:12 (2016) 1198-1203.
K. C. Tan, Y. H. Chew, L. H. Lee, A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications, 34:1 (2006) 115-151.
A. Mungwattana, T. Manisri, K. Charoenpol, G. K. Janssens, A solution for the bi-objective vehicle routing problem with the windows using local search and genetic algorithms. International Journal for Traffic and Transport Engineering, 6:2 (2016) 149-158.
K. Ghoseiri, S. F. Ghannadpour, Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing, 10:4 (2010) 1096-1107.
A. Garcia-Najera, J. A. Bullinaria, An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 38:1 (2011) 287-300.
W. K. Ho, J. C. Ang, A. Lim, A hybrid search algorithm for the vehicle routing problem with time windows. Int. J. Artif. Intell. Tools, 10:3 (2001) 431-449.
M. M. Solomon, J. Desrosiers, Survey Paper—Time Window Constrained Routing and Scheduling Problems. Transportation Science 22:1 (1988) 1-13.
B. E. Gillett, L. R. Miller, A heuristic algorithm for the vehicle dispatch problem. Oper. Res., 22 (1974) 340-349.
F. Kılıç, M. Gök, A Benchmark Proposal For Route-Planning Of Urban Bus Service, 4th Eastern European Regional Conference on the Engineering of Computer Based Systems, Bruno-Çek Cumhuriyeti, 134-137, 27-28 Ağustos, 2015.
K. Deb, A. Pratap, S. Agarwal, T. A. M. T. A. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput., 6:2 (2002) 182-197.
K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms. Vol. 16, John Wiley & Sons, 2001.
F. A. Fortin, D. Rainville, M. A. G. Gardner, M. Parizeau, C. Gagné, DEAP: Evolutionary algorithms made easy. The Journal of Machine Learning Research, 13:1 (2012) 2171-2175.
A. Seshadri, A Fast Elitist Multiobjective Genetic Algorithm: NSGA-II. MATLAB Central, 182, 2006.
M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res., 35:2 (1987) 254-265.