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

Abstract

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 subset

of arcs in a graph. The Hierarchical Chinese Postman Problem (HCPP) is a variant of Chinese

Postman Problem, one of the most common arc routing problems. There are many application

areas of HCPP in real life, such as snow plowing, garbage collection, road maintenance, letter

delivery, routing of patrolling vehicles. In this study, it was aimed to find the best / nearest routes

with the least cost by the HCPP approach in order to carry out the road maintenance activities

which the roads connected to the 12th Regional Directorate of Highways. A nearest neighbor

search based algorithm was developed in order to solve the handled large-scale problem. The

proposed algorithm was conducted on the road network involved and an efficient result was

obtained.

Keywords

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

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

Abstract

Ayrıt rotalama problemleri, kombinatoriyel optimizasyon problemlerinden biridir.

Bu problemlerin amacı, bir şebeke üzerinde yer alan ayrıtların tümünü ya da alt kümelerini

kapsayacak şekilde en kısa maliyetli turları bulmaktır. Hiyerarşik Çinli Postacı Problemi

(HÇPP), en yaygın ayrıt rotalama problemlerinden biri olan Çinli Postacı Probleminin bir

türü olup gerçek hayatta; kar küreme, çöp toplama, yol bakım çalışmaları, mektup dağıtımı ve

devriye gezen polis/güvenlik araçlarının rotalanması gibi pek çok uygulama alanı vardır. Bu

çalışmada, HÇPP yaklaşımı ile Karayolları 12. Bölge Müdürlüğüne bağlı yollarda yapılan bakım

çalışmalarının en az maliyetle gerçekleştirilmesi için eniyi/eniyiye yakın rotaların bulunması

amaçlanmıştır. Ele alınan problem büyük boyutlu olup çözümü için en yakın komşu arama

tabanlı bir sezgisel algoritma geliştirilmiştir. Geliştirilen algoritma, ele alınan tüm karayolu

şebekesi için çalıştırılmış ve etkin bir sonuç elde edilmiştir.

Keywords

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

References

1. Referans1: Alfa AS, Liu DQ, 1988. Postman routing problem in a hierarchical network. Engineering Optimization, 14: 127-138.
2. Referans2: Ahuja RK, Magnanti TL, Orlin JB, 1993. Network Flows: Theory, Algorithms and Applications. Prentice Hall: New Jersey.
3. Referans3: Ahuja RK, Orlin JB, 2002. Combinatorial algorithms for inverse network flow problems. Networks An International Journals, 40 (4): 181-187.
4. 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.
5. Referans5: Damodaran P, 1997. A methodology for dynamic planning of road service during a snow fall, Northern Illinois University, DeKalb, IL, M.S. Thesis.
6. Referans6:Damodaran P, Krishnamurthi M, Srihari K, 2008. Lower Bounds For Hierarchial Chinese Postman Problem. International Journal of Industrial Engineering, 15 (1): 36-44.
7. Referans7: Dror M, Stern H, Trudeau P, 1987. Postman tour on a graph with precedence relation on arcs. Networks, 17: 283-294.
8. 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.

9. Referans9: Ghiani G, Improta G, 2000. An algorithm for the hierarchical Chinese postman problem. Operations Research Letters, 26: 27-32.
10. 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.
11. Referans11: Korteweg P, Volgenant T, 2006. On the Hierarchical Chinese Postman Problem with Linear Ordered Classes. European Journal of Operational Research, 169: 41-52.
12. Referans12: Kwan MK, 1962. Chinese Postman Problem, Graphic Programming Using Odd or Even Points, Chinese Math., 1: 273-277.
13. Referans13: Lemieux PF, Campagna L, 1984. The snow ploughing problem solved by a graph theory algorithm. Civil Engineering Systems, 1: 337-341.
14. 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.
15. Referans15: Thimbleby H, 2002. Explaining Code For Publication, Software-Practice & Experience.
16. 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.