Алгоритм запроса — несколько водителей, несколько местоположений

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

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

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

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

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

Например:

Водитель А едет из пункта А в пункт Б.

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

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


php scheduling algorithm traveling-salesman
person Scott    schedule 27.03.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

person rodrigovr    schedule 27.03.2016
comment
Спасибо! Я попробую, но логика именно то, что я искал. - person Scott; 12.04.2016