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

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

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.

9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. Baygin, M., and Karakose, M., “A new intelligent group elevator control approach”, 15th International Symposium in Mechatronika, pp. 1-6, 2012.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.