Optymalizacja załadunku palet na ciężarówki

Problem

Żyjemy w czasach globalizacji światowej gospodarki. Surowce wydobywa się w jednej części globu, przetwarza w drugiej a gotowy wyrób sprzedaje jeszcze gdzie indziej. Taka organizacja umożliwia zmaksymalizowanie zysków, jednak rodzi także problemy. Jednym z nich jest zagadnienie przewiezienia wszystkich materiałów i produktów. Duże ilości towarów transportuje się ciężarówkami lub kontenerami (np. na statkach). Każdy przewoźnik chce oczywiście zmaksymalizować załadowanie ciężarówek, aby optymalnie wykorzystać dostępną ładowność. Tu pojawia się problem, w jaki sposób zapakować konkretny zestaw palet na "TIR'a", aby cały się zmieścił? Czy w ogóle da się przewieźć dany transport jednym kontenerem?

Specyfikacja

Zadanie stawiane przed programem wygląda więc następująco: dla zadanego zestawu palet (podane wymiary: szerokość x długość x wysokość) i wielkości ładowni (podane wymiary: szerokość x długość x wysokość) stwierdzić czy da się załadować wszystkie paczki, a jeśli nie to ile da się maksymalnie. Ponadto należy podać sposób rozmieszczenia towarów w ciężarówce.

Analogiczne programy

Istnieje kilka programów dla firm spedycyjnych rozwiązujących to lub podobne zadanie. Niestety wszystkie, które udało mi się znaleźć, są aplikacjami komercyjnymi o zamkniętych źródłach, np.:

• MaxLoad Pro
• CargoWiz

Ponadto autorzy nie opublikowali nigdzie informacji dotyczących użytych przez nich algorytmów. Uniemożliwiło mi to porównanie zastosowanych rozwiązań. Na szczęście drugi z wymienionych programów dostępny jest w użytecznej darmowej wersji demonstracyjnej, dzięki czemu mogłem porównać wyniki i jakość rozwiązań z moim programem.

Podstawy teoretyczne

Z teoretycznego punktu widzenia przedstawiony problem jest przykładem Problemu spełnialności więzów (ang. Constraint Satisfaction Problem), o którym więcej można przeczytać np. w rozdziale 5 książki "Artificial Intelligence: A Modern Approach" Stuart Russell, Peter Norvig. Istnieje wiele sposobów rozwiązywania tego problemu, jednak w ogólności jest on NP-trudny.

Zastosowane metody rozwiązania

Problem rozwiązałem na kilka sposobów.

Constraint Satisfaction Problem

Najpierw przestudiowałem różne materiały dotyczące rozwiązywania CSP (m.in. notatki z wykładu i wspomnianą wcześniej książkę "Artificial Intelligence: A Modern Approach"). Aby problem miał postać CSP przyjąłem, że zmienne to pozycje paczek (jedna zmienna zawiera 3 współrzędne w przestrzeni), więzy natomiast zachodzą parami pomiędzy wszystkimi paczkami (więz jest spełniony gdy dwie paczki nie zachodzą na siebie). Dziedziną dla każdej paczki były wszystkie możliwe położenia, w których paczka ta znajdowała się wewnątrz ciężarówki. Dzięki takiej reprezentacji zadania wszystkie więzy są binarne, co ułatwia rozwiązywanie problemu.
Następnie wybrałem kilka powszechnie znanych metod. Ogólnie wszystkie one opierają się na procedurze (Recursive Backtracking) rekurencyjnie próbującej nadać wartości kolejnym nieprzypisanym zmiennym, zachowując spójność podstawienia. Jeśli w pewnym momencie dalsze podstawianie jest niemożliwe, procedura wycofuje się i próbuje podstawić inną wartość poprzedniej zmiennej. Metody różnią się sposobami (i kolejnością!) wyboru zmiennej do podstawienia oraz wartości dla tej zmiennej.
Pierwsza metoda nadaje wartość pierwszej (w kolejności wprowadzenia danych) wolnej zmiennej podstawiając pod nią po kolei wszystkie możliwe wartości z jej dziedziny. Następnie sprawdza czy takie podstawienie jest spójne.
Druga metoda różni się tym, że na początku sortuje zmienne w ten sposób, że najpierw próbuje konkretyzować zmienne reprezentujące największe palety. Jest to moja modyfikacja. Kierowałem się spostrzeżeniem, że prościej najpierw wstawić duże paczki a potem "upchać" małe niż na odwrót.
Trzecia metoda wykorzystuje zasadę wcześniejszego przypisywania wartości tym zmiennym które da się ukonkretyzować na najmniejszą, w danej chwili, liczbę sposobów (ang. Minimum Remaining Values). Zastosowane jest tutaj przycinanie dziedzin, zwane także propagacją więzów.
Dla prostych (duża ładownia, mało towaru) lub małych (mała ciężarówka - małe dziedziny) przykładów metody te były wystarczające. Poszukiwałem jednak algorytmów działających szybciej (być może mniej dokładnie - nie znajdujących optymalnego załadunku) dla trudnych przypadków.

