Modeling a Multi Depot K- Chinese Postman Problem with Consideration of Priorities for Servicing Arcs


Masoud Rabbani, Setare Mohammadi

Author affiliation

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