• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Transformation of the Mixed Chinese Postman Problem in multigraph into the Asymmetric Travelling Salesman Problem

Maria K. Gordenko, Avdoshin S. M.

The Mixed Chinese Postman Problem (MCPP) is to find a minimum shortest tour of given graph or multigraph traversed each edge or arc at least once. The problem is NP-hard. However, mixed case of the problem has many potentially useful applications, including delivering of something, robot exploration, web site usability, etc. In this article, we propose to solve the problem using the graph transformation and solving well-known Asymmetric Travelling Salesman Problem (ATSP). The algorithm for transforming the MCPP in multigraph into ATSP is pointed out.