Çağatan TAŞKIN, Emtullah DİNÇ, Gül EMEL GÖKAY

Yönsüz Çinli Postacı Problemi: Polis Devriye Araçları İçin Bir Uygulama

Ayrıt rotalama problemi, birleşi en iyilemenin temel problemlerinden biridir. Bu çalışmada, ayrıt rotalama problemlerinden Çinli postacı problemi incelenmektedir. Çinli postacı probleminin gerçek hayatta; mektup dağıtımı, yol bakımı, polis devriye araçlarının ve kar temizleme araçlarının rotalarının belirlenmesi ve otobüs çizelgelemesi gibi pek çok uygulamasını görmek mümkündür. Çalışmada, önce Çinli postacı problemiyle ilgili temel kavramlar, problemin çeşitleri ve yönsüz Çinli postacı probleminin çözüm yöntemleri incelenmektedir. Daha sonra ise, belli bir bölgedeki yollardan geçmek zorunda olan bir polis devriye aracının en iyi rotasının bulunması, yönsüz Çinli postacı problemi olarak ele alınmaktadır. Model, en kısa mesafeli eşleştirme yöntemi kullanılarak çözülmekte ve polis devriye aracının en iyi rotası belirlenmektedir.

Undirected Chinese Postman Problem: An Application on Patrol Cars

Arc routing problem being one of the well known problems in combinatorial optimization is handled in this paper. The Chinese postman problem which is an arc routing problem, has many applications in real life problems such as mail delivery, road maintenance, routing of patrol cars and snow ploughs and bus scheduling. In this paper; after the explanation of basic concepts of Chinese postman problem, information about the types of Chinese postman problem is given. Then the solution methods for the undirected Chinese postman problem are examined and one of the solution methods, minimum length-matching method, is applied to the routing of a patrol car.

PDF

___

Ahr, D. ve Reinelt, A.G., Discrete Optimization, http://www.iwr.uni-heidelberg.de/groups/comopt/mitarbeiter/ahr/research/overviewArcRouting/nodel.html (erişim tarihi 18 Ekim 2002).
Ahuja, R.K., Magnanti, T.L. ve Orlin, J.B. (1993). Network Flows: Theory, Algorithms and Applications, Prentice Hall: New Jersey.
Avriel, M. ve Golany, B. (1996). Mathematical Programming For Industrial Engineers, Marcel Dekker Inc., New York.
Backin, B.,Hamiltonian and Euler Paths, http://www.infosun.fmi.uni-passau.de/br/lehrstuhl/Kurse/Proseminar_ss01/Hamiltonian_and_Euler.pdf. (erişim tarihi 17 Ekim 2002).
Berge, C. (1964). Graph Theory, American Mathematical Monthly, 71(5), 471-481.
Corberan, A., Marti, R. ve Romero, A. (2000). Heuristics For The Mixed Rural Postman Problem, Computers & Operations Research, 27(2), 183-203.
Corberan, A., Marti, R. ve Sanchis, J. M. (2002a). A GRASP Heuristic For The Mixed Chinese Postman Problem, European Journal Of Operational Research, 142(1), 70-80.
Corberan, A., Marti, R., Martinez, E. ve Soler, D. (2002b). The Rural Postman Problem On Mixed Graphs With Turn Penalties, Computers &Operations Research, 29(7), 887-903.
Eglese, R.W. ve Li, Y.O. L. (1996). An Interactive Algorithm For Vehicle Routeing For Winter-Gritting, The Journal Of The Operational Research Society, 47(2), 217-228.
Eglese, R.W. ve Li, Y.O.L. (1992). Efficient Routeing For Winter Gritting, The Journal Of The Operational Research Society, 43(11), 1031-1034.
Eiselt, H. A., Gendreau, M. ve Laporte, G. (1995a). Arc Routing Problems, Part 1: The Chinese Postman Problem, Operations Research, 43(2),231-242.
Eiselt, H. A-, Gendreau, M. ve Laporte, G. (1995b). Arc Routing Problems, Part 2: The Rural Postman Problem, Operations Research, 43(3),399-414.
Florian, M. (1984). Transportation Planning Models, Elsevier Science Publishers B.V.: North Holland.
Ghiani, G. ve Improta, G. (2000). An Algorithm For The Hierarchical Chinese Postman Problem, Operations Research Letters, 26(1), 27-32.
Greistorfer, P. (2003). A Tabu Scatter Search Metaheuristic For The Arc Routing Problem, Computers & Industrial Engineering, 44(2), 249-266.
Harary, F. (1960). Some Historical and Intuitive Aspects of Graph Theory, SIAM Review, 2(2), 123-131.
Ignizio, P. J. (1980). Solving Large-Scale Problems: A Venture Into A New Dimension, The Journal Of The Operational Research Society, 31(3), 217-225.
Kara, İ. (1991). Doğrusal Programlama, Bilim Teknik Yayınevi: Eskişehir.
Laporte, G. (1997). Modeling And Solving Several Classes Of Arc Routing Problems As Traveling Salesman Problems, Computers & Operations Research, 24(11), 1057-1061.
Lawler, E. (2001). Combinatorial Optimization: Networks and Matroids, Dover Publications, Inc., USA.
Minieka, E. (1979). The Chinese Postman Problem For Mixed Networks, Management Science, 25(7), 643-648.
Network Flow Problems, http://www.csulb.edu/~obenli/Research/IE-encyc/networks. html, (erişim tarihi 15 Ekim 2002).
Routing Problems, http://www.informatik.uni-heidelberg.de/groups/comopt/projekte/projektpostman/PostmanPosterEnglisch.pdf (erişim tarihi 18 Ekim 2002).
Taha, H. (2000). Yöneylem Araştırması, 6. Basımdan Çeviri, Literatür Yayıncılık: İstanbul.
Thimbleby, H., The Directed Chinese Postman Problem,
http://www.cs.mdx.ac.uk/harold/cpp/new-Java-cpp.pdf (erişim tarihi 5 Ekim 2002).
Türkay, A. (2003). Yükleme Kısıtı Altında Taşıt Rotalama Problemleri, Yayınlanmamış Yüksek Lisans Tezi: Bursa.