Запрос алгоритма - несколько драйверов, несколько локаций

Question

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

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

В любой день может занимать до 5-10 рабочих мест, каждый из которых принимает различное количество раз с разным количеством миль.

Я могу получить координаты и расстояние между всеми точками через API Google Distance.

Я хочу рассчитать оптимальное расписание, в соответствии с которым минимизируется пробег/время работы водителя, чтобы максимально полно выполнять ВСЕ задания. Время работы и местоположения фиксированы, однако драйвер может быть любым из пула до 10. Каждый драйвер не обязательно должен выполнять работу каждый день. Некоторые драйверы могут выполнять несколько заданий за один день, если они не перекрываются.

---

Для примера:

Driver Драйвер выходит из точки А в точку Б.

Существует еще одна работа из точки B в тот же день, так что водитель А должен, естественно, быть отнесены к этой работе , так как Водитель A может ждать в точке B до времени начала следующей работы, вместо того, чтобы тратить топливо на другого водителя, чтобы перейти в пункт B с пустой машиной.

---

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

Answer 1

Я постараюсь помочь вам с некоторым псевдокодом планирования. Давай попробуем!

Прежде всего, вам нужна структура планирования с N очередями и слотами M для каждой очереди. У вас должно быть расписание на каждый день, очередь для каждого возможного драйвера и переменное количество слотов.

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

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

С этим вопросом можно справиться без всякого понятия «слоты», но я считаю, что это безопасная мера, чтобы избежать невероятно сурового графика. Этот предлагаемый алгоритм также не касается времени, необходимого для перехода от начальной точки (где загружается грузовик). Я думаю, что у вас может быть справедливое, но не оптимизированное решение, выполнив второй проход по всем расписаниям и добавив необходимые маршруты из и обратно в точку загрузки. Поступая таким образом, вам нужно будет перенести некоторые из последних маршрутов драйверов на другой драйвер, чтобы маршрут «вернуться домой» мог быть положен.

Удачи вам в работе. Надеюсь, что это помогло!