MULTIPERIOD MULTI TRAVELING SALESMEN PROBLEM UNDER TIME WINDOW CONSTRAINTS

Year 2014, Volume: 15 Issue: 2, 113 - 124, 11.05.2015

Haluk Yapıcıoğlu

https://doi.org/10.18038/btd-a.72818

Cited By: 1

Abstract

Traveling salesman problem is a classical optimization model that can be used to model various real life problems. In this study, multiple traveling salesman problem, which is a generalized version of the traveling salesman problem is modeled as a 0 – 1 integer programming approach under time window constraints. Different from the models existing in the literature, the number of salesmen is treated as a decision variable. Another new feature of the model is the addition of multiple periods which is especially important in the presence of time window constraints. Proposed model can be used to determine the minimum required number of university representatives that are assigned to cities throughout Turkey during the midterm, final and make-up exams of the faculties of Distance Education, Economics and Business Administration. Developed model is tested with various example problems with differing number of cities and different scenarios using integer programming approach. Based on the results obtained, the performance of the model is discussed

Keywords

Çoklu gezgin satıcı problemi; zaman kısıtları; tamsayılı programlama

ZAMAN KISITLARI ALTINDA ÇOK PERİYODLU ÇOKLU GEZGİN SATICI PROBLEMİ

Abstract

Gezgin satıcı problemi pek çok farklı gerçek hayat problemini modellemekte kullanılabilen klasik bir optimizasyon modelidir. Bu çalışmada gezgin satıcı probleminin genelleştirilmiş hali olan çoklu gezgin satıcı problemi, zaman kısıtları altında 0 - 1 tamsayılı olarak modellenmiştir. Bu modelde literatürden farklı olarak gezgin satıcı sayısı değişken olarak alınmıştır. Literatüre getirilen bir başka önemli yenilik de şehirlerin birden fazla periyodda ziyaret edilebilecek olmasıdır. Bu özellik zaman kısıtları göz önünde bulundurulduğunda daha da önem kazanmaktadır. Önerilen model mevcut hali ile Anadolu Üniversitesi Açıköğretim, İktisat ve İşletme Fakülteleri tarafından yurt çapında düzenlenen ara sınav, final sınavı ve bütünleme sınavlarında iller bazında görevlendirilecek olan üniversite temsilci sayısının en küçük değerinin belirlenmesine yönelik problemin çözümünde kullanılabilmektedir. Geliştirilen model farklı büyüklükteki örnek problemler ele alınarak farklı senaryolar için tamsayılı programlama yaklaşımı ile çözdürülmüş ve sonuçlar yorumlanmıştır. Elde edilen sonuçlar ışığında geliştirilen modelin performansı tartışılmıştır

Keywords

Çoklu gezgin satıcı problemi, Zaman kısıtları, Tamsayılı programlama

References

• Applegate, D.L., Bixby, R. E., Chvatal, V., Cook, W.J. (2006) The Traveling Salesman Problem: Princeton University Press. Study,
• Carter, A. E., Ragsdale, C. T. (2006) A New Approach to Solving The Multiple Traveling Salesperson Problem using Genetic Algorithms, European Journal of Operational Research, 175(1), 246-257.
• Dantzig, G, Fulkerson, R, Johnson, S (1954) Solution of A Large-Scale Traveling- Salesman Problem, Operations Research 2, 393-410.
• Gavish, B. (1976) A Note on The Formulation of The M-Salesman Traveling Salesman Problem, Management Science, 22 (6), 704–705.
• Gavish, B., Srikanth, K. (1986) An Optimal Solution Method for Large-Scale Multiple Traveling Salesman Problems, Operations Research, 34(5), 698–717.
• Kara, İ, Bektas, T. (2006) Integer Linear Programming Formulations of Multiple Salesman Problems and Its Variations, European Research, 174, 1449 – 1458. of Operational
• Karp, R. M. (1972). "Reducibility Among Combinatorial Problems". Editörler: R. E. Miller and J. W. Thatcher. Complexity of Computer Computations. New York: Plenum. 85–103.
• Kulkarni, R.V., Bhave, P.R. (1985) Integer Programming Formulations of Vehicle Routing Problems, European Journal of Operational Research, 20, 58–67.
• Laporte, G., Nobert,Y. (1980) A Cutting Planes Algorithm for The M-Salesmen Problem, Journal of The Operational Research Society, 31, 1017–1023.
• Menger, K. (1930) Das Botenproblem, in Eines Ergebnisse Kolloquiums 2 (K. Menger, editor), Teubner, Leipzig, 11-12. Mathematischen
• Miller, C.E., Tucker, A.W., Zemlin, R. A. (1960) Integer Programming Formulation of Travelling Salesman Problems, Journal of The Association of Computing Machinery, 7(4) 326 – 329.
• Süral, H. (2003) Gezgin Satıcı Problemi, Matematik Dünyası, 2003-III, 37 – 40. Svestka, J.A., Huckfeldt, V.E. (1973) Computational Experience with An M- Salesman Traveling Salesman Algorithm, Management Science, 19 (7), 790–799. Venkatesh, P., Singh, A. Approaches The Metaheuristic Multiple Traveling Salesperson Problem, Applied Soft Computing, 26, 74-89.
• Yuan, S, Skinner, B., Huang, S., Liu, D. (2013) A New Crossover Approach for Solving The Problem Using Genetic Algorithms, European Research, 228(1), 72-82. Salesmen Journal of Operational