論文の概要: Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems
- arxiv url: http://arxiv.org/abs/2310.09686v1
- Date: Sun, 15 Oct 2023 00:05:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-17 18:50:01.055765
- Title: Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems
- Title（参考訳）: 車両ルーティングとスケジューリング問題に対する強化学習に基づくハイパーヒューリスティックによる列生成の強化
- Authors: Kuan Xu and Li Shen and Lindong Liu
- Abstract要約: カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。
CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 9.203492057735074
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Column generation (CG) is a vital method to solve large-scale problems by
dynamically generating variables. It has extensive applications in common
combinatorial optimization, such as vehicle routing and scheduling problems,
where each iteration step requires solving an NP-hard constrained shortest path
problem. Although some heuristic methods for acceleration already exist, they
are not versatile enough to solve different problems. In this work, we propose
a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to
enhance the performance of CG. RLHH is a selection module embedded in CG to
accelerate convergence and get better integer solutions. In each CG iteration,
the RL agent selects a low-level heuristic to construct a reduced network only
containing the edges with a greater chance of being part of the optimal
solution. In addition, we specify RLHH to solve two typical combinatorial
optimization problems: Vehicle Routing Problem with Time Windows (VRPTW) and
Bus Driver Scheduling Problem (BDSP). The total cost can be reduced by up to
27.9\% in VRPTW and 15.4\% in BDSP compared to the best lower-level heuristic
in our tested scenarios, within equivalent or even less computational time. The
proposed RLHH is the first RL-based CG method that outperforms traditional
approaches in terms of solution quality, which can promote the application of
CG in combinatorial optimization.
- Abstract（参考訳）: カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。
車両のルーティングやスケジューリングといった共通組合せ最適化の広範な応用があり、各イテレーションステップではnpハード制約付き最短経路問題を解く必要がある。
加速のためのヒューリスティックな手法はいくつか存在するが、それらは異なる問題を解決するのに十分な汎用性がない。
本研究では,CGの性能向上を目的として,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
rlhhはcgに埋め込まれた選択モジュールで、収束を加速し、より良い整数解を得る。
各CGイテレーションでは、RLエージェントが低レベルのヒューリスティックを選択し、最適解の一部である可能性が高いエッジのみを含む縮小ネットワークを構築する。
さらに、RLHHを2つの典型的な組合せ最適化問題の解法として、車載時間Windows(VRPTW)とバスドライバスケジューリング問題(BDSP)を指定する。
総コストはvrptwでは最大27.9\%、bdspでは15.4\%削減できる。
提案したRLHHは,解の最適化におけるCGの適用を促進できる,ソリューション品質の観点から従来のアプローチより優れている最初のRLベースのCG手法である。
関連論文リスト
- Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。
WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
論文 参考訳（メタデータ） (2024-07-18T02:46:06Z) - Transform then Explore: a Simple and Effective Technique for Exploratory Combinatorial Optimization with Reinforcement Learning [11.531786269804707]
グラフ上の最適化問題(COP)を解決するためのゲージ変換(GT)手法を提案する。
GTは非常にシンプルで、10行未満のPythonコードで実装でき、ほとんどの強化学習モデルに適用できる。
GTを用いた従来のRLモデルでは,MaxCut問題に対して最先端の性能が得られた。
論文 参考訳（メタデータ） (2024-04-06T15:31:17Z) - Spatial-temporal-demand clustering for solving large-scale vehicle
routing problems with time windows [0.0]
本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。
その類似度基準は、顧客の空間的、時間的、需要データを含む。
本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
論文 参考訳（メタデータ） (2024-01-20T06:06:01Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。
我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。
我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
論文 参考訳（メタデータ） (2023-02-02T18:27:20Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
我々は車載OCCにおけるスペクトル効率最適化手法を提案する。
我々は最適化問題をマルコフ決定プロセス(MDP)としてモデル化し、オンラインで適用可能なソリューションの利用を可能にする。
提案手法の性能を広範囲なシミュレーションにより検証し,提案手法の様々な変種とランダムな手法との比較を行った。
論文 参考訳（メタデータ） (2022-05-05T14:25:54Z) - Distributed Multi-agent Meta Learning for Trajectory Design in Wireless
Drone Networks [151.27147513363502]
本稿では,動的無線ネットワーク環境で動作するエネルギー制約型ドローン群に対する軌道設計の問題点について検討する。
値ベース強化学習(VDRL)ソリューションとメタトレイン機構を提案する。
論文 参考訳（メタデータ） (2020-12-06T01:30:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Combining Reinforcement Learning and Constraint Programming for
Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。
深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。
制約プログラミング(CP)は最適化問題を解決する汎用ツールである。
本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2020-06-02T13:54:27Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。