ÇOK NOKTALI GENELLEŞTİRİLMİŞ GEZEN SATICI PROBLEMİ ve PERAKENDE SEKTÖRÜNDE BİR UYGULAMA

Çalışmamızda Genelleştirilmiş Gezgin Satıcı Probleminin (GGSP) yeni bir versiyonu olan Çok Noktalı Genelleştirilmiş Gezgin Satıcı Problemi (ÇNGGSP) ele alınmıştır. ÇNGGSP her bir salkımda tek bir noktaya uğramak yerine, belirlenen oranda noktaya uğraması yönüyle GGSP probleminden ayrılmaktadır. Problem perakende sektöründe faaliyet gösteren bir marketler zincirinde denetim faaliyetlerinin planlanmasında kullanılmıştır. Farklı oranlar için problem geliştirilen bir metasezgisel ile çözülmüş ve sonuçlar tartışılmıştır.

MULTI POINT GENERALIZED TRAVELLING SALESMAN PROBLEM

In our study, we handle the Multi-point Generalized traveling Salesman Problem (MP-GTSP) which is a new version of the Generalized Traveling Salesman Problem (GTSP). MT-GTSP differ from GTSP with the node selection. MP-GTSP tour including at least one node from each cluster depending on specified rate instead of single point in each cluster. Problem designed for the retail industry, which operates a chain of grocery stores in the audit of the activities used in planning. Problem solved for different rates with using developed metaheuristic and the results are discussed.

