論文の概要: A Heuristic Algorithm Based on Beam Search and Iterated Local Search for the Maritime Inventory Routing Problem
- arxiv url: http://arxiv.org/abs/2505.13522v2
- Date: Wed, 11 Jun 2025 20:25:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-13 15:37:22.276382
- Title: A Heuristic Algorithm Based on Beam Search and Iterated Local Search for the Maritime Inventory Routing Problem
- Title（参考訳）: 海中インベントリルーティング問題に対するビームサーチと反復局所探索に基づくヒューリスティックアルゴリズム
- Authors: Nathalie Sanghikian, Rafael Meirelles, Rafael Martinelli, Anand Subramanian,
- Abstract要約: 海運インベントリ問題(MIRP)は、世界の海運レベルの統合において重要な役割を担っている。
MIRPは世界海運水準の統合において重要な役割を担っている。
大規模なMIRPインスタンスやその変種を効率的に解決できる、確立された方法論はいまだに存在しない。
- 参考スコア（独自算出の注目度）: 0.45152963243489175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Maritime Inventory Routing Problem (MIRP) plays a crucial role in the integration of global maritime commerce levels. However, there are still no well-established methodologies capable of efficiently solving large MIRP instances or their variants due to the high complexity of the problem. The adoption of exact methods, typically based on Mixed Integer Programming (MIP), for daily operations is nearly impractical due to the CPU time required, as planning must be executed multiple times while ensuring high-quality results within acceptable time limits. Non-MIP-based heuristics are less frequently applied due to the highly constrained nature of the problem, which makes even the construction of an effective initial solution challenging. Papageorgiou et al. (2014) introduced a single-product MIRP as the foundation for MIRPLib, aiming to provide a collection of publicly available benchmark instances. However, only a few studies that propose new methodologies have been published since then. To encourage the use of MIRPLib and facilitate result comparisons, this study presents a heuristic approach that does not rely on mathematical optimization techniques to solve a deterministic, finite-horizon, single-product MIRP. The proposed heuristic combines a variation of a Beam Search algorithm with an Iterated Local Search procedure. Among the 72 instances tested, the developed methodology can improve the best-known solution for 19 instances within an acceptable CPU time.
- Abstract（参考訳）: 海運インベントリルーティング問題(MIRP)は、世界の海運レベルの統合において重要な役割を担っている。
しかし、この問題の複雑度が高いため、大規模なMIRPインスタンスやその変種を効率的に解決できる方法が確立されていない。
通常、MIP(Mixed Integer Programming)に基づく正確なメソッドの採用は、CPU時間を必要とするため、日常的な運用はほとんど現実的ではない。
非MIPベースのヒューリスティックスは、問題の性質が厳しく制約されているため、適用頻度が低いため、効果的な初期解の構築さえも困難である。
Papageorgiou et al (2014)は、MIRPLibの基盤として単一の製品MIRPを導入した。
しかし、それ以来、新しい方法論を提唱する研究はごくわずかである。
MIRPLibの使用を奨励し、結果の比較を容易にするために、決定論的で有限水平な単一積MIRPを解くために、数学的最適化技術に頼らないヒューリスティックなアプローチを提案する。
提案したヒューリスティックは,ビーム探索アルゴリズムと反復局所探索手法のバリエーションを組み合わせたものである。
テストされた72のインスタンスのうち、開発済みの方法論は、許容できるCPU時間内に19のインスタンスで最もよく知られたソリューションを改善することができる。
関連論文リスト
- Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。
オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。
原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
論文 参考訳（メタデータ） (2024-12-23T14:48:32Z) - A Deep Instance Generative Framework for MILP Solvers Under Limited Data
Availability [66.37474135424637]
我々は、MILPインスタンスのための最初の深層生成フレームワークであるG2MILPを提案する。
G2MILPはMILPインスタンスを二部グラフとして表現し、マスク付き変分オートエンコーダを元のグラフの一部を反復的に破損させ、置き換えて新しいグラフを生成する。
生成されたMILPインスタンスの品質を評価するためのベンチマークスイートを設計する。
論文 参考訳（メタデータ） (2023-10-04T13:34:34Z) - An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming [5.070542698701157]
本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。
当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
論文 参考訳（メタデータ） (2023-06-09T08:24:56Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - An Efficient Merge Search Matheuristic for Maximising the Net Present
Value of Project Schedules [5.10800491975164]
リソース制約のあるプロジェクトスケジューリングは多くの実用的なアプリケーションにおいて重要な最適化問題である。
本稿では,資源制約のあるプロジェクトスケジューリングを解くために,マージ探索と並列計算に基づく新しい数学ヒューリスティックアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-20T13:30:23Z) - Learning to Accelerate Approximate Methods for Solving Integer
Programming via Early Fixing [29.29673962163146]
いくつかの反復近似法によって解かれた変数は、非常に長い反復で最終的な収束した離散状態の周りに変動する。
この観測から着想を得た我々は、これらの変動変数を収束状態に早期に固定することにより、これらの近似手法を加速することを目指している。
初期固定プロセス全体をマルコフ決定プロセスとして定式化し、模倣学習を用いて訓練する。
論文 参考訳（メタデータ） (2022-07-05T14:46:47Z) - Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。
正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。
最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
論文 参考訳（メタデータ） (2021-03-18T14:49:52Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。