Rampy i puste kontenery: dwie publikacje naukowe w naszym planerze

Klasyczny model wyznaczania tras pojazdów sprawdza każdą trasę osobno. Każda trasa ma własną pojemność, własne okna czasowe i własnego kierowcę, a trasy spotykają się dopiero w koszcie całkowitym. Dzięki temu problem da się rozwiązać w rozsądnym czasie. To także powód, dla którego tak wiele zoptymalizowanych planów rozpada się na placu.

Dwie rzeczy w transporcie towarów łamią tę niezależność. Rampa może obsłużyć jedną ciężarówkę naraz, niezależnie od tego, do której trasy ona należy. Pusty kontener zabrany przez jedną trasę nie czeka już na następną. Przyjrzeliśmy się, jak badania operacyjne radzą sobie z obydwoma problemami, i wbudowaliśmy te pomysły w planer, który napędza optymalizator Transportial oraz /vrp/solve.

Rampy: Bombelli i Fazi (2022)

A. Bombelli i S. Fazi badali ciężarówki, które odbierają fracht lotniczy od spedytorów i dostarczają go agentom obsługi naziemnej na lotnisku. Agent obsługi naziemnej rezerwuje dla nich tylko jedną lub dwie rampy. Ich publikacja modeluje to jako problem odbioru i dostawy z oknami czasowymi, w którym przy rampach nie można obsługiwać więcej ciężarówek, niż jest ramp.

Ich heurystyka to adaptacyjne przeszukiwanie dużego sąsiedztwa (ALNS). Każda trasa pozostaje wykonalna sama w sobie, ale plan jako całość może przekroczyć pojemność rampy, za co naliczana jest kara. Po każdym wstawieniu mechanizm rozwiązywania konfliktów przechodzi przez konflikty na rampach w kolejności czasowej. Przy każdym z nich opóźnia ciężarówkę, którą trzeba przesunąć najmniej, co nic nie kosztuje, jeśli ta ciężarówka ma zapas czasu.

Ich wnioski warto znać każdemu, kto planuje pod rampę:

• Bez koordynacji ciężarówki czekały w kolejce nawet około trzech godzin, a niektóre plany stawały się niewykonalne.
• Koordynacja ramp skróciła czas przejazdu o 2 do 19%.
• Druga rampa miała znaczenie głównie dla wykonalności: obie rampy były zajęte jednocześnie przez mniej niż 10% czasu.

Co zbudowaliśmy

Nasz planer prowadzi oś czasu z limitem dla każdego miejsca: rampy, stanowiska załadunkowego, nabrzeża czy bocznicy kolejowej, tak samo dla każdego rodzaju transportu. Oś czasu zawiera pobyty wszystkich tras w planie. Zawiera też to, co jest zajęte spoza planu: inne tripy już obecne w tym miejscu oraz zarezerwowane sloty czasowe na rampach.

Gdy planer wyznacza czasy trasy, przy każdym postoju z limitem sprawdza oś czasu. Obsługa zaczyna się, gdy tylko rampa jest wolna przez cały czas obsługi, o ile okna czasowe nadal na to pozwalają. Oczekiwanie liczy się jako rzeczywiste oczekiwanie: w dniu pracy kierowcy oraz w czasie i koszcie trasy. Każdy postój z limitem to jedno zapytanie, więc sprawdzenie kandydata pozostaje tanie, a plan bez limitów ramp działa dokładnie tak jak wcześniej.

W tym miejscu celowo odeszliśmy od publikacji. Nasze wyszukiwanie żongluje też licznikami czasu jazdy i odpoczynku kierowców, naczepami, komorami i zapasem sprzętu, a przekroczona pojemność rampy czyniłaby każdy z tych czasów niepewnym. Dlatego każdy plan, który przechowuje wyszukiwanie, jest wykonalny pod względem ramp:

• Robienie miejsca. Gdy trasa-kandydat nie może czekać, bo nie zmieściłaby się w czasie, trasy, które stoją jej na drodze, dostają czasy po niej, jeśli nadal się mieszczą. To zasada z publikacji: „ustępuje ciężarówka, którą można przesunąć”. Kandydat płaci za ich dodatkowy czas, a jeśli żadne przesunięcie się nie sprawdza, wstawienie jest odrzucane.
• Mechanizm rozwiązywania konfliktów. Po każdym zaakceptowanym ruchu trasa, która czeka, dostaje rampę jako pierwsza, jeśli trasa, która ją zajmuje, mogłaby poczekać mniejszym kosztem. Zwykle jest to przesunięcie w ramach zapasu czasu, a zamiana zostaje zachowana tylko wtedy, gdy łączny czas obu tras się skraca.
• Stałe rezerwacje. Istniejące tripy i zarezerwowane sloty nigdy się nie przesuwają.

Jeśli wolisz dopuścić przekraczanie pojemności, ustaw regułę dock_capacity na ostrzeżenie. Trasa może wtedy przekroczyć pojemność rampy z kosztem za każdą minutę, a przekroczenie jest raportowane, tak jak w publikacji.

Puste kontenery: Fazi, Choudhary i Dong (2023)

S. Fazi, S.K. Choudhary i J.X. Dong badali przewoźników kontenerowych pracujących z terminalu śródlądowego. Ciężarówka wykonuje kilka przejazdów dziennie, za każdym razem z jednym kontenerem.

