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

Maria K. Gordenko, Sergey M. Avdoshin

Abstract


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

Full Text:

PDF

References


V. Bryant and P. David, Decision Maths 1, London: Heinemann Educational Publishers, 2004.

P. Vreda and P. Black, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, 2014.

H. Thimbleby, "The directed Chinese Postman Problem," Software Practice and Experience, vol. 33, no. 11, pp. 1081-1096, 2003.

G. Laporte, "The Undirected Chinese Postman Problem," in Arc Routing, 2013, pp. 53-64.

J. Edmonds and E. Johnson, "Matching, Euler tours and the Chinese postman," Mathematical Programming, vol. 5, no. 1, pp. 88-124, 1973.

T. K. Ralphs, "On the Mixed Chinese Postman Problem," School of Operations Research and Industrial Engineering,, pp. 123-127, 1993.

M. Guan, "On the windy postman problem," Discrete Applied Mathematics, vol. 9, pp. 41-46, September 1984.

A. M. Rodrigues and J. ́. S. Ferreira, "MIC’2001 - 4th Metaheuristics International Conference," in Solving the Rural Postman Problem by Memetic Algorithms, Porto, Portugal, 2001.

G. Ghiani and G. Improta, "An algorithm for the hierarchical Chinese postman problem," Operations Research Letters, no. 26, pp. 27-32, 2000.

D. Mohammaditabar, "Chinese Postman Problem," pp. 224-225, 2013.

U. Derigs, Optimization and Operations Research, Singapore: EOLSS Publications, 2009.

G. Laporte and M. Gendreau, "Arc Routing Problems, Part I: The Chinese Postman Problem," Operations Research, vol. 43, no. 2, pp. 131-242, April 1993.

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.

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.

S. Bönisch, "Implementierung der Edmonds-Johnson Heuritik für das Mixed Chinese Postman Problem," 21 December 1999. [Online]. Available: http://comopt.ifi.uni-heidelberg.de/teaching/praktikum/projekte/mcppHeuristikSebastianBoenisch.tar.gz.. [Accessed 20 April 2017].

A. Corberan, "Arc Routing Problems: Data Instances," [Online]. Available: http://www.uv.es/corberan/instancias.htm. [Accessed 3 April 2017].

K. Helsgaun, "LKH," [Online]. Available: http://akira.ruc.dk/~keld/research/LKH/. [Accessed 9 April 2017].

K. Helsgaun, "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic," European Journal of Operational Research, vol. 126, no. 1, pp. 106-130, 2000.

K. Helsgaun, "Solving Arc Routing Problems Using the Lin-Kernighan- Helsgaun Algorithm," Roskilde University, 2014.

K. Helsgaun, "Solving the Equality Generalized Traveling Salesman Problem Using the Lin-Kernighan-Helsgaun Algorithm," Roskilde University, 2014.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162