Algorytm branżowy i cenowy

Question

Czy gałąź i cena mogą być dobrym rozwiązaniem problemu z routingiem z funkcją celu min-max? Na przykład minimalizowanie maksymalnej długości trasy pojazdu w VRP.

W literaturze nigdy nie widziałem, aby to podejście służyło rozwiązaniu takiego problemu. O ile wiem, podejście to służy do rozwiązywania VRP, minimalizując całkowity koszt.

Answer 1

Dobre lub złe podejście będzie zależeć od kilku czynników, na przykład:

• rozmiar instancji
• czas dostępny na znalezienie rozwiązania (jest to zwykle ważna kwestia w zastosowaniach do wyznaczania tras pojazdów)
• moc obliczeniowa
• jaki poziom jakości rozwiązania kwalifikuje się jako dostatecznie dobry

Zobacz tę pracę Yu, Nagarajana i Shena na temat minimalnego czasu pracy na VRP z ograniczeniami kompatybilności, ponieważ jest to podobny problem, który był badany przed użyciem metody rozgałęzienia i ceny jako podejścia do rozwiązania wariantu VRP o maksymalnej długości. Działało całkiem nieźle. Zauważ, że w ich przypadku zaprojektowali algorytm aproksymacji, aby przyspieszyć czas wykonywania B&P.

Proponuję następujący eksperyment:

Pierwszy krok: podążając za odpowiedzią @ RobPratt na Twoje poprzednie pytanie dotyczące minimalizacji długości produkcji w VRP :

Pozwolić $d_i$ być popytem na klienta $i\in N$, pozwolić $V=\{1,\dots,K\}$ być zbiorem pojazdów i niech $P$ być zbiorem kolumn, gdzie każda kolumna odpowiada możliwemu podtourowi zaczynającemu się od magazynu, ze zmiennymi łukowymi $x_{i,j}$ i zmienne węzłów $y_i$. Pozwolić$z$być twórcą. Główny problem się skończył$z$ i $\lambda$wygląda następująco, z podwójnymi zmiennymi w nawiasach: \ begin {align} & \ text {minimum} & 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 {dla$v\in V$} && (\ pi_v \ ge 0) \\ && \ sum_ {v \ in V} \ sum_ {p \ in P} y_i ^ p \ lambda ^ p_v & \ ge 1 && \ text {for $i\in N$} && (\ text {$\alpha_i \ge 0$}) \\ && - \ sum_ {p \ in P} \ lambda ^ p_v & \ ge -1 && \ text {for $v\in V$} && (\ text {$\beta_v \ge 0$}) \\ && \ lambda ^ p_v & \ ge 0 && \ text {for $v\in V$ i $p\in P$} \ end {align}

Podproblem generowania kolumn zakończony $x$ i $y$ dla każdego $v\in V$ to zminimalizowanie obniżonego kosztu $\lambda^p_v$. To znaczy zminimalizuj$$\pi_v \sum_{i,j} c_{i,j} x_{i,j} - \sum_{i \in N} \alpha_i y_i + \beta_v$$ z zastrzeżeniem $(x,y)$ tworząc wykonalny podtour zaczynając od zajezdni, z $\sum_i d_i y_i \le L$, gdzie $L$ to pojemność każdego pojazdu.

Jak tam powiedziano, podproblem można przeformułować jako elementarną najkrótszą ścieżkę: Podziel magazyn na źródło i ujście i przenieś wagi węzłów na łuki: $\pi_v c_{i,j}−\alpha_i$ dla wagi łuku $(i,j)$ w podstawowym problemie najkrótszej ścieżki.

Po drugie: zastosuj powyższą metodę. Polecam spróbować użyć VRPy, zgodnie z sugestią Kuifje tutaj . W ten sposób nie będziesz musiał wykonywać wszystkich operacji branżowych i cenowych od podstaw. Szczegółowe kroki:

1. Zapoznaj się z dokumentacją projektu.
2. Spójrz na kod w GitHub.
3. Utwórz rozwidlenie lub pobierz projekt jako .zip, aby móc wprowadzać zmiany lokalnie.
4. Zmodyfikuj kod dotyczący podproblemu , tak aby skład był podzielony, jak wyjaśniono powyżej.
5. Uruchom eksperymenty, możesz śledzić przykładowe instancje z dokumentacji, takie jak tutaj i tutaj .
6. Daj nam znać, jak to działało. I pamiętaj, aby potwierdzić VRPy i jego twórców w swojej pracy (czy to raport z projektu, praca dyplomowa, publikacja itp.), A także przestrzegać warunków licencji biblioteki w odniesieniu do modyfikacji.

Answer 2

VRPy (v0.3.0) obsługuje teraz tę opcję: wszystko, co musisz zrobić, to ustawić tę minimize_global_spanopcję Truepodczas tworzenia instancji VehicleRoutingProblemobiektu:

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

Oczywiście twój wykres $G$ musi być przede wszystkim dobrze zdefiniowana.

Zaimplementowano sformułowanie zaproponowane przez @RobPratt. Jeśli pobawisz się niektórymi problemami z zabawkami, zobaczysz, że formuła jest słaba w porównaniu do klasycznej (bez rozpiętości). Łatwo zauważyć, że to ograniczenie$$ 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 \ w V.$} $$ jest za to odpowiedzialny.

Możesz również wypróbować następujące alternatywne podejście:

1. Rozwiąż problem bez opcji min_max

2. Zapytaj o największy zakres

3. Rozwiąż ponownie bez min_max, ale ogranicz problem tak, aby każda trasa miała mniejszy rozpiętość niż największa z zapytań w 2.

4. Jeśli nie jest to możliwe, zatrzymaj się, w przeciwnym razie przejdź do kroku 2.

Wszystko to jest proste dzięki ekosystemowi VRPy. Baw się dobrze.