論文の概要: Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing

• arxiv url: http://arxiv.org/abs/2504.02383v1
• Date: Thu, 03 Apr 2025 08:22:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-04 12:55:46.925768
• Title: Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing
• Title（参考訳）: 列生成における価格問題解決のための強化学習:車両ルーティングへの応用
• Authors: Abdo Abouelrous, Laurens Bliek, Adriana F. Gabor, Yaoxin Wu, Yingqian Zhang,
• Abstract要約: 我々は強化学習(RL)を用いて、価格問題(PP)において最も負のコストの低い列を見つける。 我々のモデルは、他のメカニズムの助けなしに価格問題を独立して解決するので、エンドツーエンドのメカニズムをデプロイします。 提案手法は,100件の顧客を抱えるインスタンスに対して,非常に短い実行時間で,300倍以上の速度で,線形緩和を合理的な目標ギャップまで解くことができることを示す。
• 参考スコア（独自算出の注目度）: 5.584238928596282
• License:
• Abstract: In this paper, we address the problem of Column Generation (CG) using Reinforcement Learning (RL). Specifically, we use a RL model based on the attention-mechanism architecture to find the columns with most negative reduced cost in the Pricing Problem (PP). Unlike previous Machine Learning (ML) applications for CG, our model deploys an end-to-end mechanism as it independently solves the pricing problem without the help of any heuristic. We consider a variant of Vehicle Routing Problem (VRP) as a case study for our method. Through a set of experiments where our method is compared against a Dynamic Programming (DP)-based heuristic for solving the PP, we show that our method solves the linear relaxation up to a reasonable objective gap within 9% in significantly shorter running times, up to over 300 times faster for instances with 100 customers.
• Abstract（参考訳）: 本稿では,強化学習(RL)を用いたカラム生成(CG)の問題に対処する。 具体的には、注意機構アーキテクチャに基づくRLモデルを用いて、価格問題(PP)において最も負のコストの低い列を見つける。 CGのための従来の機械学習(ML)アプリケーションとは異なり、我々のモデルは、ヒューリスティックな助けなしに価格問題を独立して解決するため、エンドツーエンドのメカニズムをデプロイする。 本稿では,本手法のケーススタディとして,車両ルーティング問題(VRP)の変種を考察する。 提案手法は,PPPを解くための動的プログラミング (DP) ベースのヒューリスティック (Huristic, ヒューリスティック) と比較した一連の実験により, 提案手法は, 100の顧客を持つインスタンスの最大300倍高速な実行時間において, 9%以内の合理的な目標ギャップまで線形緩和を解くことを示した。

関連論文リスト

• Self-Regulation and Requesting Interventions [63.5863047447313]
  介入要求のための"helper"ポリシーをトレーニングするオフラインフレームワークを提案する。 PRMによる最適介入タイミングを判定し,これらのラベル付き軌道上でヘルパーモデルを訓練する。 このオフラインアプローチは、トレーニング中のコストのかかる介入コールを大幅に削減する。
  論文  参考訳（メタデータ） (2025-02-07T00:06:17Z)
• All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers [0.0]
  本稿では,並列マシンスケジューリング問題に対するニューラルネットワーク強化カラム生成(CG)アプローチを提案する。 ニューラルネットワークをオフラインでトレーニングし、推論モードで使用することにより、負の削減コスト列を予測することにより、計算時間を大幅に削減できる。 大規模インスタンスの場合,提案手法は目標値の80%を500秒未満で改善する。
  論文  参考訳（メタデータ） (2024-10-21T02:53:37Z)
• Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows [0.09831489366502298]
  本稿では,時空間における車両ルーティング問題 (SVRP) の最適化のための強化学習手法を提案する。 我々は、特定の顧客時間窓とともに、不確実な旅行コストと需要を考慮に入れた新しいSVRPの定式化を開発する。 ルーティングコストを最小限に抑えるために、強化学習を通じてトレーニングされた注意ベースのニューラルネットワークが使用される。
  論文  参考訳（メタデータ） (2024-02-15T07:35:29Z)
• 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)
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
  カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。 CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-15T00:05:50Z)
• Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigation [72.24964965882783]
  強化学習(RL)はロボットナビゲーションにおいて有望なアプローチであり、ロボットは試行錯誤を通じて学習することができる。 現実世界のロボットタスクは、しばしばまばらな報酬に悩まされ、非効率な探索と準最適政策に繋がる。 本稿では,RLに基づくロボットナビゲーションにおいて,報酬関数を変更せずにサンプル効率を向上させる新しい手法であるConfidence-Controlled Exploration (CCE)を紹介する。
  論文  参考訳（メタデータ） (2023-06-09T18:45:15Z)
• 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)
• Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach [123.55983746427572]
  本稿では,複数ラウンドの対話を通して動的ビックレー・クラーク・グローブ(VCG)機構を回復するための新しい学習アルゴリズムを提案する。 当社のアプローチの重要な貢献は、報酬のないオンライン強化学習(RL)を取り入れて、リッチな政策分野の探索を支援することである。
  論文  参考訳（メタデータ） (2022-02-25T16:17:23Z)
• Learning to Delegate for Large-scale Vehicle Routing [4.425982186154401]
  車両ルーティング問題 (VRPs) は、幅広い実用化の課題である。 従来あるいは学習ベースの作業は、最大100人の顧客の小さな問題インスタンスに対して、適切なソリューションを実現します。 本稿では,大規模VRPを解くために,新たな局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-08T22:51:58Z)
• Model-Augmented Q-learning [112.86795579978802]
  モデルベースRLの構成要素を付加したMFRLフレームワークを提案する。 具体的には、$Q$-valuesだけでなく、共有ネットワークにおける遷移と報酬の両方を見積もる。 提案手法は,MQL (Model-augmented $Q$-learning) とよばれる提案手法により,真に報いられた学習によって得られる解と同一のポリシ不変解が得られることを示す。
  論文  参考訳（メタデータ） (2021-02-07T17:56:50Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。