|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
The mixed chinese postman problem
[Смешанная задача китайского почтальона]
M. K. Gordenko, S. M. Avdoshin National Research University Higher School of Economics
Аннотация:
Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General Traveling Salesman Problem, GTSP). Указываются варианты CPP. Представлены математические формулировки некоторых проблем. Показан алгоритм редуцирования MCPP в мультиграфе к GTSP. Приводятся экспериментальные результаты решения MCPP в мультиграфе посредством редуцирования к GTSP.
Ключевые слова:
смешанная задача китайского почтальона, задача маршрутизации, эвристический алгоритм, задача коммивояжера.
Образец цитирования:
M. K. Gordenko, S. M. Avdoshin, “The mixed chinese postman problem”, Труды ИСП РАН, 29:4 (2017), 107–122
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp238 https://www.mathnet.ru/rus/tisp/v29/i4/p107
|
Статистика просмотров: |
Страница аннотации: | 316 | PDF полного текста: | 208 | Список литературы: | 30 |
|