Алгоритм Query — несколько драйверов, несколько местоположений
Я, честно говоря, не уверен, где / что опубликовать это, но я буду очень благодарен всем за любые советы, которые вы можете дать.
Я ищу, чтобы создать алгоритм, который будет рассчитывать наиболее оптимальный график для компании такси (частный прокат на дальние расстояния), с несколькими водителями и несколькими заказами.
В любой день может быть около 5-10 рабочих мест, каждая из которых занимает разное количество раз с разным количеством миль.
Я могу получить координаты и расстояние между всеми точками с помощью Google Distance API.
Я хочу рассчитать оптимальный график, при котором пробег / время водителя сводится к минимуму, чтобы выполнить ВСЕ работы максимально эффективно. Время и место работы являются фиксированными, однако драйвер может быть любым из пула до 10. Каждый водитель не обязательно должен выполнять работу каждый день. Некоторые водители могут выполнять несколько заданий в течение одного дня, если они не перекрываются.
Например:
Водитель А едет из пункта А в пункт Б.
Позже в тот же день есть еще одно задание из пункта B, поэтому водителю A следует, естественно, назначить это задание, поскольку водитель A может ждать в пункте B до времени начала следующего задания, а не тратить топливо на то, чтобы другой водитель мог перейти в пункт B. с пустой машиной.
Я пытался быть кратким, извинения за длину. Я не ожидаю полного ответа, но если кто-нибудь попробует подобное, некоторые советы будут оценены!
Решение
Я постараюсь помочь вам с планированием псевдокода. Давай попробуем!
Прежде всего, вам нужна структура планирования с N очередями и M слотами на очередь. У вас должно быть расписание на каждый день, очередь для каждого возможного водителя и переменное количество слотов.
На мой взгляд, я бы разбил день на 15-минутные интервалы. Учитывая эту структуру, алгоритм планирования будет интерактивным процессом, в котором каждое новое взаимодействие будет пытаться выделить новый маршрут.
Первым шагом будет упорядочение всех ожидающих маршрутов с нахождением ближайшей начальной точки для каждой из конечных точек маршрутов. С этим большим потоком упорядоченных маршрутов следующий шаг должен переместить эти маршруты к первому доступному водителю, пока все его слоты в течение дня не заполнены. Вы продолжаете делать то же самое разделение для следующих драйверов, пока не будет запланировано больше поставок.
С такой проблемой можно справиться без понятия «слоты», но я думаю, что это безопасная мера, позволяющая избежать создания сверхжесткого графика. Этот предложенный алгоритм также не имеет отношения к времени, необходимому для перехода от и до начальной точки (где загружен грузовик). Я думаю, что вы можете получить справедливое, но неоптимизированное решение, сделав второй проход по всем графикам и добавив необходимые маршруты от и до точки загрузки. При этом вам нужно будет перенести последний маршрут водителя к другому водителю, чтобы маршрут «обратно домой» мог быть подходящим.
Удачи вам в работе. Надеюсь, что это помогло!
Другие решения
Других решений пока нет …