列生成アルゴリズム

Aug 23 2020

列生成アルゴリズムを使用してVRPを解決したいと思います。この問題の目的は、makespanの最小化です。ただし、各ノードでの車両の到着時間を計算することにはポイントがあります。車両は、上記のVRPを解決する前に、ルートが事前に決定されている列車などの別の輸送モードと同期する必要があります。列車は、車両が通過するいくつかのノードから通過する場合があり、これらのノードでは、到着時間は列車と車両の到着時間の最大値です。価格設定のサブ問題をどのように解決すればよいか知りたいですか?

回答

5 Kuifje Aug 23 2020 at 16:12

私があなたの問題を正しく理解した場合、最初のバージョン(列車なし)との唯一の違いは、時間関数が加算されないことです。

たとえば、列車がノードを通過するとします。 $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$ 時間枠を使用して最短経路アルゴリズムを実行します(手元にある場合)。

言い換えれば、(時間)リソース拡張関数は加算的ではありません。これは、たとえば、リソース制約付きの最短パスを計算する優れたPythonライブラリであるcspyによって処理されます。ここで、独自のカスタマイズされたリソース拡張ルールを入力できます(このような例が示されているドキュメントを確認してください)。VRPy、VRPのためのVRPのPythonライブラリは、に依存しcspy列生成のための最短経路を計算します。VRPyは時間枠を処理するので、あなたは自分自身に良い出発点を持っています!