Алгоритм создания столбца
Я хочу решить VRP с помощью алгоритма генерации столбцов. Задача задачи - минимизация сроков изготовления. но есть смысл в вычислении времени прибытия транспортного средства в каждый узел. транспортное средство должно быть синхронизировано с другим видом транспорта, например с поездом, маршрут которого заранее определен до решения вышеупомянутой VRP. поезд может пройти из некоторых узлов, через которые пройдет транспортное средство, и в этих узлах время прибытия является максимальным по сравнению со временем прибытия поезда и транспортного средства. Я хочу знать, как мне решить подзадачу с ценообразованием?
Ответы
Если я правильно понял вашу проблему, то единственное отличие от начальной версии (без шлейфа) в том, что функция времени не аддитивная.
Например, скажем, поезд проходит через узел $j$ в (данное) время $t_j$, и вы вычисляете путь $p$ чей последний узел $i$. Общее накопленное время на этом пути обозначается$\tau_p(i)$. $\Delta t_{ij}$ обозначает время, которое требуется автомобилю, чтобы уехать из $i$ к $j$. Если вы хотите расширить путь и добавить узел$j$, то общее накопленное время пути $p$, $\tau_p$, увеличивается следующим образом: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$
Если поезд прибывает раньше транспортного средства, то общее накопленное время принимает значение $\tau_p(i) + \Delta t_{ij}$, в противном случае принимает значение $t_j$.
Обратите внимание, что это похоже на временные окна на узлах поезда, только с нижней границей: вы можете просто добавить временные окна. $[t_j, +\infty[$ на узле $j$ и запустите свой алгоритм кратчайшего пути с временными окнами (если они у вас есть).
Другими словами, функция увеличения (временного) ресурса не аддитивна. Это обрабатывается, например, cspy , отличной библиотекой Python, которая вычисляет кратчайшие пути с ограничениями ресурсов, где вы можете ввести свое собственное настраиваемое правило расширения ресурсов (ознакомьтесь с документацией, где приводится такой пример). VRPy , библиотека Python VRP для VRP, полагается на cspy для вычисления кратчайших путей для генерации столбцов. Поскольку VRPy обрабатывает временные окна, у вас есть хорошая отправная точка!