Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems
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 mathe...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2018-10-01
|
| Series: | Труды Института системного программирования РАН |
| Subjects: | |
| Online Access: | https://ispranproceedings.elpub.ru/jour/article/view/532 |
| _version_ | 1818834318566359040 |
|---|---|
| author | M. K. Gordenko S. M. Avdoshin |
| author_facet | M. K. Gordenko S. M. Avdoshin |
| author_sort | M. K. Gordenko |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-19T02:32:55Z |
| format | Article |
| id | doaj.art-29b5af29a95e4668b73ba982542f0cad |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-19T02:32:55Z |
| publishDate | 2018-10-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-29b5af29a95e4668b73ba982542f0cad2022-12-21T20:39:33ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262018-10-0130322123210.15514/ISPRAS-2018-30(3)-16532Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing ProblemsM. K. Gordenko0S. M. Avdoshin1Департамент программной инженерии, Национальный исследовательский университет “Высшая школа экономики”Департамент программной инженерии, Национальный исследовательский университет “Высшая школа экономики”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.https://ispranproceedings.elpub.ru/jour/article/view/532обобщенная задача коммивояжеразадача маршрутизации дугзадача маршрутизацииобобщенная задача маршрутизациизадача китайского почтальона |
| spellingShingle | M. K. Gordenko S. M. Avdoshin Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems Труды Института системного программирования РАН обобщенная задача коммивояжера задача маршрутизации дуг задача маршрутизации обобщенная задача маршрутизации задача китайского почтальона |
| title | Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems |
| title_full | Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems |
| title_fullStr | Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems |
| title_full_unstemmed | Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems |
| title_short | Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems |
| title_sort | variants of chinese postman problems and a way of solving through transformation into vehicle routing problems |
| topic | обобщенная задача коммивояжера задача маршрутизации дуг задача маршрутизации обобщенная задача маршрутизации задача китайского почтальона |
| url | https://ispranproceedings.elpub.ru/jour/article/view/532 |
| work_keys_str_mv | AT mkgordenko variantsofchinesepostmanproblemsandawayofsolvingthroughtransformationintovehicleroutingproblems AT smavdoshin variantsofchinesepostmanproblemsandawayofsolvingthroughtransformationintovehicleroutingproblems |