Филиал и алгоритм цены

Question

Может ли ветвь и цена стать хорошим подходом к решению проблемы маршрутизации с целевой функцией min-max? Например, минимизация максимальной длины любого маршрута транспортного средства в VRP.

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

Answer 1

Хороший или плохой подход будет зависеть от нескольких факторов, например:

• размер экземпляров
• время, доступное для поиска решения (это, как правило, важный вопрос в приложениях для маршрутизации транспортных средств)
• вычислительная мощность
• какой уровень качества решения считается достаточно хорошим

См. Эту работу Ю, Нагараджан и Шен о минимальной продолжительности изготовления VRP с ограничениями совместимости, поскольку это аналогичная проблема, которая изучалась до использования ветвей и цен в качестве подхода к решению варианта виртуальной производственной мощности. Это сработало довольно хорошо. Обратите внимание, что в их случае они разработали алгоритм аппроксимации для ускорения времени выполнения B&P.

Предлагаю следующий эксперимент:

Первый шаг: следуя ответу @ RobPratt на ваш предыдущий вопрос о минимизации времени выполнения в VRP :

Позволять $d_i$ быть спросом на клиента $i\in N$, позволять $V=\{1,\dots,K\}$ быть набор транспортных средств, и пусть $P$ - набор столбцов, где каждый столбец соответствует возможному суб-маршруту, начиная с депо, с переменными дуги $x_{i,j}$ и переменные узла $y_i$. Позволять$z$быть мастером. Главная проблема окончена$z$ и $\lambda$выглядит следующим образом с двойными переменными в скобках: \ begin {align} & \ text {minim} & z \\ & \ text {subject to} & z - \ sum_ {p \ in P} \ left (\ sum_ {i, j } c_ {i, j} x_ {i, j} ^ p \ right) \ lambda ^ p_v & \ ge 0 && \ text {для$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {для $i\in N$} && (\ text {$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {для $v\in V$} && (\ text {$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {для $v\in V$ и $p\in P$} \ end {align}

Подзадача генерации столбца закончилась $x$ и $y$ для каждого $v\in V$ затем минимизировать сниженную стоимость $\lambda^p_v$. То есть минимизировать$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ при условии $(x,y)$ формирование возможного субтура, начиная с депо, с $\sum_i d_i y_i \le L$, где $L$ вместимость каждого автомобиля.

Как указано там, подзадача может быть переформулирована как элементарный кратчайший путь: разделите депо на источник и сток и переместите веса узлов на дуги: $\pi_v c_{i,j}−\alpha_i$ для веса дуги $(i,j)$ в элементарной подзадаче поиска кратчайшего пути.

Во-вторых: реализовать вышеуказанный метод. Я рекомендую попробовать использовать VRPy, как предлагает здесь Куифье . Таким образом, вам не придется реализовывать все операции ветвления и цены с нуля. Подробные шаги:

1. Взгляните на документацию по проекту.
2. Взгляните на код в GitHub.
3. Создайте вилку или загрузите проект как .zip, чтобы вы могли вносить изменения локально.
4. Измените код, относящийся к подзадаче , таким образом, чтобы депо было разделено, как было объяснено выше.
5. Запустите эксперименты, вы можете следовать примерам из документации, например здесь и здесь .
6. Сообщите нам, как это работало. И не забудьте поблагодарить VRPy и ее разработчиков за свою работу (будь то отчет о проекте, тезис, публикация и т. Д.), А также за соблюдение условий лицензии библиотеки в отношении модификаций.

Answer 2

VRPy (v0.3.0) теперь поддерживает эту опцию: все, что вам нужно сделать, это установить minimize_global_spanопцию Trueпри создании экземпляра VehicleRoutingProblemобъекта:

prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True)
prob.solve()

Конечно, ваш график $G$ в первую очередь должно быть четко определено.

Формулировка, предложенная @RobPratt, реализована. Если вы поиграете с некоторыми игрушечными задачами, вы увидите, что формулировка слабовата по сравнению с классической (без разминки). Легко видеть, что ограничение$$ z - \sum_{p\in P} \left(\sum_{i,j} c_{i,j}x_{i,j}^p\right) \lambda^p_v \ge 0 \quad \text{ for $v \ in V$} $$ несет ответственность за это.

Вы также можете попробовать следующий альтернативный подход:

1. Решить проблему без опции min_max

2. Запросить самый большой диапазон

3. Решите снова без min_max, но ограничьте проблему так, чтобы каждый маршрут имел меньший интервал, чем самый большой, запрошенный в 2.

4. Если это невозможно, остановитесь, в противном случае перейдите к шагу 2.

Все это просто с экосистемой VRPy. Развлекайся.