Karayolları Bakım Çalışmasında Kullanılan Araçların Güzergâhlarının Hiyerarşik Çinli Postacı Problemi Kullanılarak Düzenlenmesi

Ayrıt rotalama problemleri, kombinatoriyel optimizasyon problemlerinden biridir.

Anahtar Kelimeler:

Ayrıt rotalama, hiyerarşik Çinli postacı problemi, karayolu bakım çalışmaları, karayolu bakım çalışmaları

Route Management for Vehicles Used in Road Maintenance Activities through Hierarchical Chinese Postman Problem Approach

The arc routing problems are one of the combinatorial optimization problems.The aim of solving such problems is to determine a least cost tour which covers all or subsetof arcs in a graph. The Hierarchical Chinese Postman Problem (HCPP) is a variant of ChinesePostman Problem, one of the most common arc routing problems. There are many applicationareas of HCPP in real life, such as snow plowing, garbage collection, road maintenance, letterdelivery, routing of patrolling vehicles. In this study, it was aimed to find the best / nearest routeswith the least cost by the HCPP approach in order to carry out the road maintenance activitieswhich the roads connected to the 12th Regional Directorate of Highways. A nearest neighborsearch based algorithm was developed in order to solve the handled large-scale problem. Theproposed algorithm was conducted on the road network involved and an efficient result wasobtained.

Keywords:

Arc routing, hierarchical Chinese postman problem, road maintenance activities,

PDF

___

Referans1: Alfa AS, Liu DQ, 1988. Postman routing problem in a hierarchical network. Engineering Optimization, 14: 127-138.
Referans2: Ahuja RK, Magnanti TL, Orlin JB, 1993. Network Flows: Theory, Algorithms and Applications. Prentice Hall: New Jersey.
Referans3: Ahuja RK, Orlin JB, 2002. Combinatorial algorithms for inverse network flow problems. Networks An International Journals, 40 (4): 181-187.
Referans4: Cabral EA, Gendreau M, Ghiani G, Laporte G, 2004. Solving the hierarchical Chinese postman problem as a rural postman problem. European Journal of Operational Research, 155 (2): 44-50.
Referans5: Damodaran P, 1997. A methodology for dynamic planning of road service during a snow fall, Northern Illinois University, DeKalb, IL, M.S. Thesis.
Referans6:Damodaran P, Krishnamurthi M, Srihari K, 2008. Lower Bounds For Hierarchial Chinese Postman Problem. International Journal of Industrial Engineering, 15 (1): 36-44.
Referans7: Dror M, Stern H, Trudeau P, 1987. Postman tour on a graph with precedence relation on arcs. Networks, 17: 283-294.
Referans8: Emel GG, Taşkın Ç, Dinç E, 2003. Yönsüz Çinli Postacı Problemi: Polis Devriye Araçları İçin Bir Uygulama. Anadolu Üniversitesi Sosyal Bilimler Dergisi, 3 (1): 121-140.
Referans9: Ghiani G, Improta G, 2000. An algorithm for the hierarchical Chinese postman problem. Operations Research Letters, 26: 27-32.
Referans10: Krishnamurthi M, Damodaran P, 1998. A modified postman tour heuristic for efficient snow removal planning, Proceedings of 7th Industrial Engineering Research Conference, Banff, Canada.
Referans11: Korteweg P, Volgenant T, 2006. On the Hierarchical Chinese Postman Problem with Linear Ordered Classes. European Journal of Operational Research, 169: 41-52.
Referans12: Kwan MK, 1962. Chinese Postman Problem, Graphic Programming Using Odd or Even Points, Chinese Math., 1: 273-277.
Referans13: Lemieux PF, Campagna L, 1984. The snow ploughing problem solved by a graph theory algorithm. Civil Engineering Systems, 1: 337-341.
Referans14: Sayata UB, Desai NP, 2015. An Algorithm for Hierarchical Chinese Postman Problem Using Minimum Spanning Tree Approach Based on Kruskal’s Algorithm. 2015 IEEE International Advance Computing Conference, June 12-13, pp: 222-227.
Referans15: Thimbleby H, 2002. Explaining Code For Publication, Software-Practice & Experience.
Referans16: Yılmaz M, Kayacı Çodur M, Yılmaz H, 2017. Chinese Postman Problem Approach for a Large-scale Conventional Rail Network in Turkey. Tehnicki Vjesnik-Technical Gazette, 5: 1471-1477.