ERZURUM BÜYÜKŞEHİR BELEDİYESİ İÇİN KLONAL SEÇİM ALGORİTMASI KULLANILARAK EN KISA YOL TESPİTİ

Year 2017, , 138 - 142, 24.12.2017

Abdullah Naralan , Salih Serkan Kaleli , Mehmet Bayğın

https://doi.org/10.22531/muglajsci.357621

Cited By: 3

Abstract

Optimizasyon
algoritmaları günlük yaşamdaki birçok problemi çözmeye yarayan ve genellikle
büyük bir çözüm uzayına sahip problemlerde optimal çözümü tespit etmeye yarayan
yaklaşımlar bütünüdür. Bu çalışmada yapay bağışıklık sisteminin alt yöntemi
olan klonal seçim algoritması kullanılarak bir optimum rota tespit yaklaşımı
geliştirilmiştir. Bu amaçla Erzurum Büyükşehir Belediyesinden temin edilen
karayolu yolcu taşıma ağı modellenmiş olup, bu ağdan seçilen ve hali hazırda
kullanılan bir otobüs hattı klonal seçim algoritması ile incelenmiştir.
Önerilen yaklaşım için geliştirilen optimizasyon yöntemi MATLAB ortamında
gerçekleştirilmiş ve elde edilen sonuçlar Google Maps üzerinde karşılaştırmalı
olarak çizdirilmiştir. Önerilen yöntemin performansı test edilmiş ve elde
edilen sonuçlara göre yaklaşık %10’luk bir performans artışı sağlanmıştır. 

Keywords

En Kısa Yol Tespiti, Klonal Seçim Algoritması, Optimizasyon, Gezgin-Satıcı, Yapay Bağışıklık Sistem

SHORTEST PATH DETECTION USING CLONAL SELECTION ALGORITHM FOR ERZURUM METROPOLITAN MUNICIPALITY

Abstract

Optimization algorithms
are an approach to solving many problems in everyday life and usually to find
the optimal solution for problems with a large solution space. In this study,
an optimal route detection approach was developed using the clonal selection
algorithm which is a sub-method of the artificial immune system. For this
purpose, the road passenger transport network obtained from Erzurum Metropolitan
Municipality has been modeled and a bus line which is selected and used from
this network has been examined by clonal selection algorithm. The optimization
method developed for the proposed approach was implemented in the MATLAB
environment and the results obtained are plotted comparatively on Google Maps.
The performance of the proposed method was tested and a performance improvement
of about 10% was achieved according to the results obtained.

Keywords

Shortest Path Detection, Clonal Selection Algorithm, Optimization, Traveling Salesman, Artificial Immune System

References

• Abeysundara, S., Giritharan, B., and Kodithuwakku, S., “A Genetic algorithm approach to solve the shortest path problem for road maps”, In Proceedings of the International Conference on Information and Automation, pp. 272-275, 2005.
• Barketau, M., and Pesch, E., “An approximation algorithm for a special case of the asymmetric travelling salesman problem”, International Journal of Production Research, vol. 54, no. 14, pp. 4205-4212, 2016.
• Dorigo, M., and Gambardella, L. M., “Ant-Q: A reinforcement learning approach to the traveling salesman problem”, In Proceedings of ML-95, Twelfth Intern. Conf. on Machine Learning, pp. 252-260, 2016.
• Bartal, Y., Gottlieb, L. A., and Krauthgamer, R., “The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme”, SIAM Journal on Computing, vol. 45, no. 4, pp. 1563-1581, 2016.
• Osaba, E., Yang, X. S., Diaz, F., Lopez-Garcia, P., and Carballedo, R., “An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems”, Engineering Applications of Artificial Intelligence, vol. 48, pp. 59-71, 2016.
• Mahi, M., Baykan, Ö. K., and Kodaz, H., “A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem”, Applied Soft Computing, vol. 30, pp. 484-490, 2015.
• Dikmen, H., Dikmen, H., Elbir, A., Eksi Z., and Çelik, F., “Gezgin satıcı probleminin karınca kolonisi ve genetik algoritmalarla eniyilemesi ve karşılaştırılması”, Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, vol. 18, no. 1, pp. 8-13, 2014.
• Groba, C., Sartal, A., and 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, vol. 56, pp. 22-32, 2015.
• Anderson, R., Ashlagi, I., Gamarnik, D., and Roth, A. E., “Finding long chains in kidney exchange using the traveling salesman problem”, Proceedings of the National Academy of Sciences, vol. 112, no. 3, pp. 663-668, 2015.
• Taş, D., Gendreau, M., Jabali, O., and Laporte, G., “The traveling salesman problem with time-dependent service times”, European Journal of Operational Research, vol. 248, no. 2, pp. 372-383, 2016.
• Mavrovouniotis, M., and Yang, S., “Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors”, Applied Soft Computing, vol. 13, no. 10, pp. 4023-4037, 2013.
• Baygin, M., Kaleli, S. S., and Naralan A., Optimal Route Detect Based On Genetic Algorithm for Erzurum Metropolitan Municipality” 5th International Conference on Advanced Technology & Sciences (ICAT'17), pp. 167-171, 2017.
• Zeren, F., and Baygin, M., “Genetik Algoritmalar ile Optimal Portföy Seçimi: BİST-30 Örneği”, Journal of Business Research Turk, vol. 7, no. 1, pp. 309-324, 2015.
• Baygin, M., and Karakose, M., “A new intelligent group elevator control approach”, 15th International Symposium in Mechatronika, pp. 1-6, 2012.
• Rego, C., Gamboa, D., and Glover, F., “Doubly‐rooted stem‐and‐cycle ejection chain algorithm for the asymmetric traveling salesman problem”, Networks, vol. 68, no. 1, pp. 23-33, 2016.
• Subramanyam, A., and Gounaris, C. E., “A branch-and-cut framework for the consistent traveling salesman problem”, European Journal of Operational Research, vol. 248, no. 2, pp. 384-395, 2016.
• Aydin, I., Karakose, M., and Akin, E., “A multi-objective artificial immune algorithm for parameter optimization in support vector machine”, Applied Soft Computing, vol. 11, no. 1, pp. 120-129, 2011.
• Zhang, W., Lin, J., Jing, H., and Zhang, Q., “A Novel Hybrid Clonal Selection Algorithm with Combinatorial Recombination and Modified Hypermutation Operators for Global Optimization”, Computational Intelligence and Neuroscience, vol. 2016, 2016.
• Díaz-Cortés, M. A., Cuevas, E., and Rojas, R., “Clonal Selection Algorithm Applied to Circle Detection”, In Engineering Applications of Soft Computing, vol. 129, pp. 143-164, 2017.