Я работал над проектом планирования маршрута, и у меня возникли проблемы при разработке оптимального алгоритма планирования / планирования пути, который работает при определенных ограничениях, а именно, что путь должен останавливаться в определенном узле в данный момент времени.Я построил формулировку проблемы следующим образом:
Маршрут имеет время начала и окончания (t s и t e ) и состоит из действий {а 1 ... а п }.Каждое действие a i имеет время начала t i и продолжительность d i .Первое действие не обязательно должно начинаться в момент времени t s .
. Кроме того, между каждым мероприятием существует стоимость поездки.Я представляю стоимость поездки в матрице смежности C, где C [i] [j] - это стоимость поездки от i до j .
Вот где это становится сложным.Существует одно такое действие a f ∈ {a 1 ... a n } такое, что t f фиксировано - действиедолжен начинаться в момент времени t f .В то же время мы хотим максимально сократить время в пути.Я знаю, что есть алгоритмы, чтобы найти кратчайший гамильтонов путь, который я уже использовал, чтобы найти оптимальный порядок.Проблема возникает, когда оптимальный порядок не позволяет начать фиксированную деятельность в требуемое время, поскольку она конфликтует с временем начала / окончания маршрута.
Существует ли эффективный алгоритм для нахождения оптимального порядка, которыйвсе еще выполняет ограничение на активность a f ?
Количество узлов не будет превышать около 6 или 7. Таким образом, я не чрезмерно , связанный с ростом времени выполнения, но все же хочу избежать поиска методом перебора, если это возможно.