Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama

ÇOLAK, SELÇUK

Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama

Selçuk ÇOLAK (Çukurova Üniversitesi, İktisadi ve İdari Bilimler Fakültesi, İşletme Bölümü, Adana, Türkiye)

Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi

16 0

Yıl: 2010 Cilt: 19 Sayı: 3 Sayfa Aralığı: 423 - 438 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama

Öz:

Gezgin (Seyyar) Satıcı Problemi’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 şehirsı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ıryoğun olarak çalışılan çözümü zor (NP-hard) bir problemdir. Bu çalışmada metasezgisel 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ündefaaliyet gösteren bir firma üzerinde gerçekleştirilmiştir. Firmanın güncel olarakkullandığı rotalar ile algoritma ile elde edilen rotalar karşılaştırılarak algoritmanınetkinliği gösterilmiştir

Anahtar Kelime:

Öz:

Traveling Salesman Problem aims to find the shortest route, among n cities (nodes,customers, branches etc.) with known distances between each city, where the salesmanleaves 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 inoptimization, has wide application areas including distribution, planning, logistics, andit has been studied by researchers and academicians for decades. In this paper, a geneticalgorithm has been applied to solve the traveling salesman problem and a real worldapplication of the study has been implemented on a food delivery firm in Adana. Theroutes that the firm already uses and the routes that are found using genetic algorithmsare compared to illustrate the efficiency of the algorithm.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

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.

APA	ÇOLAK S (2010). Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. , 423 - 438.
Chicago	ÇOLAK SELÇUK Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. (2010): 423 - 438.
MLA	ÇOLAK SELÇUK Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. , 2010, ss.423 - 438.
AMA	ÇOLAK S Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. . 2010; 423 - 438.
Vancouver	ÇOLAK S Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. . 2010; 423 - 438.
IEEE	ÇOLAK S "Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama." , ss.423 - 438, 2010.
ISNAD	ÇOLAK, SELÇUK. "Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama". (2010), 423-438.

APA	ÇOLAK S (2010). Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 19(3), 423 - 438.
Chicago	ÇOLAK SELÇUK Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi 19, no.3 (2010): 423 - 438.
MLA	ÇOLAK SELÇUK Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, vol.19, no.3, 2010, ss.423 - 438.
AMA	ÇOLAK S Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi. 2010; 19(3): 423 - 438.
Vancouver	ÇOLAK S Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi. 2010; 19(3): 423 - 438.
IEEE	ÇOLAK S "Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama." Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 19, ss.423 - 438, 2010.
ISNAD	ÇOLAK, SELÇUK. "Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama". Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi 19/3 (2010), 423-438.