Best-First i Hill Climbing

Spośród innych algorytmów interesujące były algorytmy przeszukiwania przestrzeni stanów. Najpopularniejsze z nich to przeszukiwanie grafu stanów w szerz (ang. Breadth First Search) i w głąb (ang. Depth First Search) oraz ich modyfikacje. Algorytm BFS nie nadawał się do moich zastosowań z powodu olbrzymich wymagań pamięciowych (które w moim problemie zajęłyby prawdopodobnie więcej bajtów pamięci niż jest atomów we wszechświecie) oraz praktycznie identycznej złożoności przypadku najlepszego i średniego (na który nie doczekałoby się do końca świata). Algorytm DFS z kolei oferuje bardzo dobry czas dla przypadku optymistycznego. Niestety przypadek średni i najgorszy wyglądają podobnie jak w BFS. Chcielibyśmy aby nasz program działał zazwyczaj w czasie bliskim optymistycznego. W tym celu można wykorzystać modyfikacją DFS zwaną Best-First, tzn. przeglądamy graf w głąb wybierając do rozwijania potencjalnie najlepszego kandydata. Aby móc go wybrać potrzebne były dodatkowe informacje (być może szacunkowe) o problemie - funkcje heurystycznej oceny stanu. Rozważałem kilka takich funkcji. Ostatecznie zdecydowałem się na funkcję, która przyjmuje wartość ilorazu sumarycznej objętości niezapakowanych palet przez minimum z wielkości przyciętych dziedzin tych palet (czyli liczbę sposobów, na które aktualnie można włożyć najtrudniejszą do zapakowania paletę). Im mniejsza wartość funkcji tym lepsza ocena stanu. Heurystyka ta jest o tyle dobra, że jednocześnie promuje wcześniejsze pakowanie dużych palet oraz takich paczek które najmniej przytną minimalne dziedziny (czyli prawdopodobnie zostaną zapakowane w jakąś niedużą przestrzeń gdzie niewiele innych towarów by się zmieściło).
Przeglądanie przestrzeni stanów zaczyna się od sytuacji, gdzie żadna paleta nie jest zapakowana, a kończy gdy wszystkie są w ciężarówce. Nie interesuje nas przestawianie palet w samochodzie, dlatego też przyjąłem, że w każdym ruchu operator bierze jedną paczkę i wstawia je w jakieś miejsce w kontenerze, na którym zostaje ona już do końca. Takie podejście sprawia, że każda ścieżka prowadząca do rozwiązania ma długość równą ilości palet. Jak widać w tym przypadku nie ma zastosowania algorytm A*, który polega na minimalizowaniu długości ścieżki do rozwiązania.
W algorytmie Best-First można wybierać stan który ma najlepszą ocenę wśród dzieci aktualnego stanu lub wśród wszystkich rozwiniętych do te pory stanów. Drugie podejście jednak odrzuciłem, gdyż nawet na optymalnej ścieżce moja funkcja nie musi monotonicznie maleć (choć można by próbować ją modyfikować aby zachodziła taka własność). Ponadto ilość pamięci potrzebna do przechowywania informacji o wszystkich do tej pory rozwiniętych stanach byłaby nie do zaakceptowania. Tym sposobem zdecydowałem się na zastosowanie algorytmu gradientowego (ang. Hill Climbing), czyli w każdym kroku wybieram najlepszą (wg. heurystycznej oceny stanu) drogę.
Zrealizowałem dwa warianty przedstawionej metody różniące się sposobem wyboru najlepszego operatora w każdym kroku. Pierwszy z nich dla każdej niewstawionej paczki, wstawia ją w każde możliwe miejsce i wylicza heurystyczną ocenę. Drugi wybiera paczkę do wstawienia zgodnie z zasadą MRV, a następnie wstawia ją w każde możliwe miejsce i ocenia powstały stan. Możliwe miejsca wstawienia paczek ograniczyłem do rogów (utworzonych przez inne paczki lub ściany kontenera), gdyż paczkę stojącą nie w rogu zawsze można dosunąć do niego nie tracąc ogólności. W obu przypadkach najlepiej oceniony stan jest realizowany i pętla się powtarza. Należy zauważyć, że druga metoda jest bardzo podobna do algorytmu rozwiązywania CSP ze sposobem wyboru zmiennej na zasadzie MRV oraz sposobem wyboru wartości, która najmniej przytnie inne dziedziny (ang. Least Constraining Value).

Implementacja

