Genetik Algoritmalar Yardımı ile Gezgin Satıcı Probleminin Çözümü Üzerine Bir Uygulama

Year 2010, Volume: 19 Issue: 3, 423 - 438, 01.09.2010

Yrd. Doç. Dr. Selçuk Çolak

Abstract

Traveling Salesman Problem aims to find the shortest route among n cities nodes customers branches etc with known distances between each city where the salesman leaves a city visits each of the cities exactly once and returns back to the starting point The traveling salesman problem one of the very important NP hard problems in optimization has wide application areas including distribution planning logistics and it has been studied by researchers and academicians for decades In this paper a genetic algorithm has been applied to solve the traveling salesman problem and a real world application of the study has been implemented on a food delivery firm in Adana The routes that the firm already uses and the routes that are found using genetic algorithms are compared to illustrate the efficiency of the algorithm Keywords: Traveling salesman problem genetic algorithms metaheuristic methods

Keywords

-

Genetik Algoritmalar Yardımı ile Gezgin Satıcı Probleminin Çözümü Üzerine Bir Uygulama

Abstract

Gezgin Seyyar Satıcı Problemi 8217;nde aralarındaki mesafeler bilinen n adet şehrin nokta düğüm yerleşim yeri müşteri şube vb her birine yalnız bir kez uğranarak başlangıç noktasına geri dönülmesi esnasında kat edilen toplam yolun en kısa olduğu şehir sırasının bulunması hedeflenir Dağıtım planlama lojistik gibi alanlar başta olmak üzere birçok sektörde geniş uygulama alanlarına sahip olan gezgin satıcı problemi optimizasyon alanında araştırmacı ve akademisyenler tarafından üzerinde uzun yıllardır yoğun olarak çalışılan çözümü zor NP hard bir problemdir Bu çalışmada meta sezgisel bir yöntem olan genetik algoritmalar yardımı ile gezgin satıcı problemine çözüm aranmış ve geliştirilen algoritmanın uygulaması Adana ilinde gıda sektöründe faaliyet gösteren bir firma üzerinde gerçekleştirilmiştir Firmanın güncel olarak kullandığı rotalar ile algoritma ile elde edilen rotalar karşılaştırılarak algoritmanın etkinliği gösterilmiştir Anahtar Kelimeler: Gezgin satıcı problemi genetik algoritmalar meta sezgisel yöntemler

Keywords

Gezgin satıcı problemi, genetik algoritmalar, meta sezgisel yöntemler

References

