|
This article is cited in 3 scientific papers (total in 3 papers)
Variants of chinese postman problems and a way of solving through transformation into vehicle routing problems
M. K. Gordenko, S. M. Avdoshin National Research University Higher School of Economics
Abstract:
In this article, the routing problems are described. It is shown, that almost all routing problem can be transformed into each other. An example of the Mixed Chinese Postman problem is discussed. The article gives an overview of various variants of Chinese Postman Problem. For all problems the mathematical formulation is given. Moreover, the useful real-life application is presented, too. Then, the article provides a table of possible Chinese Postman problems and identifies parameters that can be varied for obtaining new problems. Five parameters have been identified, such as: presence of set of edges; presence of set of arcs; presence of edges with cost, depending on traversing; the presence of set of required edges; the presence of set of required arcs. It was shown that by varying these parameters one can obtain tasks that were not described earlier but can be used in real life. Four new tasks were identified. Then it is shown that the Chinese Postman problem can be solved as another routing tasks through graph transformations. The method for transforming Chinese Postman problem into the Generalized Travelling Salesman problem is given. Then the results of solving the above problem are presented by simple algorithms, and their effectiveness is shown. The research is not over yet. The testing of other algorithms is planned.
Keywords:
Generalized Routing Problem, Arc Routing Problem, Chinese Postman Problem, Generalized Travelling Salesman Problem.
Citation:
M. K. Gordenko, S. M. Avdoshin, “Variants of chinese postman problems and a way of solving through transformation into vehicle routing problems”, Proceedings of ISP RAS, 30:3 (2018), 221–232
Linking options:
https://www.mathnet.ru/eng/tisp336 https://www.mathnet.ru/eng/tisp/v30/i3/p221
|
Statistics & downloads: |
Abstract page: | 197 | Full-text PDF : | 123 | References: | 21 |
|