Proceedings of ISP RAS


The Mixed Chinese Postman Problem

M.K. Gordenko (HSE, Moscow, Russia)
S.M. Avdoshin (HSE, Moscow, Russia)

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.

Keywords

Mixed Chinese Postman Problem, Arc Routing Problem, heuristic algorithm, Traveling Salesman Problem

Edition

Proceedings of the Institute for System Programming, vol. 29, issue 4, 2017, pp. 107-122.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(4)-7

Full text of the paper in pdf Back to the contents of the volume