Как решить задачу, на оптимальную нагрузку курьера доставки?

Question

[NubasLol]

Есть логистическая задача, где на входе имеем например такие данные.

В течение дня с помощью 3 курьеров нужно развести 20 коробок по 20 адресам из 4 точек. Например в рамках Питера.

И нужно построить оптимальную загрузку курьеров, чтобы они проехали минимальное расстояние и быстрее всего сделали доставку.

Задача решается не в реальном времени, а заранее составляется маршрут для каждого.

Comments

[mayton2019]

Мне кажется это так не решается. В течение дня обстановка на дорогах может менятся. Тоесть маршрут,
построенный утром к обеду может быть не актуален и надо будет все заново перерасчитывать.

Ну к задача коммивояжера - это вроде уже решенная задача в гео-системах.

[rPman]

mayton2019, достаточно решить задачу (в идеале с исходным размещением курьеров и товаров) чтобы затем просто при изменении состояния на дорогах (временных оценках на графах пути) заново запускать алгоритм пересчета

[NubasLol]

rPman, а как решить в упрощённом виде, без учёта трафика?)

[rPman]

перебором ;)
само собой алгоритмов понаделали огромное количество, но это уже ищи сам

[mayton2019]

Не хватает условий. Где курьеры изначально расположены? На базе?

Вечером должны ли они вернуться на базу или могут ехать по своим домам?

Как можно грузить курьера? Может ли он забрать сразу 20 коробок или (на скутере)
он может брать 1-2.

Answer 1

[Wataru]

Это обобщенная задача коммивояжора Multiple Traveling Salesman Problem.

Надо будет построить граф. Взять все точки доставки и склад как вершины и каким-нибудь google maps найти расстояние и пути между каждой парой точек. Эти длины пути надо записать в ребра.

Вообще, это очень сложная задача, как-то легко и быстро не решается. Если допустить не оптимальное решение, а что-то приблизительное, то есть эвристические аппроксимации да не точные методы вроде генетического алгоритма, метода отжига или муравьиного алгоритма (смотрите википедию для обычного коммивояжора). А так - только полный перебор с отсеченями, если у вас будет побольше точек и куръеров.

Если у вас точек и куръеров действительно мало (не более 25 точек, не более 3 куръеров), то можно попробовать решать через динамическое программирование F(M, c1, c2, c3) - минимальная стоимость развезти товары из множества M так, что 3 куръера остаются в вершинах c1, c2 и c3. Переход - перебрать куръера и откуда он пришел из множества M. Посмотрите в википедии алгоритм для одного куръера, на трех это легко обобщается. Будет это работать за O(n^(c+1)2^n), где c - количество куръеров. n - количество вершин в графе. Сильно много куръеров или точек на карте этот алгоритм не переварит.

Answer 2

[rPman]

В течение дня с помощью 3 курьеров нужно развести 20 коробок по 20 адресам из 4 точек. Например в рамках Питера.

Для начала тебе нужно построить граф путей, где вершины - это 20 целевых адресов и 4 исходные точки, а вектора - это оценка (в худшем) времени пути между ними, причем как от складов до адресов так и между адресами. Это тут самая сложная задача, так как исходные данные только карты, где непонятно сколько времени ехать, есть ли зависимость от времени суток и нагруженности курьера.

Если ты курьерская компания уже не первый год на рынке, ты можешь себе позволить собрать статистику по тысячи курьеров (у тебя есть отметки где какой курьер куда приезжал) и составить такие графы для временных периодов 'не должно быть проблемой'.

Ну а дальше комбинаторика, самый тупой метод поиска в глубину решит условно любую задачу, причем найдет оптимальное решение, но максимально неэффективным (с точки зрения затрат на решение) способом, у тебя всего 3 курьера и всего 20 точек, это ниочем.

Есть конечно еще момент, оценка времени перемещения курьера в виде одного числа (например максимум) не является идеальным прогнозом, так как чем больше будет курьеров, тем больше будет простоев из-за того что реальное время перемещения быстрее чем оценка, правильно брать среднее и придерживать какой то процент курьеров про запас, чтобы не увеличивать время ожидания, когда все курьеры 'опаздывают' согласно средней оценки.

Поиск в глубину в данном случае это симуляция перемещения курьеров по развозу товаров заданным порядком, каждый шаг - меняешь порядок нахождения на точке и вычисляешь затраты времени. Если выполнять одновременную симуляцию сразу всех комбинаций, делая это по одному шагу (например шаг по ребру) то выбор на каждом шаге выбирать нужно тот вариант, у которого суммарное время наименьшее, таким образом как только хотя бы один из вариантов закончит развозить коробки, он и будет искомым.