• Arora S., 1998. “Polynomial time approximation schemes for euclidian traveling salesman and other geometric problems”, Journal of the ACM, 45(5): 753-782.
• Applegate D.L., Bixby R.E., Chvatal V. ve Cook W.J., 2007. The traveling salesman problem: A computational study, Princeton University Press, Princeton, NJ,
• Bellmore M. ve Nemhauser G. L., 1968. “The traveling salesman problem: A survey”,
• Operations Research, 16:538–558. Cevre U., Özkan B. ve Uğur A., 2007. “Gezgin satıcı probleminin genetik algoritmalarla eniyilemesi ve etkileşimli olarak internet üzerinde görselleştirilmesi”,
• XII. “Türkiye’de İnternet” Konferansı 8-10 Kasım 2007, Ankara.
• Chatterjee S., Carrera C. ve Lynch L., 1996. “Genetic algorithms and traveling salesman problems.” European Journal of Operational Research, 93:490–510.
• Cochrane E. M. ve Beasley J. E., 2003. “The co-adaptive neural network approach to the euclidean traveling salesman problem”, Neural Networks, 16(10):1499-1525.
• Croes G. A., 1958. “A method for solving traveling salesman problems”, Operations Research, 6:791–812.
• Dantzig G., Fulkerson R., ve Johnson S., 1954. "Solution of a large-scale traveling- salesman problem", Operations Research, 2: 393-410.
• Dorigo M., Maniezzo V. ve Colorni A., 1996. “The ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics- Part B, 26(1): 29-41.
• Fiechter C.N., 1994. “A parallel tabu search algorithm for large traveling salesman problems”, Discrete Applied Mathematics, 51: 243 –267.
• Gao H.C., Feng B.Q., ve Zhu,L., 2006. “Reviews of the meta-heuristic algorithms for
• TSP”, Control ve Decision, 3: 241-246. Garey M.R. ve Johnson D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and co., New York.
• Goldberg, D. ve Lingle, R. (1985). “Alleles, loci,and the TSP”. In Proceedings of an
• International Conference on Genetic Algorithms and Their Applications, 154-159. Goldberg D., 1989. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, USA.
• Gonzales E.L. ve Fernandez M.A.R., 2000. “Genetic optimization of a fuzzy distribution model”, International Journal of Physical Distribution & Logistics Management, 30(7/8): 681-696.
• Holland J.H., 1975. Adaptation in Natural and Artificial Systems, The University of
• Michigan Press, Ann Arbor, MI. Jang J.S.R., 1997. Neuro-Fuzzy and Soft Computing: A Computational Approach To
• Learning and Machine Intelligence, Prentice-Hall, USA, 173-196. Johnson D.S. ve McGeoch L.A., 1995. “The traveling salesman problem: a case study in local optimization”,Local Search in Combinatorial Optimization, 215-310.
• Jozefowiez N., Glover F. ve Laguna M., 2008. “Multi-objective meta-heuristics for the traveling salesman problem with profits”, Journal of Mathematical Modelling and Algorithms, 7(2): 177-195.
• Kirkpatrick S., Gelatt C.D. ve Vecchi M.P., 1983. “Optimization by simulated annealing”, Science, 220: 671-680.
• Laporte G., 1992. “The traveling salesman problem: an overview of exact and approximate algorithms”, European Journal of Operational Research, 59:231-247.
• Larranaga P., Kuijpers C.M.H., Murga R.H., Inza I., Dizdarevic S., 1999. “Genetic algorithms for the traveling salesman problem: A review of representations and operators”, Articial Intelligence Review, 13: 129 -70.
• Malek M., Guruswamy M., Pandya M. ve Owens H., 1989. “Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem”,
• Annals of Operations Research, 21(1): 59-84. Menger K., 1932. "Das botenproblem", in Ergebnisse eines Mathematischen
• Kolloquiums 2 (K. Menger, editor), Teubner, Leipzig. Merz P. ve Freisleben B., 2001. “Memetic algorithms for the traveling salesman problem”, Complex Systems, 4:297–345.
• Miliotis P., 1976. "Integer programming approaches to the traveling salesman problem",
• Mathematical Programming 10: 367-378. Murata, T., Ishıbuchi, H. ve Tanaka, H. (1996). “Genetic algorithms for flow shop scheduling problems, Computers and Industrial Enginering, 30:4, 1061-1071.
• Roberts S. M. ve Flores B., 1966. “An engineering approach to the traveling salesman problem”, Management Science, 13:269-288.
• Schmitt L ve Amini M., 1998. “Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: an mpirical study.” European Journal of Operational Research, 108:551-70.
• Syswerda, G., 1991. “Schedule optimization using genetic algorithms”, Handbook of
• Genetic Algorithms, New York NY, 350-372. Takahashi, R., 2005. ‘Solving the traveling salesman problem through genetic algorithms with changing crossover operators’, Machine Learning and Applications,
• Proceedings, Fourth International Conference, Los Angeles, CA, 319-325. Tao Y. Q., Cui D. W., Miao X. L., ve Chen, H., 2007. “An improved swarm intelligence algorithm for solving TSP problem”, Lecture Notes in Computer Science, 813-822.
• Tsai H.K., Yang J.M., Tsai Y.F. ve Kao C.Y., 2004. “Some issues of designing genetic algorithms for traveling salesman problems”, Soft Computing, 8: 689-697.
• Yeo M.F., ve Agyei E.O., 1998. “Optimizing engineering problems using genetic algorithms”, Engineering Computations, 15(2): 268-280.