Omówienie heurystyki See-Saw E. Munapo: jak rozszerza ona metodę dla problemu przydziału na ogólny problem transportowy i dlaczego jej ruchy można liczyć równolegle.
Opracowanie: Artur Łaski na podstawie: E. Munapo, Development of a heuristic to solve the general transportation problem, Eastern-European Journal of Enterprise Technologies, 6/4 (114), 2021, s. 44–51. DOI: 10.15587/1729-4061.2021.243735
O czym jest ta praca
Problem transportowy to jedno z klasycznych zagadnień badań operacyjnych: jak przewieźć towar z kilku źródeł do kilku odbiorców tak, żeby łączny koszt był jak najniższy. Od lat rozwiązuje się go programowaniem liniowym, metodą węgierską, metodą potencjałów (MODI) czy sieciowym simpleksem.
Elias Munapo zwraca uwagę, że te metody mają charakter szeregowy — każdy krok zależy od poprzedniego — więc trudno wykorzystać w nich wiele procesorów jednocześnie. Proponuje heurystykę See-Saw („huśtawka”), która rozszerza wcześniejsze podejście dla problemu przydziału na ogólny problem transportowy i pozwala wykonywać część obliczeń niezależnie, czyli równolegle.
Sformułowanie problemu
Dane są źródła S₁…Sₘ z podażą, odbiorcy D₁…Dₙ z popytem oraz koszty jednostkowe cᵢⱼ przewozu ze źródła i do odbiorcy j:
| D1 D2 ... Dn | Podaż
-------+--------------------+------
S1 | c11 c12 ... c1n | S1
S2 | c21 c22 ... c2n | S2
... | ... ... ... ... | ...
Sm | cm1 cm2 ... cmn | Sm
-------+--------------------+
Popyt | D1 D2 ... Dn |Szukamy ilości xᵢⱼ, które minimalizują łączny koszt:
min Z = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ
przy ograniczeniach:
Σⱼ xᵢⱼ = Sᵢ (podaż każdego źródła)
Σᵢ xᵢⱼ = Dⱼ (popyt każdego odbiorcy)
xᵢⱼ ≥ 0Zadanie jest zbilansowane, gdy suma podaży równa się sumie popytu. Jeśli nie jest, dodaje się fikcyjny wiersz lub kolumnę. Autor przypomina też, że macierz ograniczeń jest unimodularna, więc rozwiązanie optymalne jest całkowitoliczbowe.
Idea ruchu See-Saw
Nazwa pochodzi od huśtawki: gdy jedna strona idzie w dół, druga idzie w górę. W problemie przydziału każda kolumna ma dokładnie jedną alokację, więc przesunięcie w jednej kolumnie wymusza przeciwny ruch w drugiej. W problemie transportowym kolumna może mieć wiele alokacji, dlatego ruch rozważa się osobno dla każdej z nich.
Kolumny łączy się w pary i sprawdza, czy przesunięcie części przewozu między nimi obniży koszt. Do oceny wystarczy porównać sumy krzyżowe — sumy kosztów na przekątnych podmacierzy 2×2 utworzonej przez dwa wiersze i dwie kolumny. Przykładowo dla wierszy 2 i 3 oraz kolumn 1 i 3 porównuje się:
c₂₁ + c₃₃ oraz c₃₁ + c₂₃Ruch jest:
- opłacalny, gdy suma przed ruchem jest większa niż po ruchu — koszt spada,
- nieopłacalny, gdy suma przed ruchem jest mniejsza,
- neutralny, gdy obie sumy są równe — wskazuje to na istnienie rozwiązania alternatywnego o tym samym koszcie.
Ważna zaleta: do oceny ruchu nie trzeba znać przesuwanej ilości. Wystarczą dodawanie i odejmowanie kosztów jednostkowych.
Algorytm
- Wyznacz rozwiązanie początkowe, np. metodą najmniejszego kosztu (Least Cost) lub metodą Vogela (VAM).
- Łącz kolumny w pary, zaczynając od lewej, i wykonuj najlepszy opłacalny ruch See-Saw.
- Powtarzaj, dopóki istnieją ruchy opłacalne. Gdy żaden ruch nie obniża kosztu, rozwiązanie jest optymalne.
Dlaczego to nadaje się do obliczeń równoległych
Ruchy dla różnych par kolumn można oceniać niezależnie od siebie. W przykładzie autora cztery kolumny w pierwszej iteracji można by przypisać czterem osobnym procesorom. To główna przewaga nad metodami klasycznymi — choć autor zaznacza, że na razie jest to możliwość teoretyczna.
Przykład liczbowy z pracy
Autor ilustruje metodę zadaniem z trzema źródłami. Rozwiązanie początkowe wyznaczone metodą najmniejszego kosztu ma sześć alokacji. W pierwszej iteracji:
- w kolumnie 1 ruch jest opłacalny (suma 5 + 17 = 22 jest większa niż 7 + 12 = 19), więc przesuwa się 10 jednostek,
- w kolumnie 2 obie sumy wynoszą 27 — ruch neutralny, czyli istnieje rozwiązanie alternatywne,
- w kolumnach 3 i 4 nie ma ruchów opłacalnych.
Po pierwszej iteracji koszt spada do 1360. W drugiej iteracji nie ma już ruchów opłacalnych, więc rozwiązanie jest optymalne. Rozwiązanie alternatywne ma ten sam koszt 1360. Łącznie wykonano pięć porównań par kolumn.
W tekście pracy koszt rozwiązania początkowego podano raz jako 1390, a raz jako 1370 — z alokacji w tabeli wynika 1390.
Wnioski i ograniczenia
Według autora:
- regułę See-Saw z problemu przydziału można uogólnić na problem transportowy, bo każdy problem transportowy da się przedstawić jako kombinację problemów przydziału,
- w problemie transportowym w jednej kolumnie może być wiele ruchów, więc stosuje się więcej wskaźników na kolumnę,
- niezależność ruchów pozwala skrócić czas obliczeń przez zrównoleglenie.
Autor uczciwie wskazuje główne ograniczenie: brak wyników obliczeniowych dla większych zadań. Metoda została pokazana na jednym małym przykładzie i nie porównano jej czasów działania z metodami klasycznymi.
Komentarz praktyczny
Z perspektywy IT i logistyki praca jest ciekawa przede wszystkim jako kierunek. Planowanie dostaw, rozkład towaru między magazyny czy przydział zleceń do przewoźników to codzienne problemy transportowe, a współczesne serwery mają dziesiątki rdzeni, których metody szeregowe nie wykorzystują. Zanim jednak heurystyka See-Saw trafi do systemów produkcyjnych, potrzebne są testy na zadaniach o realnej skali — setkach źródeł i tysiącach odbiorców — oraz porównanie z dojrzałymi solwerami programowania liniowego.
Źródło
E. Munapo, Development of a heuristic to solve the general transportation problem, Eastern-European Journal of Enterprise Technologies, 6/4 (114), 2021, s. 44–51. DOI: 10.15587/1729-4061.2021.243735 · pełny tekst (PDF)