• Skąd biorą się puste kontenery. Ładunek eksportowy potrzebuje pustego kontenera: z ograniczonego zapasu terminalu, z właśnie rozładowanego importu (street-turn, czyli bezpośrednie ponowne użycie kontenera, który właśnie został rozładowany, do ładunku eksportowego) albo z odległego depotu kontenerowego.
• Twarde ograniczenie. Zapas pustych kontenerów w terminalu nigdy, w żadnym momencie, nie może spaść poniżej zera. To wiąże ze sobą przejazdy różnych ciężarówek.
• Ich rozwiązanie. Rozwiązują problem dokładnie, metodą branch-and-price. Ograniczenie zapasu jest sprawdzane tylko w „momentach krytycznych”, czyli wtedy, gdy przejazd pobiera pusty kontener, bo zapasu może zabraknąć tylko przy pobraniu jednostki. Objazd do depotu jest wyceniany w ramach łuku grafu, zamiast stawać się dodatkowym postojem.

W rzeczywistych przypadkach z okolic Tilburga i 's-Hertogenbosch ich plany były o 25 do 43% tańsze od planów przygotowanych przez planistów i wymagały mniej przejazdów. Autorzy sprawdzili też, co się dzieje przy trudniejszych warunkach. Mniej okazji do street-turnów podniosło koszty w rzeczywistych przypadkach o 2 do 12%, a rozpoczęcie dnia bez pustych kontenerów w zapasie podniosło je nawet o 27%.

Co zbudowaliśmy

Przesyłka może teraz określić, że potrzebuje jednostki przy załadunku, że zwalnia jednostkę po dostawie, albo jedno i drugie. Jednostką może być pusty kontener, nadwozie wymienne lub naczepa z puli.

Gdy planer buduje trasę, szuka źródła dla każdej potrzebnej jednostki w tej kolejności:

1. Jednostka zwolniona wcześniej na tej samej trasie, jeśli obie przesyłki dopuszczają street-turn, a ciężarówka może ją przewieźć w międzyczasie.
2. Zapas lub depot, który dodaje najmniej kilometrów, z pobraniem po drodze do miejsca załadunku.

Zwolniona jednostka, która nie zostanie ponownie wykorzystana, wraca po dostawie do zapasu leżącego po drodze. Podobnie jak łuki do depotu w publikacji, te wizyty są wyceniane w ramach odcinka jako czas, odległość i koszt, zamiast stawać się postojami.

W skali wszystkich tras jedna księga obejmuje każdy śledzony zapas: jego stan początkowy, znane przyjęcia i wydania oraz pobrania i zwroty każdej trasy. Zgodnie z publikacją księga sprawdza zapas tylko wtedy, gdy pobierana jest jednostka. Pobranie, które sprowadziłoby zapas poniżej zera, przechodzi do kolejnego źródła, a jeśli żadne nie zostało, decyduje reguła equipment_stock. Istniejące tripy liczą się ze swoimi otwartymi pobraniami i zwrotami.

Nie stosujemy metody branch-and-price. Przeszukiwanie dużego sąsiedztwa rozbiera plany na części i składa je na nowo, a usunięcie jednej trasy może zostawić inną bez pustego kontenera, na który liczyła. Dlatego wyszukiwanie nalicza za każdą brakującą jednostkę taki sam koszt jak za pominiętą przesyłkę, a ostatni przebieg znajduje nowe źródło dla wszystkiego, czego nadal brakuje, albo to usuwa. Plan, który otrzymujesz, nigdy nie wysyła dwóch ciężarówek po ostatni pusty kontener na placu.

Gdzie oba mechanizmy się spotykają

Najciekawsze jest miejsce, w którym oba mechanizmy się stykają. Gdy planer zmienia czasy trasy z powodu rampy, moment, w którym ta trasa pobiera lub zwraca kontener, przesuwa się razem z nią. Jeśli zwrot przesunie się za pobranie innej trasy, zapas, który wyglądał dobrze, może nagle okazać się niewystarczający. W naszym planerze trasa z nowymi czasami zabiera ze sobą swój plan sprzętu, więc księga zapasów zawsze odzwierciedla rzeczywiste czasy trasy.

Właśnie dlatego wszystko trafia do jednego wyszukiwania. W osobnych narzędziach nikt by tego nie zauważył. Ekran ramp przesunąłby ciężarówkę, dział pustych kontenerów miałby rację co do porannego zapasu, a plan i tak by się nie powiódł.

Czego nie uwzględniliśmy

• Osobnych ramp załadunkowych i rozładunkowych oraz ramp zarezerwowanych dla określonych typów pojazdów. Wszystkie czynne rampy lokalizacji liczą się razem.
• Pul podwozi kontenerowych. Źródło kontenera jest planowane, ale pula podwozi współdzielona przez ciężarówki już nie.
• Równoważnych typów kontenerów (grup rozmiar-typ ISO) i pojemności placu. Typy muszą się dokładnie zgadzać, a zwroty nigdy nie są odrzucane z powodu pełnego placu.
• Zapasu sprzętu i rozkładowych połączeń kolejowych lub barkowych w jednym zapytaniu. Na razie zaplanuj odcinki drogowe jako przesyłki.

Przeczytaj publikacje

• A. Bombelli i S. Fazi (2022). The ground handler dock capacitated pickup and delivery problem with time windows: a collaborative framework for air cargo operations. Transportation Research Part E 159, 102603.
• S. Fazi, S.K. Choudhary i J.X. Dong (2023). The multi-trip container drayage problem with synchronization for efficient empty containers re-usage. European Journal of Operational Research 310(1), 343–359.

Oparliśmy się na opublikowanych pracach. Autorzy nie brali udziału w naszym projekcie, a za wszelkie niedoskonałości naszej adaptacji odpowiadamy sami. O tym, co jeszcze planer rozstrzyga w tym samym wyszukiwaniu, przeczytasz we wpisie Jedno wyszukiwanie, cały plan transportu. Pola, których należy użyć, opisuje przewodnik po multimodalnym VRP.