論文の概要: A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing

• arxiv url: http://arxiv.org/abs/2607.16875v1
• Date: Sat, 18 Jul 2026 16:27:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.29281
• Title: A Deep Reinforcement Learning Algorithm for the Vehicle Routing Problem with Stochastic Demands and Outsourcing
• Title（参考訳）: 確率的需要とアウトソーシングを伴う車両経路問題に対する深層強化学習アルゴリズム
• Authors: Mohsen Dastpak, Fausto Errico, Ola Jabali,
• Abstract要約: 要求とアウトソーシングオプションによる車両ルーティング問題(VRP-SDO) コミットしたサブセットに対してほぼ瞬時にコストを見積もるオフラインルーティングポリシを学びます。 実験の結果,現状の手法と比較して,ルーティングコストを19.6%削減できることがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the vehicle routing problem with stochastic demands and outsourcing options (VRP-SDO), in which a logistics service provider partitions customer requests into customers outsourced to a common carrier and customers committed to its fixed fleet. The latter induces a vehicle routing problem with stochastic demands (VRP-SD), solved dynamically. Demands are revealed upon visit; residual demand may be served by other vehicles or after restocking at the depot. Work beyond the regular shift incurs overtime costs, and the unit outsourcing cost decreases with the expected outsourced demand. The objective is to minimize expected travel, overtime, and outsourcing costs. We propose an iterative two-level methodology whose first level partitions customers into committed and outsourced subsets, while the second level estimates the expected VRP-SD routing cost. To avoid solving this problem from scratch at every iteration, we learn an offline routing policy that estimates costs almost instantly for any committed subset. An iterated local search establishes the first-level partitions. We formulate the second level as a Markov decision process and solve it with a deep Q-network whose state is represented by a graph attention network aggregating customer and vehicle information by relevance to the acting vehicle. Trained offline on instances with variable customer cardinality and locations, the policy applies to any daily customer realization; online fine-tuning improves the cost approximation. Experiments show that our policy reduces routing costs by 19.6% relative to a state-of-the-art method and by at least 29.6% over classical heuristics. Our overall algorithm saves 13.7% on average over the version without the attention-based representation and generates high-quality decisions within minutes, whereas benchmarks without an offline-trained estimator require over an hour.
• Abstract（参考訳）: 本稿では、ロジスティクスサービスプロバイダが、顧客要求を共通キャリアにアウトソースする顧客と、その固定車両にコミットする顧客に分割する、確率的要求とアウトソーシングオプション(VRP-SDO)による車両ルーティング問題を紹介する。 後者は、確率的要求(VRP-SD)を伴う車両ルーティング問題を動的に解決する。 需要は訪問時に明らかにされ、残りの需要は他の車両によって提供され、あるいは補給所で補給される。 定期的なシフトを超えた作業は残業コストを発生させ、予想されるアウトソース需要によってユニットアウトソーシングコストは減少する。 目的は、期待される旅行、残業、アウトソーシングコストを最小限にすることである。 本稿では,第1レベルが顧客をコミットおよびアウトソースサブセットに分割し,第2レベルが期待されるVRP-SDルーティングコストを見積もる,反復的な2段階手法を提案する。 イテレーション毎にスクラッチからこの問題を解決するために、コミットしたサブセットに対してほぼ即座にコストを見積もるオフラインルーティングポリシを学びます。 反復ローカルサーチは、第1レベルのパーティションを確立する。 我々は、マルコフ決定プロセスとして第2段階を定式化し、その状態が顧客情報と車両情報をアクティベートするグラフアテンションネットワークによって表現されるディープQネットワークで解決する。 さまざまな顧客濃度とロケーションを持つインスタンスでオフラインでトレーニングされたこのポリシーは、毎日の顧客実現に適用される。 実験によると、我々の政策は、最先端の手法と比較して、ルーティングコストを19.6%削減し、古典的ヒューリスティックスよりも少なくとも29.6%削減している。 我々の全体的なアルゴリズムは、注意に基づく表現なしで平均13.7%の時間を節約し、数分で高品質な決定を生成するが、オフラインでトレーニングされた推定器を持たないベンチマークでは1時間以上かかる。

関連論文リスト

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。 本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。 このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  協力的な車両ルーティングは、キャリアがそれぞれの輸送要求を共有し、互いに代表して輸送要求を実行することで協力するときに発生する。 従来のゲーム理論解の概念は、特性関数がエージェントの数とともに指数関数的にスケールするので、計算に費用がかかる。 我々は,この問題を,深層マルチエージェント強化学習を用いて解決した連立交渉ゲームとしてモデル化することを提案する。
  論文  参考訳（メタデータ） (2023-10-26T15:42:29Z)
• Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing [49.00137468773683]
  コラボレーティブ・ビークル・ルーティング(Collaborative Vehicle Routing)とは、デリバリ情報を共有し、互いに代理してデリバリ要求を実行することで、デリバリ企業が協力する場所である。 これによりスケールの経済が達成され、コスト、温室効果ガスの排出、道路渋滞が減少する。 しかし、どの会社が誰とパートナーし、それぞれの会社がどれだけの報酬を支払うべきか? シャプリー値(英語版)やヌクレオルス(英語版)のような伝統的なゲーム理論解の概念は、協調車両ルーティング(英語版)の現実問題に対して計算することが困難である。
  論文  参考訳（メタデータ） (2023-10-26T15:04:23Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。 本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。 特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
  論文  参考訳（メタデータ） (2023-10-22T02:46:37Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。 RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2023-06-04T09:18:02Z)
• Off-line approximate dynamic programming for the vehicle routing problem with stochastic customers and demands via decentralized decision-making [0.0]
  本稿では,顧客の位置と需要が不確実な車両経路問題(VRP)の変種について検討する。 目的は、車両の容量と時間制限を満たしながら、提供された要求を最大化することである。 本稿では,Replay MemoryやDouble Q Networkといった最先端のアクセラレーション技術を用いたQラーニングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-09-21T14:28:09Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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