___

  • Ben-Arieh D., Gutin G., Penn M., Yeo A., Zverovitch A., (2003), “Transformations Of Generalized ATSP Into ATSP”, Oper. Res. Lett., 31(5):357-365
  • Bontoux, B., Christian , A. Dominique, F. , (2009) , “A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem”, Computers & Operations Research 37 ,1844 – 1852
  • Cacchiani, V., Muritiba A., Negreiros, M, Toth,P. (2010), “A Multistart Heuristic For The Equality Generalized Traveling Salesman Problem”, Published Online 22 December 2010 In Wiley Online Library Chentsov, G, Korotayeva, N., (1995), “The Dynamic Programming Method in the Generalized Traveling Salesman Problem”, Mat/J. Compnt. Modelling Vol. 25, No. 1, 93-105
  • CM Pintea, PC Pop, C Chira, (2007), “The Generalized Traveling Salesman Problem Solved With Ant Algorithms”, Journal Of Universal Computer Science Dimitrijevic, V., Saric, Z. (1997). “Efficient Transformation Of The Generalized Traveling Salesman Problem İnto The Traveling Salesman Problem On Digraphs”, Information Science, 102, 65–110.
  • Dror, M., Langevin, A., (1997),” Generalized Tsp Approach To The Directed Clustered Rural Postman Problem”, Transportation Science , 187-192
  • Fischetti, M., (1997). Salazar-Gonzalez, J., Toth, P., “A Branch-And-Cut Algorithm For The Symmetric Generalized Traveling Salesman Problem”, Oper. Res. 45(3), 378–394.
  • Golden, B, Naji-Azimi, Z.Ragyavan S, Salari, M.,Toth, P, (2012), “The Generalized Covering Salesman Problem”, Informs Journal, Pubsonline.Informs.Org Gutin, G., Karapetyan, D., (2010), “ A Memetic Algorithm For The Generalized Traveling Salesman Problem”, Nat. Comput., 9(1) ,47-60
  • Helsgaun, K. (2014), “Solving The Equality Generalized Traveling Salesman Problem Using The Lin-Kernighan-Helsgaun Algorithm”, Computer Science Research Report Kan, J, Zhang Y. ,(2012) , “Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem”, 2012 International Conference on Future Electrical Power and Energy Systems, Energy Procedia 17, 319 – 325
  • Kara, I. Guden, H., Koç, Ozge, (2011),” New Formulations For The Generalized Traveling Salesman Problem”, Recent Researches In Applied Mathematics And Economics
  • Kara, İ., Bektaş, T., (2003),” Integer Linear Programming Formulation Of The Generalized Vehicle Routing Problem ”,Presented In 5th EURO/INFORMS Joint International Meeting, July 6-10 2003 İstanbul, Turkey Karaboğa, D., (2004), Yapay Zeka Optimizasyon Algoritmaları, İstanbul, Atlas Yayın Dağıtım.
  • Karapetyan, D., Gutin, G., (2011),” Lin-Kernighan Heuristic Adaptations For The Generalized Traveling Salesman Problem. European Journal Of Operational Research” 208, 221–232 72
  • Karapetyan. D., Gutin, G., (2012), “Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem”., Eur. J. Oper. Res, 219(2):234-251
  • Karp, R.M, (1972), "Reducibility Among Combinatorial Problems", In R. E. Miller and J. W. Thatcher (editors), Complexity of Computer Computations, 85–103 Laporte, G., Mercure, H., Nobert, Y. (1987). “Generalized Traveling Salesman Problem Through N -Sets Of Nodes - The Asymmetrical Case”, Discrete Appl. Math. 18(2), 185–197.
  • Laporte, G., Semet, F. (1999), “Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem”, INFOR 37(2), 114-120
  • Lian Ming-Mou, (2012), “The Continuous Selective Generalized Traveling Salesman Problem: An Efficient Ant Colony System”, 8th International Conference on Natural Computation, 1242-1246
  • Mohammad, S., Majid S. , Zahra N., (2014), “The generalized covering traveling salesman problem”, Applied Soft Computing 24 , 867–878
  • Mou, L., (2011), “An Efficient Ant Colony System ForSolving The New Generalized Traveling Salesman Problem”, Proceedings Of IEEE CCIS2011 Noon, C., Bean, J. (1991). “A Lagrangian Based Approach For The Asymmetric Generalized Traveling Salesman Problem”, Oper. Res. 39(4), 623–632.
  • Renaud, J., Boctor, F. (1998), “An Efficient Composite Heuristic For The Symmetric Generalized Traveling Salesman Problem”, Eur. J. Oper. Res. 108(3), 571–584. Rice, M. Tsotras, V., (2012), “Exact Graph Search Algorithms For Generalized Traveling Salesman Path Problems”, 11th International Symposium On Experimental Algorithms, Springer Silberholz, J., Golden, B. (1997). “The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach”, Extending The Horizons: Advances İn Computing, Optimization And Decision Technologies, Vol. 37, Pp. 165–181.
  • Heidelberg, Springer. Shaelaiea , H., Azimib , Z., Salari, M., (2014) . “ The generalized covering traveling salesman problem”, Applied Soft Computing, Volume 24, 867–878,Elsevier Snyder, L., Daskin, M. (2006), “A Random-Key Genetic Algorithm For The Generalized Traveling Salesman Problem”, Eur. J. Oper. Res. 174, 38–53.
  • Srivastava, S., Kumar, S., Garg, R., Sen, R. (1970). “Generalized Traveling Salesman Problem Through N Sets Of Nodes”, Journal Of The Canadian Operational Research Society 7, 97–101.
  • Sural, H., (2003)“Gezgin Satıcı Problemi”, Matematik Dünyası Dergisi, Güz Sayısı Tasgetiren, M., Suganthan, P., Pan, Q.-K., (2010). “An Ensemble Of Discrete Differantial Evolution Algorithms For Solvining The Generalized Traveling Salesman Problem” , Applied Mathematics and Computation, 215 (9), 3356-3368.
  • Uluşans, İ., (2010), “Yerel Tarama Ile Birleştirilmiş Kesikli Farksal Evrim Algoritmasi Kullanarak Genelleştirilmiş Gezgin Satici Probleminin Çözümü”, Yaşar Üniversitesi Sosyal Bilimler Enstitüsü Işletme Anabilim Dali Yüksek Lisans Tezi X Tang, C Yang, X Zhou, W Gui, (2013), “A Discrete State Transition Algorithm For Generalized Traveling Salesman Problem”, Arxiv:1304.7607 [Math.OC] Zaheed, A.Younas, I., Zahoor M., (2010), “A Novel Genetic Algorithm For GTSP”, International Journal Of Computer Theory And Engineering, Vol.2, No.6, December, 1793-8201 ELEKTRONİK KAYNAKLAR Cook, W. , “Milestones in the Solution of TSP Instances”, The Travelling Salesman” (http://www.math.uwaterloo.ca/tsp/history/milestone.html) . [28.12.2014,WEB;] Vericert, “Gıda Zincir Mağaza/Şube Ve Bayi Denetimleri” (http://www.vericert.com.tr/ ). [29.12.2014, WEB;] Taşkın, S. , “Zincir Mağazacılıkta Operasyonel Denetim Faaliyetleri” (http://www.perakende.org/guncel/zincir-magazacilikta-operasyonel-denetim- faaliyetleri-1342018036h.html) .[29.12.2014,WEB;]