Как разделить граф на несколько более мелких графов, в которых кратчайшие пути обхода всех вершин были бы примерно одинаковыми?
Другими словами, если есть 100 магазинов и 10 курьеров, как распределить магазины между курьерами, что бы каждый из них прошел примерно одинаковое расстояние?
Задача коммивояжёра, дополненная несколькими курьерами. Не ожидайте найти быстрых, красивых решений NP-полной задачи.
Но, в какой-то мере вам могли бы помочь:
-поиск подходов к выбору курьера для точки на основе динамического программирования.
-предварительное разбиение графа на сообщества по расстоянию.
-любые допустимые упрощения исходных данных (уж не знаю вашей специфики).
Ди Ма, например постараться решить задачу выбора оптимального пути для курьера, близкого к среднему времени по всем курьерам и с таким маршрутом, который минимально "испортит" последующие.
Еще, как вариант, можно попытаться решить задачу по оптимальному выбору следующей точки маршрута и тогда строить маршруты параллельно.
Оговорюсь, это имеет смысл, если мы говорим не о поиске лучшего решения, а о поиске "достаточно хорошего" приближения к лучшему решению.
Простой
Средний
