バース割り当て問題

バース割り当て問題（バーススケジューリング問題とも呼ばれる）は、コンテナターミナルにおける船舶のバーススペースの割り当てに関するオペレーションズリサーチにおけるNP 完全問題です。船舶は時間の経過とともに到着し、ターミナルオペレーターはできるだけ早くサービス（コンテナの積み下ろし）が受けられるように、船舶をバースに割り当てる必要があります。さまざまな要因が各船舶のバースと時間の割り当てに影響します。

文献に見られるモデルの中で、最も頻繁に観察されるケースは次の4つです。^[要出典]

1. 離散停泊スペースと連続停泊スペース、
2. 静的な船舶の到着と動的な船舶の到着、
3. 静的および動的船舶処理時間、および
4. 船舶の到着は変動します。

離散問題では、岸壁は有限のバースの集合としてみなされます。連続問題では、船舶は岸壁沿いのどこにでも停泊でき、研究の大部分は前者のケースを扱っています。静的な到着問題では、すべての船舶がすでに港に到着していますが、動的な問題ではスケジュールされる船舶の一部のみが存在しています。バーススケジュールに関する公開された研究の大部分は、後者のケースを扱っています。静的な処理時間問題では、船舶の処理時間は入力と見なされますが、動的な問題では決定変数です。最後に、最後のケースでは、船舶の到着時間は変数と見なされ、最適化されます。

停泊喫水や船舶間および停泊端のクリアランス距離などの技術的制約は、停泊割り当て問題を扱ういくつかの研究で採用されているさらなる仮定であり、問​​題の定式化を現実世界の状況に近づけています。既存の停泊割り当てモデルに技術的制約を導入することはむしろ単純であり、問​​題の複雑さが増す可能性がありますが、メタヒューリスティックの使用が簡素化されます (実行可能なスペースが減少)。

文献で取り上げられている最も注目すべき目的のいくつかは以下のとおりです。^[要出典]

1. 船舶の総サービス時間（待機時間と取扱時間）の最小化
2. 出発の早退や遅延を最小限に抑える
3. 船舶到着時間の最適化、
4. 排出量と燃料消費量の最適化。

問題は、単一目的および複数目的、ならびに単一レベルおよび二レベルとして ^{[誰によって]}定式化されています。

• コンテナ港の設計プロセス
• NP完全問題のリスト