Jak wspominałem już wcześniej nie znalazłem, żadnych narzędzi o otwartych źródłach lub chociażby zawierających opisy zastosowanych algorytmów. Napisałem więc odpowiedni program samemu. Rozważany problem cechuje się bardzo dużą złożonością, a wymyślone algorytmy potrzebują specyficznych rozwiązań, struktur danych itp. Zdecydowałem się więc napisać program w "szybkim" języku C++. Większość kodu napisana jest strukturalnie co zapewnia szybkość, ale wykorzystałem także udostępniany model obiektowy aby stworzyć typy danych wyższego poziomu, na których łatwiej operować.
Zbudowałem struktury danych reprezentujące: zmienną (pozycję palety w trójwymiarowej przestrzeni), przypisanie (wartości do zmiennych), domenę (zawierającą informację które wartości do niej należą a które zostały wycięte i przez jaką zmienną), zmodyfikowane drzewo ósemkowe (do reprezentacji zachodzących na siebie obszarów 3D), problem CSP (zawierający wymiary palet i ciężarówki), itp. Klasy te wyposażyłem w niezbędne im metody (tj. przypisanie wartości zmiennej w podstawieniu, przycięcie domeny o odpowiednie pole, pobranie następnej wolnej wartości dla zmiennej i wiele innych).
Najważniejsza część algorytmiczna zawarta jest jednak w funkcjach rekurencyjnie wywołujących się (Recursive Backtracking w różnych wersjach) i realizujących przedstawione w poprzednim akapicie metody rozwiązania problemu. Wykorzystują one powyższe klasy, dynamicznie tworząc potrzebne obiekty. Dodatkowo w celu wizualizacji napisałem kilka funkcji wykorzystujących bibliotekę OpenGL. Umożliwiają one obejrzenie wyniku działania programu, czyli ułożenia palet w ciężarówce, z każdej strony w środowisku 3D.
Zaimplementowane przeze mnie algorytmy przeszukują przestrzeń stanów. Aby móc w skończony sposób reprezentować stan, zdecydowałem, że wielkość palet i ciężarówki będę podawał z dokładnością do 5 cm.

Przykłady działania programu

Program przetestowałem najpierw na kilku zestawach danych syntetycznych, aby sprawdzić jego poprawność i wyłapać błędy. Były to raczej małe przykłady, np. aby sprawdzić czy zostanie zapakowany zestaw w pełni zajmujący ładownie uruchomiłem program dla:
kontenera (3, 3, 3),
palet (3, 1, 3), (2, 2, 2), (1, 2, 3), (2, 2, 1),
wymiary (szerokość, długość, wysokość) w umownych jednostkach.
Wszystkie wersje oczywiście poradziły sobie z tym zadaniem bardzo szybko (poniżej 1 sekundy). Co ciekawe, nawet dla tak trywialnego przypadku dały różne (możliwe i poprawne) wyniki.

Bardziej interesujące są jednak prawdziwe dane, które udało mi się uzyskać od jednej z firm transportującej tirami palety różnych rozmiarów. Poniższe zestawy są prawdziwym spisem palet, który w firmie załadowano na ciężarówkę rozmiarów 2,6 m (wysokość) x 2,45 (szerokość) x 13,6 (długość).
Zestaw 1 (44 palety):
(80, 95, 180) x 28 sztuk
(110, 100, 95) x 12 sztuk
(120, 120, 85) x 2 sztuki
(80, 220, 40) x 1 sztuka
(110, 110, 120) x 1 sztuka
O dziwo najprostsza wersja programu poradziła sobie z tym problemem bardzo szybko (2 sekundy):

...był to jednak przypadek bo po zmianie kolejności, w której podano dane, program utknął nie zwracając wyniku w sensownym czasie.
Podobnie niestety zachowywały się pozostałe dwie wersje bazujące na ogólnych metodach rozwiązywania problemów CSP. Jedna z nich w sensownym czasie zapakowała 40 paczek, a druga 42.
Bardzo dobre wyniki dały za to obie metody wykorzystujące funkcję heurystyczną. Wariant oceniający wszystkie możliwe operatory w każdym ruchu zakończył pracę w 356 sekund, a oceniając tylko podstawienia dla zmiennej mającej najmniej możliwości drugi wariant trwał tylko 16 sekund. Oba zapakowały wszystkie palety, acz w nieco inny sposób.
Wariant 1:

Wariant 2:

Zestaw 2 (47 palet):
(90, 135, 120) x 11 sztuk
(100, 125, 100) x 10 sztuk
(115, 115, 95) x 9 sztuk
(120, 120, 110) x 8 sztuk
(125, 250, 40) x 2 sztuki
(80, 120, 85) x 2 sztuki
(120, 120, 85) x 2 sztuki
(115, 130, 120) x 2 sztuki
(100, 120, 65) x 1 sztuka
Tego zestawu nie udało się zapakować żadnemu algorytmowi. Trzy pierwsze wersje w sensownym czasie zapakowały odpowiednio 40, 43 i 39 paczek. Wersja programu wykorzystująca funkcję heurystyczną w wariancie sprawdzającym wszystkie możliwe operatory zapakowała 43 paczki w 981 sekund a w wariancie ograniczonym do operatorów podstawiających wartości pod zmienną z najmniejszą liczbą możliwych podstawień zapakowała 40 paczek w 32 sekundy.
Wariant 1:

