Интересная
задачка у вас:
NP-полная, но при ограничениях реального мира вполне разрешимая.
Коммивояжер ваш имеет ограниченный ресурс по числу пунктов доставки. Доставку, наверно, нужно делать в заданных временнЫх рамках (пока горячая).
Итого ваша задача разбивается на две:
- Распределить заказы между курьерами. Причем какие-то курьеры еще в пути, какие-то в резерве. Скажем, курьеров у вас 7: один в пути далеко, еще один на подходе и трое стоят под загрузкой (плюс двое в резерве на подхвате на случай аврала). Есть поток задач на доставку и нужно распределить их между курьерами максимально эффективно.
- Расставить задачи одного курьера в очередь так, чтобы при обходе точек назначения минимизировать какой-то параметр. Обычно это время, поскольку бензин, расстояние и стоимость проезда вторичны и коррелируют со временем.
Если вы не "веществами" приторговываете, то курьер на задании автономен и не может принять доп-заказы. Отдельная история с "заехать в магаз и купить водки", тут автономность нарушается, но в целом ничего особо не меняет.
Если случай вырожденный, то есть курьеров много, а заказов мало, то и вопроса нет.
Проблемы начинаются когда курьеров много и заказов много.
Для начала я бы провёл кластеризацию адресного пространства. Построил бы матрицу "цены" перемещения между узлами. Вынес бы роутинг на отдельный изолированный слой, чтобы не быть сильно зависимым от конкретного построителя маршрутов.
Можно глянуть, например, в сторону
OSRM.
Я не искал готовых сервисов для решения задачи коммивояжера, а вам стоило бы сперва поискать готовое решение. Саму задачу не обязательно решать полностью и находить максимально эффективный маршрут. Достаточно, чтобы он был достаточно хорошим. В любом случае погрешности прогнозирования пробок и прочих факторов сделают это бессмысленным. Подходы к решению хорошо перечислены на вики по ссылке выше.
Вообще технически можно ещё круче сделать, чтобы один курьер второго мог перехватить по пути и перераспределить с ним часть заказов так, чтобы совокупный расход на перемещение был меньше.
Здесь курьер, получается, может доставлять товар еще и в произвольную точку рандеву другому курьеру.
Если у вас мультимодальная система доставки с пешими и "конными" курьерами, то часть товаров, возможно, будет проще выпускать и развозить по магистрали автомобилем, а пешие гонцы перехватывают грузовик по пути и разносят локально.
Можно попробовать глубже копнуть роевые алгоритмы.
Каждый акт перемещения курьера, приёма/передачи товара (от ресторана курьеру, от курьера курьеру), подготовки заказа в конкретном пункте выдачи - это ветвоение в дереве решений.
Такие ветвления могут быть реальными и потенциальными:
- Реальные необратимы и по своему факту отсекают потенциальные ветки связанные зависимостями.
- Потенциальные ветки имеют свою цену и динамически характеризуются числом зависимостей. Зависимости бывают мягкие и критические: чем большим приростом потенциально цены обернётся отсечение ветки, тем более она критична.
Где тут роевой алгоритм. Можно наплодить виртуальных агентов, которые рандомно (или руководствуясь сигналами нейронной сети) выбирают те или иные ветки из предложенных. Весь рой клубится в потенциальной части дерева решений. Время бежит по пятам и реальные курьеры принимают те или иные решения: система для них выбирает оптимальное действие, или курьер предполагает, что не успеет или форс-мажор и пробка. Стена настоящего времени обрубает недостижимые потенциальные ветки и убивает агентов, которые на них оказались. Это высвобождает ресурсы и дает возможность спаунить новых агентов.
Нейронную сеть агентов можно мутировать в рамках генетических алгоритмов.
Можно взять маркерно-феромонную концепцию муравьиных алгоритмов. Так получится феромонами отмаркировать быстрые маршруты, а когда ситуация изменится и они станут медленными, то эти участки будут перемаркированы сами сорбой следующими агентами. Никто, кстати, не мешает в мультимодальной системе сделать особый вид агентов, которые будут маркировать маршруты для автотранспорта данными от яндекс-пробок. Для пеших агентов можно сделать отдельныз муравьёв разведчиков, которые маркируют по данным тепловой карты Стравы или каких-то локальных сетей сбора пешеходных треков.
Короче, добро поджаловать в логистический адок.
Простой
Простой
