Problem z alokacją nabrzeża - Berth allocation problem

Problemem alokacji kuszetka (znany również jako problemu harmonogramowania cumowania) jest NP-zupełny problem w badaniach operacyjnych , w odniesieniu do alokacji przestrzeni miejsc do cumowania statków w terminalach kontenerowych . Statki przybywają z czasem i operator terminalu musi przydzielić je do nabrzeży w celu jak najszybszej obsługi (załadunku i rozładunku kontenerów). Różne czynniki wpływają na przydział do cumowania i czas każdego statku.

Wśród modeli znalezionych w literaturze można wyróżnić cztery najczęściej obserwowane przypadki:

1. dyskretna vs ciągła przestrzeń do cumowania,
2. przyloty statyczne vs dynamiczne,
3. statyczne vs dynamiczne czasy obsługi statku oraz
4. zmienne zawinięcia statków.

W dyskretnym problemie nabrzeże jest postrzegane jako skończony zestaw koi. W ciągłym problemie statki mogą cumować w dowolnym miejscu na nabrzeżu i większość badań dotyczy tego pierwszego przypadku. W przypadku statycznego problemu przybycia wszystkie statki są już w porcie, podczas gdy w przypadku dynamicznym obecna jest tylko część statków, które mają być zaplanowane. Większość opublikowanych badań dotyczących planowania nabrzeży uwzględnia ten drugi przypadek. W statycznym problemie czasu obsługi czas obsługi statku traktuje się jako dane wejściowe, podczas gdy w dynamicznym są to zmienne decyzyjne. Wreszcie, w ostatnim przypadku, czasy przybycia statku są traktowane jako zmienne i są optymalizowane.

Ograniczenia techniczne, takie jak zanurzenie do cumowania oraz odległość między statkami i między nabrzeżami, są kolejnymi założeniami, które zostały przyjęte w niektórych badaniach dotyczących problemu alokacji nabrzeży, zbliżając sformułowanie problemu do warunków rzeczywistych. Wprowadzenie ograniczeń technicznych do istniejących modeli alokacji nabrzeży jest raczej proste i może zwiększyć złożoność problemu, ale uprościć wykorzystanie metaheurystyk (zmniejszenie możliwej przestrzeni).

Niektóre z najważniejszych celów poruszanych w literaturze to:

1. Minimalizacja całkowitego czasu obsługi statku (czas oczekiwania i obsługi),
2. Minimalizacja wczesnych i opóźnionych wyjazdów,
3. Optymalizacja czasów zawinięć statków,
4. Optymalizacja emisji i zużycia paliwa.

Problemy zostały sformułowane jako jedno- i wielocelowe oraz jedno- i dwupoziomowe.

Zobacz też

• Proces projektowania portu kontenerowego
• Lista problemów NP-zupełnych

Dalsza lektura

