Новый алгоритм для разбиения дорожных сетей ускорил вычисления в 17 раз
В новой научной работе, опубликованной в архиве arXiv, описана задача edge-based contiguous p-median (ECpM), которая позволяет разбивать дороги сети на заданное число компактных и связных территорий. Такая постановка актуальна для логистического районирования, например при планировании зон обслуживания или оптимизации маршрутов доставки.
Авторы предложили две модели целочисленного программирования с учётом сетевых расстояний. Первая использует экспоненциальное число ограничений на основе разрезов для моделирования связности и решается алгоритмом ветвей и отсечений (branch-and-cut). Вторая модель применяет полиномиальное число ограничений на кратчайшие пути (shortest-path contiguity, SPC) и может обрабатываться стандартными решателями.
Эксперименты проводились на дорожных сетях с более чем 2700 узлами и почти 3400 рёбрами. В моделях использовалось свыше 9,6 миллиона бинарных переменных. Решение модели на основе SPC-ограничений стандартным методом ветвей и границ позволило ускорить вычисления до 17 раз по сравнению с реализацией на базе отсечений.
Кроме того, авторы показали, что SPC-ограничения являются супервалидными неравенствами для модели edge-based p-median (EpM), где связность не требуется явно. Это означает, что они могут отсекать целочисленные допустимые решения, но не все оптимальные решения более простой задачи.
В работе также исследуются структурные связи между ECpM и задачей edge-based districting (EBD), которая добавляет критерий балансировки нагрузки. Существующая модель с ограничениями на основе разрезов не могла найти допустимое решение ни для одного тестового примера в течение 12 часов, тогда как EBD-модель на SPC-ограничениях решала большинство задач до оптимальности.
Практическая значимость работы в том, что новый подход позволяет быстрее решать задачи районирования дорожных сетей, что может быть полезно для логистических компаний, планирования городской инфраструктуры и экстренных служб.
