Аннотация:
Рассматривается подход к снижению сложности NP-трудных задач путём использования структурно близких задач с уже известными решениями. Применяется кластеризация с построением маршрутов внутри кластеров с учётом временных окон в задачах многоагентной маршрутизации. Представлена математическая модель, разбитая на логические блоки ограничений, такие как блок маршрутизации, блок временных ограничений и другие. Показано, как на основе решения близкой задачи маршрутизации формируется решение для исходной задачи. Близость задач определяется по взвешенному метрическому расстоянию между векторами метаэвристических параметров. На выделенном кластере рассматривается евклидова задача коммивояжера (ETSP) — NP-трудная задача комбинаторной оптимизации. Целью является расширение применимости полиномиальных алгоритмов для специальных случаев ETSP, таких как задачи с вершинами, лежащими на выпуклой оболочке, на более общие конфигурации точек. Для этого используется метод попарных сравнений. Результатом является новый эвристический алгоритм с гарантированной абсолютной погрешностью, который состоит из трех этапов. На первом этапе проводится разбиение множества точек на подмножества, образующие вложенные выпуклые многоугольники. На втором этапе решаются подзадачи для каждого многоугольника как специального случая ETSP с линейной сложностью. На третьем этапе осуществляется объединение решений подзадач в единый маршрут. Эксперименты подтверждают гипотезу о близости характеристик у схожих задач и выявляют допустимые границы различий графов. Разработанное программное приложение реализует данный подход для маршрутизации на территории Крыма и включает модуль анализа графов и расширяемую базу данных графовых структур с системой рекомендации метаэвристик.
Полный текст:
PDF файл (11324 kB)