M13
Çok Noktalı Genelleştirilmiş Gezen Satıcı Problemi ve Perakende Sektöründe Bir Uygulama
Doç. Dr. Timur Keskintürk
İstanbul Üniversitesi İşletme Fakültesi Sayısal Yöntemler Anabilim Dalı
Araş. Gör. Bahadır Fatih Yıldırım
İstanbul Üniversitesi İşletme Fakültesi Sayısal Yöntemler Anabilim Dalı
Ümran Tüzün
İstanbul Üniversitesi Sosyal Bilimler Enstitüsü
Hilal Kaya
İstanbul Üniversitesi Sosyal Bilimler Enstitüsü
Özet
Ç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.
Anahtar Kelimeler: Denetim, Genelleştirilmiş Gezgin Satıcı Problemi, Rotalama
Multi-point Generalized Traveling Salesman Problem
Abstract
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.
Keywords: Auditing, Generalized Travelling Salesman Problem, Routing
- 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
- 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
- Cook, W. , “Milestones in the Solution of TSP Instances”, The Travelling Salesman” (http://www.math.uwaterloo.ca/…) . [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/gunc…) .[29.12.2014,WEB]