Using Genetic Algorithm For Winter Maintenance Operations: Multi Depot K-Chinese Postman Problem

Authors

  • İbrahim Zeki Akyurt
  • Timur Keskinturk
  • Çağatay Kalkancı

DOI:

https://doi.org/10.5195/emaj.2015.69

Keywords:

WINTER MAINTENANCE, GENETIC ALGORITHM, k-CHINESE POSTMAN PROBLEM

Abstract

In this study, the assignment and routing problem of one of Istanbul’s winter maintenance activities, salt pouring, was scrutinized. The starting point of the study considers the high cost of winter maintenance work, a shrinking assigned budget, high numbers of vehicles and streets to service that the increase in difficulty to solve the problem due to their high numbers. In this respect, the problem was modeled as multi depot k-Chinese postman problem, a type of arc routing problem. This mathematical model was solved by genetic algorithm. For comparison, the current solution, Clarke and Wright Algorithm and Sweep Algorithm were used.

References

Ahmetzade, P., Yılmaz, M. ve Yılmaz, M. (2007). Kar ve buz ile mücadele etmek amacıyla geliştirilen daha etkili ve ekonomik yeni yöntemler. 7. Ulaştırma Kongresi Bildiri Kitabı, ss. 186–195, İstanbul: Eylül, 2007.

Ahuja, K. R., Magnatni, T. L. ve Orlin, J. B. (1993). Network flows: Theory, algorithms and applications, Prentice Hall, New Jersey.

Allison E. K. and Bernard N. S. (2004), Effects of highway deicing chemicals on shallow unconsolidated aquifers in Ohio—Final Report, Scientific Investigations Report 2004–5150, p. 199.

Campbell, J. F. and Langevin, A. (1995). Operations management for urban snow removal and disposal. Transportation Research– A, 29 (5): 359–370.

Cook, T. M. and Alprin, B. S. (1976). A snow and ice removal in an urban environment. Management Science, 23: 227–234.

Dali, Z. (2009). Optimization of vehicle routing for plowing and snow disposal. Y. Wang, P. Yi, S. An, H. Wang (Editors). Proceedings of the 9th International Conference of Chinese Transportation Professionals. ICCTP 2009: Critical Issues in Transportation System Planning, Development, and Management, Harbin, China, ss. 2738– 2744.

Eriksson, M. and Norrman, J. (2001). Analysis of station locations in a road weather information system. Meteorological Applications, 8: 437–448.

Fu, L., Trudel, M. and Kim, V. (2009). Optimization winter road maintenance operations under real time information. European Journal of Operational Research, 196: 332¬341.

Golbaharan, N. (2001). An application of optimization to the snow removal problem – A column generation approach. Ph. D. Thesis, Linköping University, Linköping, Sweden.

Gupta, D., Tokar–Erdemir, E., Kuchera, D., Mannava, A. K. ve Xiong, W. (2010). Optimal workforce planning and shift scheduling for snow and ice removal. Technical Report, Industrial and Systems Engineering Program, Department ofMechanical Engineering, University of Minnesota.

Haslam, E. and Wright, J. R. (1991). Application of routing technologies to rural snow and ice control. Transportation Research Record, 1304: 202–211.

Kuloğlu N. and Kök B. V. (2005). Karayollarında kar ve buz mücadelesinde kullanılan tuzun beton asfalt kaplamaya etkisi. Fırat Üniversitesi Fen ve Mühendislik Bilimleri Dergisi, 17 (1): 87–96.

Lemieux, P. F. and Campagna, L. (1984). The snow plowing problem solved by a graph theory algorithm. Civil Engineering Systems, 1: 337–341.

Liebling, T. M. (1973). Routing problems for street cleaning and snow removal. İçinde, Deininger, R. (Editör), Models for environmental pollution control, ss. 363–374.

Marks, H. D. and Strieker, R. (1971). Routing for public service vehicles. ASCE Journal of the Urban Planning and Development Division, 97: 165–178.

Mitchell, M. (1995). Genetic algorithms: An overview. Complexity, 1 (1): 31–39.

Norrman, J., Eriksson, M. and Lindqvist, S. (2000). Relationships between road slipperiness, traffic accident risk and winter road maintenance activity. Climate Research, 15: 185–193.

Perrier, N., Langevin, A. and Amaya, C. A. (2008). Vehicle routing for urban snow plow operations. Transportation Science, 42: 44–56.

Sever, R. (2008). Aşırı kar yağışlarının afete dönüşmesini engellemek için alınması gereken bazı önlemler. 5. Dünya Su Forumu Bölgesel Hazırlık Süreci: DSİ Yurtiçi Bölgesel Su Toplantıları. Kar Hidrolojisi Konferansı Bildiri Kitabı, ss. 173–183.

Sherif, A. and Hassan, Y. (2004). Modelling pavement temperature for winter maintenance operations. Canadian Journal of Civil Engineering, 31: 369-378.

Tucker, W. B. and Clohan, G. M. (1979). Computer simulation of urban snow removal. Transportation Research Board, Special Research Report Number 185, ss. 293–302.

Tuong–Quan V., Hyoung–Seok, K., Hyo, S. C., Doan, N. D. and Byung–Ryong, L. (2009). A study on optimization of fish robot maximum velocity using the combination of genetic – hill climbing algorithm. ICCAS–SICE, ss. 2280– 2285.

Downloads

Published

2015-02-20

Issue

Section

Articles