• Golias, Mihalis M.; i in. (2009). „Problem z alokacją nabrzeża: optymalizacja czasu przybycia statku”. Gospodarka morska i logistyka . 11 (4): 358–377. doi : 10.1057/mel.2009.12 . S2CID  14279733 .
• Guan, Yongpei; Cheung, Raymond K. (2004). „Problem alokacji nabrzeża: modele i metody rozwiązania”. LUB Widmo . 26 (1): 75–92. doi : 10.1007/s00291-003-0140-8 . S2CID  67751655 .
• Pinedo, Michael L. (2008). Planowanie: teoria, algorytmy i systemy . Nowy Jork: Springer. Numer ISBN 978-0-387-78934-7.
• Briano C, Briano E., Bruzzone AG, Revetria R. (2005) Modele wsparcia logistyki morskiej: studium przypadku poprawy planowania terminali . XIX Europejska Konferencja Modelowania i Symulacji. 1–4 czerwca 2005 Ryga, Łotwa
• Brown GG, Cormican KJ, Lawphongpanich S. i Widdis, DB Optymalizacja cumowania okrętów podwodnych z zachętą do wytrwałości . Logistyka badań morskich. Tom. 44, 1997, s. 301–318.
• Brown GG, Lawphongpanich S. i Thurman KP Optymalizacja cumowania statku. Logistyka badań morskich, tom. 41, 1994, s. 1-15.
• Canonaco P., Legato P., Mazza R., Musmanno R. Model sieci kolejkowej do zarządzania operacjami dźwigów nabrzeżowych . Komputery i badania operacyjne, tom. 35(8), 2008, s. 2432–2446.
• Cordeau, J.-F., Laporte, G., Legato, P., Moccia, L. Modele i heurystyki przeszukiwania tabu dla problemu alokacji koi . Nauka o transporcie. Tom. 39, 2005, s. 526-538.
• Dai, J., Liu, W., Moorthy, R. i Teo, C.-P. Optymalizacja planowania alokacji nabrzeży w terminalach kontenerowych . http://www.bschool.nus.edu.sg/staff/bizteocp/berthplanningjuly2004.pdf%5B%5D
• Dragović, B., Park NK, Radmilović Z. Ocena wydajności łącza statek-nabrzeże: podejścia symulacyjne i analityczne . Polityka i zarządzanie morskie, tom. 33 (3), 2006, s. 281–299.
• Edmond ED i Maggs RP, 1978. Jak przydatne są modele kolejek w decyzjach dotyczących inwestycji portowych dla nabrzeży kontenerowych? Dziennik Towarzystwa Badań Operacyjnych, tom. 29, 1978, s. 741-750.
• Golias MM (2011) Dwuobiektywne sformułowanie przydziału miejsca do cumowania w celu uwzględnienia niepewności czasu obsługi statku . Dziennik Gospodarki Morskiej i Logistyki. 13:419-441
• Golias MM, Haralambides HE Planowanie nabrzeży z funkcjami kosztów zmiennych . (2011) Dziennik Gospodarki Morskiej i Logistyki. 13:174-189
• Golias MM, Boilé M., Theofanis S., Efstathiou C. (2010) Problem planowania nabrzeży: maksymalizacja wydajności nabrzeża i minimalizacja zużycia paliwa i produkcji emisji . Transportation Research Record: Journal of the Transportation Research Board, Marine Transportation and Port Operations, 2166, 20-27.
• Golias MM, Boilé M., Theofanis S. (2010) Problem planowania dyskretnych nabrzeży: W kierunku ujednoliconego sformułowania matematycznego . Transportation Research Record: Journal of the Transportation Research Board, Modelowanie, planowanie i logistyka transportu towarowego, 2168, 1-8.
• Golias MM, Boilé M., Theofanis S., Taboada AH (2010) Wielocelowe podejście decyzyjne i analityczne do problemu planowania nabrzeży . International Journal of Information Technology Project Management, 1(1), 54-73.
• Saharidis GKD, Golias MM, Boilé M., Theofanis S., Ierapetritou M. (2009) Problem planowania nabrzeży ze zróżnicowaniem klientów: Nowe podejście metodologiczne oparte na optymalizacji hierarchicznej . International Journal of Advanced Manufacturing Technology, 46(1-4), 377-393.
• Golias MM, Boilé M., Theofanis S. (2009) Zróżnicowanie czasu obsługi harmonogramu nabrzeży klientów. Badania nad transportem, część E: Przegląd logistyki i transportu, 45(6), 878-892.
• Golias MM, Boilé M., Theofanis S. (2009) Heurystyka oparta na optymalizacji lambda dla problemu dyskretnego planowania nabrzeży. Badania transportu Pt. C, 18(5), 794-806.
• Golias MM, Boilé M., Theofanis S. (2009) Algorytm oparty na adaptacyjnym partycjonowaniu okien czasowych dla problemu dyskretnego i dynamicznego planowania nabrzeży. Transportation Research Record: Journal of the Transportation Research Board, Network Modeling, 2091, 21-30.
• Boilé M., Golias MM, Theofanis S. (2009) Planowanie zasobów cumowania w morskim terminalu kontenerowym za pomocą Genetic Algorithms: Current and Future Research. W: Pinheiro dos Santos, Wellington i in. (red.), Obliczenia ewolucyjne . Vukovar: In-Teh. ISBN  978-953-307-008-7 , s. 61-76.
• Guan Y, Xiao WQ, Cheung RK i Li CL. Wieloprocesorowy model harmonogramowania zadań do alokacji nabrzeży: analiza heurystyczna i analiza najgorszego przypadku . Listy z badań operacyjnych, tom. 30, 2002, s. 343–350.
• Han M., Ping L. i Sun J. „ Algorytm problemu planowania nabrzeży według strategii optymalizacji hybrydowej GASA ”, 9. międzynarodowa konferencja nt. sterowania, automatyki, robotyki i wizji, ICARCV, 2006.
• Hansen P. i Oguz C. Notatka dotycząca sformułowań problemów statycznej i dynamicznej alokacji nabrzeży . Raport, Les Cahiers du Gerad, G-2003-20, 2003.
• Hansen, P., Oguz, C. i Mladenovic, N. Wyszukiwanie zmiennych sąsiedztwa w celu alokacji miejsc postojowych przy minimalnych kosztach . European Journal of Operational Research, tom. 131(3), 2008, s. 636–649.
• Imai A., JT. Zhang, E. Nishimura i S. Papadimitriou. Problem alokacji nabrzeża z celami czasu obsługi i opóźnienia , Gospodarka morska i logistyka, tom. 9, 2007, s. 269–290.
• Imai A., Nagaiwa K., Tat CW. Efektywne planowanie przydziału nabrzeży dla terminali kontenerowych w Azji . Journal of Advanced Transportation, tom. 31, 1997, s. 75-94.
• Imai A., Nishimura E. i Papadimitriou S. Berth przydział z priorytetem usługi . Badania nad transportem, część B, tom. 37, 2003, s. 437-457.
• Przydział Imai A., Nishimura E., Hattori M. i Papadimitriou S. Berth przy wciętych nabrzeżach dla megakontenerów . European Journal of Operations Research, tom. 179 (2), 2007, s. 579–593.
• Alokacja Imai A., Sun X., Nishimura E. i Papadimitriou S. Berth w porcie kontenerowym: przy użyciu podejścia opartego na ciągłej przestrzeni lokalizacji . Badania nad transportem, część B, tom. 39, 2005, s. 199-221.
• Imai, A., Nishimura, E. i Papadimitriou, S. Berthing pływają w wieloużytkownikowym terminalu kontenerowym o ograniczonej pojemności nabrzeża . Badania nad transportem, część E, tom. 44(1), 2007, s. 136–151.
• Imai, A., Nishimura, E. i Papadimitriou, S. Sprostowanie do „Problemu dynamicznej alokacji nabrzeża dla portu kontenerowego”. Badania nad transportem, część B, tom. 39(3), 2005a, s. 197.
• Imai A., Nishimura E., Papadimitriou S. Problem dynamicznej alokacji nabrzeża dla portu kontenerowego . Badania nad transportem, część B, tom. 35, 2001, s. 401–417.
• C. Iris, D. Pacino, S. Ropke, A. Larsen, Integrated Berth Allocation and Quay Crane Assignment Problem: Ustaw modele podziału i wyniki obliczeń . Badania nad transportem, część E, tom. 81, 2015, s. 75–97.
• Planowanie Kim KH i Moon KC Berth przez symulowane wyżarzanie . Badania nad transportem, część B, tom. 37, 2003, s. 541-560.
• Lai KK i Shih K. Badanie przydziału nabrzeży kontenerowych . Journal of Advanced Transportation, tom. 26, 1992, s. 45-60.
• Lee DH, Song L. i Wang H.,. Algorytm genetyczny dla dwupoziomowego modelu programowania alokacji nabrzeży i harmonogramowania suwnic nabrzeżowych. Materiały z dorocznego posiedzenia rady ds. badań nad transportem w 2006 r. Waszyngton, 2006.
• Lee, Y. i Chen, Y.-C. Heurystyka optymalizacji dla problemu planowania nabrzeży . European Journal of Operational Research, 2008 (w druku).
• Legato, P. i Mazza, R. Berth Planowanie i optymalizacja zasobów w terminalu kontenerowym poprzez symulację zdarzeń dyskretnych . European Journal of Operational Research, Vol.133(3), 2001
• Li CL, Cai X i Lee CY. Planowanie przy użyciu wzorca wielu zadań na jednym procesorze . Transakcje IIE. Tom. 30, 1998, s. 433–445.
• Lim A. Problem planowania nabrzeży . Listy z badań operacyjnych .Vol. 22, 1998, s. 105-110.
• Lokuge, P. i Alahakoon, P. Poprawa zdolności adaptacyjnych w zautomatyzowanym harmonogramowaniu statków w portach kontenerowych za pomocą inteligentnych agentów oprogramowania . European Journal of Operational research, tom. 177(3), 2007, s. 1985–2015.
• Meersmans, PJM i Dekker, R. Operations Research wspiera obsługę kontenerów. Raport Instytutu Ekonometrycznego EI 2001-22, Uniwersytet Erasmus, Holandia, 2001.
• Meisel F. i Bierwirth C., Integracja alokacji nabrzeży i przydziału dźwigów w celu poprawy wykorzystania zasobów w terminalu kontenerowym w porcie morskim . Procedury Badań Operacyjnych, tom. 2005, Springer Berlin Heidelberg, 2006.
• Meisel, F. (2009). Planowanie operacji morskich w terminalach kontenerowych . Physica-Verlag Berlin Heidelberg.
• Meisel, F. i Bierwirth, C. (2009) Heurystyki integracji wydajności dźwigów w problemie alokacji nabrzeży . Badania nad transportem, część E 45(1): 196-209.
• Monako, MF i Samara, M. Problem alokacji nabrzeża: silna formuła rozwiązana przez podejście Lagrange'a ”, Transportation Science, tom. 41, nr 2, 2007, s. 265–280.
• Moorthy R. i Teo CP. Zarządzanie nabrzeżem w terminalu kontenerowym: problem projektowania szablonu . LUB Widmo. Tom. 28(4), 2006, s. 495-518.
• Nikolaou NS Planowanie nabrzeża poprzez ocenę zagęszczenia ruchu i kosztów . Journal of Waterways Highways Div. Proc. Jestem. Soc. Cyw. inż., tom. 93, 1967, s. 107–132.
• Nishimura E., Imai A., Papadimitriou S. Planowanie alokacji nabrzeży w publicznym systemie nabrzeży za pomocą algorytmów genetycznych . European Journal of Operational Research, tom. 131, 2001, s. 282–292.
• Notteboom, TE Czynnik czasu w usługach liniowych. Gospodarka morska i logistyka, tom. 8(1), 2006, s. 19–39.
• Park MY i Kim HKA metoda planowania dla żurawi nabrzeżowych i nabrzeżowych . LUB Spektrum, tom. 25, 2003, s. 1–23.
• Planowanie Park, KT i Kim, KH Berth dla terminali kontenerowych przy użyciu technik optymalizacji sub-gradientowej . Dziennik Towarzystwa Badań Operacyjnych, tom. 53, 2002, s. 1054–1062.
• Stahlbock, R. and Voss, S. Badania operacyjne na terminalach kontenerowych: aktualizacja literatury . LUB Spektrum, tom. 30, 2007, s. 1–52.
• Steenken D., Voss S. i Stahlbock R. Eksploatacja i badanie eksploatacji terminali kontenerowych – klasyfikacja i przegląd literatury . LUB Spektrum, tom. 26, 2004, s. 3-49.
• Theofanis S., Boilé M., Golias MM (2009) Planowanie nabrzeży terminali kontenerowych: krytyczny przegląd podejść badawczych i praktycznych wyzwań . Transportation Research Record: Journal of the Transportation Research Board, Marine Transportation and Port Operations, 2100, 22-28.
• Tong, CJ, Lau, HC i Lim, A. Optymalizacja kolonii mrówek dla problemu cumowania statku . Materiały Comp. Nauka. Konf. (AZJATYCKIE), s. 359–370, 1999.
• Umang, N., Bierlaire, M. i Vacca, I. Dokładne i heurystyczne metody rozwiązywania problemu alokacji nabrzeży w portach masowych . Badania nad transportem Część E: Przegląd logistyki i transportu, tom. 54, 2013, s. 14–31.
• Vis, IFA i de Koster, R. Przeładunek kontenerów na terminalu kontenerowym: przegląd . European Journal of Operational Research, Vol.147, 2003, s. 1-16.
• Wang F, Lim A (2007) Stochastyczne poszukiwanie wiązki dla problemu alokacji nabrzeża . Systemy wspomagania decyzji, tom. 42, 2007, s. 2186-2196.
• Zhou P, Kang H. i Lin L. (2006) Dynamiczny model alokacji nabrzeża oparty na rozwadze stochastycznej . Materiały VI Światowego Kongresu Inteligentnego Sterowania i Automatyki. Dalian, Chiny.
• Karam, A. i AB Eltawil. „ Nowa metoda przydzielania miejsc do cumowania, suwnic nabrzeżowych i wewnętrznych samochodów ciężarowych w terminalach kontenerowych ”. Logistyka, Informatyka i Nauki o Usługach (LISS), 2015 Międzynarodowa Konferencja nt. IEEE, 2015.
• El-Boghdadly, T., Bader-El-Den, M. i Jones, D. (2016, lipiec). Rozwijająca się lokalna heurystyka wyszukiwania dla zintegrowanego przydzielania nabrzeży i problemu przydzielania suwnic nabrzeżowych . W Evolutionary Computation (CEC), 2016 IEEE Congress na (s. 2880-2887). IEEE.