• Golias, Mihalis M.; et al. (2009). 「バース割り当て問題: 船舶到着時間の最適化」. Maritime Economics & Logistics . 11 (4): 358–377. doi :10.1057/mel.2009.12. S2CID  14279733.
• Guan, Yongpei; Cheung, Raymond K. (2004). 「バース割り当て問題: モデルと解決方法」. OR Spectrum . 26 (1): 75–92. doi :10.1007/s00291-003-0140-8. S2CID  67751655.
• Pinedo, Michael L. (2008).スケジューリング: 理論、アルゴリズム、システム. ニューヨーク: Springer. ISBN 978-0-387-78934-7。
• Briano C、Briano E.、Bruzzone AG、Revetria R. (2005) 海上物流支援モデル: ターミナル計画改善のケーススタディ Archived 2019-08-03 at the Wayback Machine . 第 19 回ヨーロッパモデリングおよびシミュレーション会議。2005 年 6 月 1 ～ 4 日、リガ、ラトビア
• Brown GG、Cormican KJ、Lawphongpanich S.、および Widdis, DB「持続性インセンティブによる潜水艦の停泊の最適化」海軍研究ロジスティクス第 44 巻、1997 年、301 ～ 318 ページ。
• Brown GG、Lawphongpanich S.、Thurman KP「船舶の停泊の最適化」Naval Research Logistics、第41巻、1994年、1～15ページ。
• Canonaco, P., Legato, P., Mazza, R., Musmanno, R. バースクレーン操作管理のための待ち行列ネットワークモデル。Computers and Operations Research、Vol. 35(8)、2008、pp. 2432–2446。
• Cordeau, J.-F., Laporte, G., Legato, P., Moccia, L. バース割り当て問題のためのモデルとタブー探索ヒューリスティック。交通科学。第39巻、2005年、pp. 526–538。
• Dai, J.、Liu, W.、Moorthy, R.、Teo, C.-P. コンテナターミナルにおけるバース割り当て計画の最適化。http://www.bschool.nus.edu.sg/staff/bizteocp/berthplanningjuly2004.pdf%5B%5D
• Dragović, B., Park NK, Radmilović Z. 船舶バースリンクの性能評価：シミュレーションと分析アプローチ。海事政策と管理、第33巻（3）、2006年、281〜299頁。
• Edmond ED、Maggs RP、1978 年。「コンテナバースの港湾投資決定においてキュー モデルはどの程度有用か?」Journal of the Operational Research Society、第 29 巻、1978 年、741 ～ 750 ページ。
• Golias MM (2011) 船舶の取り扱い時間の不確実性を考慮した二目的バース割り当て定式化。海事経済・物流ジャーナル。13:419-441
• Golias MM、Haralambides HE 可変コスト関数によるバーススケジューリング。(2011) Journal of Maritime Economics and Logistics。13:174-189
• Golias MM、Boilé M.、Theofanis S.、Efstathiou C. (2010) バーススケジューリング問題: バース生産性の最大化と燃料消費および排出量の最小化。交通研究記録: 交通研究委員会ジャーナル、海上輸送および港湾運営、2166、20-27。
• Golias MM、Boilé M.、Theofanis S. (2010)「離散バーススケジューリング問題：統一された数学的定式化に向けて」輸送研究記録：輸送研究委員会ジャーナル、貨物輸送モデル化、計画、およびロジスティクス、2168、1-8。
• Golias MM、Boilé M.、Theofanis S.、Taboada AH (2010) バーススケジューリング問題に対する多目的意思決定および分析アプローチ。International Journal of Information Technology Project Management、1(1)、54-73。
• Saharidis GKD、Golias MM、Boilé M.、Theofanis S.、Ierapetritou M. (2009) 顧客差別化を伴うバーススケジューリング問題: 階層的最適化に基づく新しい方法論的アプローチ。International Journal of Advanced Manufacturing Technology、46(1-4)、377-393。
• Golias MM、Boilé M.、Theofanis S. (2009)「サービス時間に基づく顧客差別化バーススケジューリング」輸送研究パートE：物流と輸送レビュー、45（6）、878-892。
• Golias MM、Boilé M.、Theofanis S. (2009)「離散バーススケジューリング問題のためのラムダ最適化ベースのヒューリスティック」Transportation Research Pt. C、18(5)、794-806。
• Golias MM、Boilé M.、Theofanis S. (2009) 離散的かつ動的なバーススケジューリング問題のための適応型時間ウィンドウ分割ベースのアルゴリズム。交通研究記録: 交通研究委員会ジャーナル、ネットワークモデリング、2091、21-30。
• Boilé M.、Golias MM、Theofanis S. (2009) 遺伝的アルゴリズムを使用した海上コンテナターミナルでの停泊リソースのスケジュール設定: 現在の研究と将来の研究。Pinheiro dos Santos、Wellington 他 (編)、Evolutionary Computation。Vukovar : In - Teh。ISBN 978-953-307-008-7、pp. 61–76。 
• Guan Y、Xiao WQ、Cheung RK、Li CL。バース割り当てのためのマルチプロセッサ タスク スケジューリング モデル: ヒューリスティックおよび最悪ケース分析。Operations Research Letters、第 30 巻、2002 年、343 ～ 350 ページ。
• Han M.、Ping L.、および Sun J.「ハイブリッド最適化戦略 GASA によるバース スケジューリング問題のアルゴリズム」、第 9 回国際制御、オートメーション、ロボティクス、およびビジョン会議、ICARCV、2006 年。
• Hansen P.、Oguz C. 静的および動的バース割り当て問題の定式化に関するメモ。レポート、Les Cahiers du Gerad、G-2003-20、2003 年。
• Hansen, P., Oguz, C. および Mladenovic, N. 最小コストバース割り当てのための可変近傍探索^{[リンク切れ‍ ]}。European Journal of Operational Research、Vol. 131(3)、2008 年、636 ～ 649 ページ。
• Imai A.、JT. Zhang、E. Nishimura、およびS. Papadimitriou。サービス時間と遅延時間の目標を伴うバース割り当て問題^{[リンク切れ‍ ]}、Maritime Economics & Logistics、Vol.9、2007年、pp.269–290。
• 今井 明、永岩 功、Tat CW. アジアのコンテナターミナルにおける効率的なバース割り当て計画。高度交通ジャーナル、第31巻、1997年、75～94頁。
• Imai A.、Nishimura E.、および Papadimitriou S. サービス優先によるバース割り当て Archived 2019-08-03 at the Wayback Machine . Transportation Research Part B、Vol. 37、2003、pp. 437–457。
• Imai A., Nishimura E., Hattori M., and Papadimitriou S. 「メガコンテナ船のインデントバースにおけるバース割り当て」 European Journal of Operations Research, Vol. 179 (2), 2007, pp. 579–593.
• Imai A.、Sun X.、Nishimura E.、および Papadimitriou S.「コンテナ港におけるバース割り当て: 連続位置空間アプローチの使用」。交通研究パート B、第 39 巻、2005 年、pp. 199–221。
• Imai, A., Nishimura, E. and Papadimitriou, S. 限られた岸壁容量を持つマルチユーザーコンテナターミナルでの船舶の停泊。Transportation Research Part E、Vol. 44(1)、2007、pp. 136–151。
• Imai, A., Nishimura, E. and Papadimitriou, S. 「コンテナ港の動的バース割り当て問題」に対する訂正。Transportation Research Part B、Vol. 39(3)、2005a、p. 197。
• Imai, A., Nishimura, E., Papadimitriou, S. コンテナ港の動的バース割り当て問題。交通研究パートB、第35巻、2001年、pp. 401-417。
• Iris, C.、Pacino, D.、Ropke, S.、Larsen, A.、「統合バース割り当ておよび岸壁クレーン割り当て問題：セット分割モデルと計算結果」。Transportation Research Part E、Vol. 81、2015、pp. 75–97。
• Kim KH、Moon KC「シミュレーテッドアニーリングによるバーススケジューリング」、Transportation Research Part B、Vol. 37、2003、pp. 541–560。
• Lai KK、Shih K. コンテナバース割り当ての研究。Journal of Advanced Transportation、第26巻、1992年、45～60ページ。
• Lee DH、Song L.、Wang H.、「バース割り当てと岸壁クレーンのスケジュールの 2 レベル計画モデルのための遺伝的アルゴリズム」。2006 年交通研究委員会年次会議の議事録。ワシントン DC、2006 年。
• Lee, Y. および Chen, Y.-C.「バーススケジューリング問題のための最適化ヒューリスティック」European Journal of Operational Research、2008 年 (印刷中)。
• Legato, P. および Mazza, R. 離散イベントシミュレーションによるコンテナターミナルのバース計画とリソースの最適化。European Journal of Operational Research、Vol.133(3)、2001
• Li CL、Cai X、Lee CY。「1 つのプロセッサに複数のジョブを配置するパターンによるスケジューリング」IIE Transactions。第 30 巻、1998 年、pp. 433–445。
• Lim A. バース計画問題。オペレーションズ・リサーチ・レターズ、第22巻、1998年、105～110ページ。
• Lokuge, P. および Alahakoon, P. インテリジェントソフトウェアエージェントを使用したコンテナ港での船舶スケジュールの自動化における適応性の向上。European Journal of Operational research、Vol. 177(3)、2007、pp. 1985–2015。
• Meersmans, PJM および Dekker, R. 「オペレーションズ リサーチがコンテナの取り扱いをサポートする」。計量経済学研究所レポート EI 2001-22、エラスムス大学、オランダ、2001 年。
• Meisel F. および Bierwirth C.、「港湾コンテナ ターミナルのリソース利用率を向上させるためのバース割り当てとクレーン割り当ての統合」。Operations Research Proceedings、Vol. 2005、Springer Berlin Heidelberg、2006 年。
• Meisel, F. (2009)。コンテナターミナルにおける海上作業計画。Physica-Verlag Berlin Heidelberg。
• Meisel, F., Bierwirth, C. (2009) バース割り当て問題におけるクレーンの生産性の統合に関するヒューリスティックス。Transportation Research Part E 45(1): 196-209。
• Monaco, MF および Samara, M. 「バース割り当て問題: ラグランジュアプローチによる強力な定式化の解決」、Transportation Science、Vol. 41、No.2、2007、pp. 265–280。
• Moorthy R. および Teo CP. コンテナターミナルのバース管理: テンプレート設計の問題. OR Spectrum. Vol. 28(4), 2006, pp. 495–518.
• Nikolaou NS「混雑とコストの評価によるバース計画」Journal of Waterways Highways Div. Proc. Am. Soc. Civ. Engrs.、Vol. 93、1967年、pp. 107–132。
• Nishimura E., Imai A., Papadimitriou S. 遺伝的アルゴリズムによる公共バースシステムにおけるバース割り当て計画^{[ dead link ‍ ]} . European Journal of Operational Research, Vol. 131, 2001, pp. 282–292.
• Notteboom, TE「定期船サービスにおける時間要因」海事経済・物流、第8巻（1）、2006年、19～39頁。
• Park MY、Kim HKA「バースおよび岸壁クレーンのスケジュール作成方法」OR Spectrum、Vol. 25、2003、pp. 1–23。
• Park, KT および Kim, KH サブ勾配最適化技術を使用したコンテナターミナルのバーススケジューリング。Journal of Operational Research Society、第 53 巻、2002 年、1054 ～ 1062 ページ。
• Stahlbock, R. および Voss, S. コンテナターミナルにおけるオペレーションリサーチ: 最新の文献。OR Spectrum、第 30 巻、2007 年、1 ～ 52 ページ。
• Steenken, D.、Voss, S.、Stahlbock, R.「コンテナターミナルの運用とオペレーションズリサーチ - 分類と文献レビュー」OR Spectrum、Vol. 26、2004年、pp. 3-49。
• Theofanis S.、Boilé M.、Golias MM (2009) コンテナターミナルバース計画：研究アプローチと実際的な課題の批判的レビュー^{[リンク切れ‍ ]}。交通研究記録：交通研究委員会ジャーナル、海上輸送および港湾運営、2100、22-28。
• Tong, CJ、Lau, HC、Lim, A. 船舶停泊問題のためのアリコロニー最適化。アジア計算科学会議(ASIAN)の議事録、pp. 359–370、1999年。
• Umang, N.、Bierlaire, M.、Vacca, I.「バルク港におけるバース割り当て問題を解決するための正確かつヒューリスティックな方法」輸送研究パートE：物流と輸送レビュー、第54巻、2013年、pp. 14～31。
• Vis, IFA および de Koster, R. コンテナターミナルでのコンテナの積み替え: 概要。European Journal of Operational Research、Vol.147、2003 年、pp. 1–16。
• Wang F、Lim A (2007) バース割り当て問題のための確率的ビーム探索。Decision Support Systems、Vol. 42、2007、pp. 2186–2196。
• Zhou P、Kang H.、Lin L. (2006) 確率論的考慮に基づく動的バース割り当てモデル。第 6 回世界インテリジェント制御およびオートメーション会議の議事録。中国、大連。
• Karam, A.、および AB Eltawil。「コンテナ ターミナルのバース、岸壁クレーン、内部トラックを割り当てる新しい方法。」ロジスティクス、情報科学、およびサービス サイエンス (LISS)、2015 年国際会議。IEEE、2015 年。
• El-Boghdadly, T.、Bader-El-Den, M.、Jones, D. (2016 年 7 月)。統合バース割り当ておよび岸壁クレーンの割り当て問題のための進化型ローカル検索ヒューリスティック。Evolutionary Computation (CEC)、2016 IEEE 会議 (pp. 2880-2887)。IEEE。
• Wang, C., Miao, L., Zhang, C., Wu, T., & Liang, Z. (2023). 統合バース割り当ておよび岸壁クレーン割り当て問題に対するロバスト最適化。海軍研究ロジスティクス (NRL)、1–25。https://doi.org/10.1002/nav.22159