Algorytm generowania kolumn

Question

Chcę rozwiązać VRP za pomocą algorytmu generowania kolumn. Celem problemu jest minimalizacja czasu trwania. ale jest sens obliczać czas przybycia pojazdu do każdego węzła. pojazd musi być zsynchronizowany z innym środkiem transportu, takim jak pociąg, którego trasa jest z góry określona przed rozwiązaniem wspomnianego wyżej VRP. pociąg może przejechać z niektórych węzłów, przez które przejedzie pojazd, iw tych węzłach czas przyjazdu to maksymalny czas przyjazdu pociągu i pojazdu. Chcę wiedzieć, jak mam rozwiązać podproblem cenowy?

Answer 1

Jeśli dobrze zrozumiałem twój problem, jedyną różnicą w stosunku do wersji początkowej (bez pociągu) jest to, że funkcja czasu nie jest addytywna.

Na przykład, powiedzmy, że pociąg przejeżdża przez węzeł $j$ o (podanym) czasie $t_j$, i obliczasz ścieżkę $p$ którego ostatni węzeł to $i$. Całkowity czas na tej ścieżce jest oznaczony przez$\tau_p(i)$. $\Delta t_{ij}$ oznacza czas potrzebny na odjazd pojazdu $i$ do $j$. Jeśli chcesz przedłużyć ścieżkę i dodać węzeł$j$, a następnie łączny czas na ścieżkę $p$, $\tau_p$, zwiększa się w następujący sposób: $$ \tau_p(j) := \max\{ t_j, \tau_p(i) + \Delta t_{ij} \} $$

Jeśli pociąg przyjedzie przed pojazd, wówczas wartość nabiera łącznego czasu $\tau_p(i) + \Delta t_{ij}$w przeciwnym razie ma wartość $t_j$.

Zauważ, że to jest jak posiadanie okien czasowych w węzłach pociągu, z tylko dolną granicą: możesz po prostu dodać okna czasowe $[t_j, +\infty[$ na węźle $j$ i uruchom algorytm najkrótszej ścieżki z oknami czasowymi (jeśli masz je pod ręką).

Innymi słowy, funkcja rozszerzenia zasobów (czas) nie jest addytywna. Jest to obsługiwane na przykład przez cspy , świetną bibliotekę Pythona, która oblicza najkrótsze ścieżki z ograniczeniami zasobów, gdzie możesz wprowadzić własną niestandardową regułę rozszerzania zasobów (sprawdź dokumenty, w których podano taki przykład). VRPy , biblioteka VRP w Pythonie dla VRP, opiera się na cspy do obliczania najkrótszych ścieżek do generowania kolumn. Ponieważ VRPy obsługuje okna czasowe, masz dobry punkt wyjścia!