The Mixed Chinese Postman Problem
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 s...
| 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/316 |
| _version_ | 1818749741152862208 |
|---|---|
| author | M. K. Gordenko S. M. Avdoshin |
| author_facet | M. K. Gordenko S. M. Avdoshin |
| author_sort | M. K. Gordenko |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-18T04:08:36Z |
| format | Article |
| id | doaj.art-8c037a5aeb0a4a07b0fedf873656eb2a |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-18T04:08:36Z |
| publishDate | 2018-10-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-8c037a5aeb0a4a07b0fedf873656eb2a2022-12-21T21:21:31ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262018-10-0129410712210.15514/ISPRAS-2017-29(4)-7316The Mixed Chinese Postman ProblemM. K. Gordenko0S. M. Avdoshin1Национальный исследовательский университет «Высшая школа экономики»Национальный исследовательский университет «Высшая школа экономики»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.https://ispranproceedings.elpub.ru/jour/article/view/316смешанная задача китайского почтальона, задача маршрутизации, эвристический алгоритм, задача коммивояжера |
| spellingShingle | M. K. Gordenko S. M. Avdoshin The Mixed Chinese Postman Problem Труды Института системного программирования РАН смешанная задача китайского почтальона, задача маршрутизации, эвристический алгоритм, задача коммивояжера |
| title | The Mixed Chinese Postman Problem |
| title_full | The Mixed Chinese Postman Problem |
| title_fullStr | The Mixed Chinese Postman Problem |
| title_full_unstemmed | The Mixed Chinese Postman Problem |
| title_short | The Mixed Chinese Postman Problem |
| title_sort | mixed chinese postman problem |
| topic | смешанная задача китайского почтальона, задача маршрутизации, эвристический алгоритм, задача коммивояжера |
| url | https://ispranproceedings.elpub.ru/jour/article/view/316 |
| work_keys_str_mv | AT mkgordenko themixedchinesepostmanproblem AT smavdoshin themixedchinesepostmanproblem AT mkgordenko mixedchinesepostmanproblem AT smavdoshin mixedchinesepostmanproblem |