Wariant 2:

Omówienie wyników

Tabelka przedstawia działanie programu w 5 wariantach dla 3 przedstawionych powyżej przykładów (inne przeprowadzone przeze mnie testy nie wnoszą nic nowego).

Program może układać paczki na 5 sposobów. Pierwsze 3 są ogólnymi metodami rozwiązywania problemów CSP i w teorii zawsze zwracają wynik, jeśli taki istnieje. W praktyce jak widać dla większych zadań w ogóle się nie zatrzymują, a podglądając ich wyniki częściowe widać, że brakuje im ok. 4-8 palet do załadowania zestawu, z którym poradził sobie człowiek. Po przeprowadzeniu większej ilości testów zauważyłem, że zgodnie z oczekiwaniami wersja stosująca zasadę MRV jest trochę lepsza od wersji stosującej sortowanie na początku. Jest to całkiem sensowne, gdyż początkowe sortowanie jest strategią MRV zastosowaną w pierwszym kroku a później porzuconą. Algorytm RB bez żadnych ulepszeń jest mocno uzależniony od kolejności wprowadzania danych, przez co daje bardzo niestabilne wyniki (dla niektórych zestawów świetne, ale dal większości bardzo złe).
Dwie ostatnie metody wykorzystują funkcję heurystyczną i nie sprawdzają wszystkich możliwych położeń paczek. Więc teoretycznie nie zawsze muszą umieć zapakować wszystkie paczki, nawet jeśli jest to możliwe. W praktyce jednak zawsze się zatrzymują w sensownym czasie i zazwyczaj dają dobre wyniki (ładują cały towar lub jego zdecydowaną większość). Algorytm wybierający zmienną do podstawienia strategią MRV, a wartość dla niej przy pomocy funkcji heurystycznej H1 jest bardzo szybki, choć czasami daje trochę gorsze wyniki niż pełny przegląd operatorów przy pomocy funkcji H1. Co ciekawe przetestowany przeze mnie program komercyjny w jednym z rzeczywistych przypadków nie poradził sobie z załadunkiem, który potrafiły wykonać 2 moje algorytmy (wykorzystujące heurystykę), a w drugim prawdziwym przykładzie dały taki sam wynik jak lepszy z moich algorytmów.

Wnioski

Problem optymalnego (lub nawet bliskiego optymalnemu) załadunku ciężarówki paletami różnej wielkości jest trudny. Nie jest to łatwe zadanie dla człowieka (co wynika z informacji otrzymanej od firmy zajmującej się transportem) i jak widać nawet duża moc obliczeniowa nie wiele może tu pomóc. Zaimplementowane przeze mnie algorytmy otrzymywały rezultaty podobne do ludzkich lub nieco gorsze. Uważam, że wprowadzając do nich kilka poprawek (np. lepsze funkcje heurystyczne, możliwość układania palet wszerz lub wzdłuż - obracania) program ma szanse osiągnąć poziom doświadczonego w tej dziedzinie człowieka. Nie polepszy to może uzyskiwanego "stopnia upakowania" palet, ale może zautomatyzować proces planowania załadunku, przyspieszając go lub obniżając koszty, co także jest wartościowe.
Szczególnie dobre wyniki uzyskiwałem uruchamiając 2 wersje programu wykorzystujące funkcje heurystyczne, z których jedna dodatkowo była całkiem szybka. Można by zmodyfikować program tak, aby uruchamiał najpierw wariant 2, a jeśli nie uda się zapakować nim wszystkiego włączał wariant 1. Widać jaki potencjał drzemie w funkcjach heurystycznych (zwłaszcza jeśli zależy nam na czasie działania, a godzimy się na niewielkie pogorszenie jakości wyniku).

Materiały

1. książka: "Artificial Intelligence: A Modern Approach" Stuart Russell, Peter Norvig - szczególnie rozdział 5 dotyczący CSP;
2. slajdy: "Metody przeszukiwania" Witold Paluszyński;
3. Slajdy z przeszukiwania ślepego Uniwersytetu Rensselaer;
4. Slajdy z przeszukiwania poinformowanego Uniwersytetu Rensselaer;
5. Slajdy z przeszukiwania do książki: "Computational Intelligence: A Logical Approach" Poole, Mackworth, Goebel:
   • część 1,
   • część 2,
   • część 3,
   • część 4,
   • część 5,
   • część 6.