26 тысяч приёмов пищи в день с доставкой?
Логистика доставки такого объёма — задача непростая. Мы исходим из того, что наши водители-волонтёры могут перевозить 15 рационов, то есть 30 приёмов пищи за одну поездку, и предоставляем им оптимизированные маршруты. Тем не менее, одна такая поездка занимает у них около 1,5–2 часов, что, по нашему мнению, является устойчивой нагрузкой при работе 2–3 дня в неделю для наших волонтёров.
Для нас 26 тысяч приёмов пищи означают 13 тысяч рационов. Мы предполагаем, что это потребует примерно 7 тысяч остановок (около 2 рационов на остановку). При использовании волонтёрских водителей и обычных автомобилей для доставки это потребовало бы 700 водителей, работающих ежедневно, то есть на практике около 2000 водителей (поскольку наши волонтёры не готовы ездить каждый день).
Если вы контролируете источник приготовления пищи (мы сами не готовим еду, поэтому для нас это гораздо сложнее), то вам достаточно разделить список адресов между водителями и оптимизировать каждый маршрут. Наш объём значительно меньше вашего (мы планируем 2–3 тысячи приёмов пищи в день, что составляет 1/10 от вашего), поэтому мы не автоматизируем разделение списка адресов. Каждый адрес доставки относится к определённому району, а наши диспетчеры вручную распределяют список доставки по районам (это делается простым сортированием в электронной таблице). Затем мы оптимизируем маршрут каждого водителя через веб-сервер, работающий на AWS, и предоставляем каждому водителю оптимизированный маршрут (простой алгоритм задачи коммивояжёра).
Мы рассматривали возможность автоматического разделения полного списка адресов. Но пока в этом нет необходимости, и у нас не так много денег, поэтому мы хотим минимизировать расходы на AWS и Google Maps API :-). Для обобщённой задачи маршрутизации нескольких транспортных средств существуют простые алгоритмические решения, например, вот здесь:
Однако, учитывая такое количество доставок, я предполагаю, что вы охватываете очень большую географическую область, поэтому, возможно, вам также нужно учитывать домашние адреса водителей, что выводит задачу за рамки стандартной задачи маршрутизации транспортных средств (VRP). Возможно, простые эвристики позволят разделить группы водителей и адреса доставки на подзадачи, где и доставки, и водители находятся в одной географической зоне; в этом случае вы снова сможете использовать готовое решение VRP.
Кстати, мы используем продолжительность поездки по данным GMap в качестве расстояния между точками.