• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

Some approaches to solving the NP-hard Mixed Chinese Postman Problem

P. 272-290.

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