: Masoud Rabbani, Setare Mohammadi
: School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
This study deals with the Chinese Postman Problem in critical situation. Critical situation is defined by moving on arcs. One aim of this investigation is visitation of critical edges as soon as possible. The starting points of the study are the high cost of activities, decreased out of priority in servicing arcs, high numbers of vehicles and routes to service. In this respect, the problem was determined as multi depot k-Chinese postman problem, a kind of arc routing problem. This Problem considers three weighted goals. In this study, the optimal number of postman and the optimal path for each of them is determined. This mathematical model was solved by a heuristic algorithm which determines possible routes for each postman then by comparing paths and eliminating expensive ways sets the best route and the best number of postman. For comparison of the current solution, Artificial intelligence algorithms entitled Genetic and Particle swarm were applied.
:Chinese postman problem; genetic algorithm; graph theory; particle swarm optimization algorithm
Masoud Rabbani, Setare Mohammadi, Modeling a Multi Depot K- Chinese Postman Problem with Consideration of Priorities for Servicing Arcs, Advances in Industrial Engineering and Management, vol. 4, no. 2, 2015, pp. 147-156, doi: 10.7508/aiem.2015.02.004
(size: 872.71 kB, pp. 147-156
, Download times:
 M. K. Kwan, 1962. Graphic programming using odd or even points. Chinese Math., vol. 1 1, pp. 110.
 J. Edmonds, 1965. Paths, trees, and flowers. Canadian Journal of mathematics, vol. 17, no. 3, pp. 449-467.
 M. Guan and H. Fleischner, 1983. On the Minimum Weighted Cycle-covering Problem for Planar Graphs. Department of Combinatorics and Optimization, University of Waterloo.
 J. Edmonds and E.L. Johnson, 1973. Matching, Euler tours and the Chinese postman. Mathematical programming, vol. 5, no. 1, pp. 88-124.
 M. Minoux, 1992. Optimal link test patterns in networks and the Chinese postman problem. Cahiers du Centre d'études de recherche opérationnelle, vol. 34, pp. 139-143.
 N. Christofides, et al., 1984. An optimal method for the mixed postman problem. System Modelling and Optimization, vol. 59, pp. 641-649.
 W. L. Pearn, 1994. Solvable cases of the k-person Chinese postman problem. Operations Research Letters, vol. 16, no. 4, pp. 241-244.
 C. Thomassen, 1997. On the complexity of finding a minimum cycle cover of a graph. SIAM Journal on Computing, vol. 26, no. 3, pp. 675-677.
 A. Osterhues and F. Mariak, 2005. On variants of the k-Chinese Postman Problem. Operations Research and Wirtschaftsinformatik, University Dortmund, vol. 30.
 M. Sorge, 2013. Some algorithmic challenges in arc routing. Talk at NII Shonan Seminar, no. 18.
 G. Gutin, G. Muciaccia and A. Yeo, 2013. Parameterized complexity of k-Chinese postman problem. Theoretical Computer Science,vol 513, pp. 124-128.
 İ. Z.Akyurt, T. Keskinturk and Ç. Kalkanci, 2015. Using Genetic Algorithm For Winter Maintenance Operations: Multi Depot K-Chinese Postman Problem. Emerging Markets Journal, vol. 5, no. 1, pp. 50.