Сборники трудов ИСП РАН


Смешанная задача китайского почтальона

М.К. Горденко (ВШЭ, Москва, Россия)
С.М. Авдошин (ВШЭ, Москва, Россия)

Аннотация

Задачи маршрутизации важны для областей логистики и управления трансортом. Задачи маршрутизации в основном связаны с определением оптимального набора путей в мультиграфе. Задача китайского почтальона (CPP) является особым случаем задачи маршрутизации, имющим много потенциальных приложений. Мы предлагаем решение MCPP (специального NP-полного случая CPP на смешанном мультиграфе) с использованием редуцирования исходной задачи к обобщенной задаче коммивояжера (General Traveling Salesman Problem, GTSP). Указываются варианты CPP. Представлены математические формулировки некоторых проблем. Показан алгоритм редуцирования MCPP в мультиграфе к GTSP. Приводятся экспериментальные результаты решения MCPP в мультиграфе посредством редуцирования к GTSP.

Ключевые слова

смешанная задача китайского почтальона, задача маршрутизации, эвристический алгоритм, задача коммивояжера

Издание

Труды Института системного программирования РАН, том 29, вып. 4, 2017, стр. 107-122.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(4)-7

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома