The Mixed Chinese Postman Problem
https://doi.org/10.15514/ISPRAS-2017-29(4)-7
Abstract
The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented.
About the Authors
M. K. Gordenko
National Research University Higher School of Economics
Russian Federation
Russian Federation
S. M. Avdoshin
National Research University Higher School of Economics
Russian Federation
Russian Federation
References
1. C. E. Noon and J. C. Bean, "An Efficient Transformation of The Generalized Traveling Salesman Problem," INFOR Information Systems and Operational Research, vol. 31, no. 1, February 1993.
2. H. Thimbleby, "The directed Chinese Postman Problem," Software Practice and Experience, vol. 33, no. 11, pp. 1081-1096, 2003.
3. Mei-Ko Kwan, «Graphic programming using odd or even points» Acta Mathematica Sinica, p. 263–266, 1960.
4. G. Laporte and M. Blais, "Exact Solution of the Generalized Routing Problem through Graph Transformations," Operations Research, vol. 54, no. 8, pp. 906-910, 2003.
5. F. L. Pimentel, «Double-ended nearest and loneliest neighbour–a nearest neighbour heuristic variation for the travelling salesman problem» Revista de Ciências da Computação, т. 6, № 6, 2016.
6. P. Vreda and P. Black, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 2014.
7. G. Laporte, «Modeling and solving several classes of arc routing problems as traveling salesman problems» Computers & operations research, т. 24, № 11, pp. 1057-1061, 1997.
8. S. Bönisch, «Implementierung der Edmonds-Johnson Heuritik für das Mixed Chinese Postman Problem» 21 December 1999.
9. Á. Corberán, "Arc Routing Problems: Data Instances," [Online]. Available: http://www.uv.es/corberan/instancias.htm. [Accessed 3 April 2017].
Review
For citations:
Gordenko M.K., Avdoshin S.M. The Mixed Chinese Postman Problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(4):107-122. https://doi.org/10.15514/ISPRAS-2017-29(4)-7
Email this article 