論文の概要: Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet

• arxiv url: http://arxiv.org/abs/2411.04777v1
• Date: Thu, 07 Nov 2024 15:16:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:37:12.637063
• Title: Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet
• Title（参考訳）: 車両経路問題の解法:有限車両艦隊による時間制約車両経路問題に対するニューラル最適化手法
• Authors: Elija Deineko, Carina Kehrt,
• Abstract要約: 車両の車両サイズが有限である時間制約付静電容量VRPを解くためのNCO手法を提案する。 この手法は、柔軟性と堅牢な一般化の両方を示す、適切で費用効率のよい解を見つけることができる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Finding a feasible and prompt solution to the Vehicle Routing Problem (VRP) is a prerequisite for efficient freight transportation, seamless logistics, and sustainable mobility. Traditional optimization methods reach their limits when confronted with the real-world complexity of VRPs, which involve numerous constraints and objectives. Recently, the ability of generative Artificial Intelligence (AI) to solve combinatorial tasks, known as Neural Combinatorial Optimization (NCO), demonstrated promising results, offering new perspectives. In this study, we propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The approach is based on an encoder-decoder architecture, formulated in line with the Policy Optimization with Multiple Optima (POMO) protocol and trained via a Proximal Policy Optimization (PPO) algorithm. We successfully trained the policy with multiple objectives (minimizing the total distance while maximizing vehicle utilization) and evaluated it on medium and large instances, benchmarking it against state-of-the-art heuristics. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalization. Finally, we provide a critical analysis of the solution generated by NCO and discuss the challenges and opportunities of this new branch of intelligent learning algorithms emerging in optimization science, focusing on freight transportation.
• Abstract（参考訳）: 車両ルーティング問題(VRP)に対する実現可能かつ迅速な解決策を見つけることは、効率的な貨物輸送、シームレスなロジスティクス、持続可能な移動のための前提条件である。 従来の最適化手法は、多くの制約や目的を含む現実的なVRPの複雑さに直面すると限界に達する。 近年,Neural Combinatorial Optimization(NCO)と呼ばれる組み合わせタスクを解くための生成人工知能(AI)の能力は,期待できる結果を示し,新たな視点を提供する。 本研究では, 時間制約付き静電容量VRPを有限車両サイズで解くためのNCO手法を提案する。 アプローチはエンコーダ・デコーダアーキテクチャに基づいており、複数のオプティマイザ (POMO) プロトコルによるポリシー最適化 (Polym Optimization with Multiple Optima) プロトコルに従って定式化され、PPO (Proximal Policy Optimization) アルゴリズムを用いて訓練されている。 我々は、複数の目標(車両利用を最大化しながら全距離を最小化する)でポリシーをトレーニングし、中規模および大規模インスタンスで評価し、最先端のヒューリスティックスに対してベンチマークした。 この手法は、柔軟性と堅牢な一般化の両方を示す、適切で費用効率のよい解を見つけることができる。 最後に、NCOが生み出したソリューションの批判的分析を行い、貨物輸送に焦点を当てた最適化科学に出現する知的学習アルゴリズムの新しい分野の課題と機会について論じる。

関連論文リスト

• 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)
• DNN Partitioning, Task Offloading, and Resource Allocation in Dynamic Vehicular Networks: A Lyapunov-Guided Diffusion-Based Reinforcement Learning Approach [49.56404236394601]
  本稿では,Vehicular Edge Computingにおける共同DNNパーティショニング,タスクオフロード,リソース割り当ての問題を定式化する。 我々の目標は、時間とともにシステムの安定性を保証しながら、DNNベースのタスク完了時間を最小化することである。 拡散モデルの革新的利用を取り入れたマルチエージェント拡散に基づく深層強化学習(MAD2RL)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T06:31:03Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。 本稿では,CVRPの車両容量制約を回避できる最短経路を最小化する目的機能を備えた,CVRP用の新しいバイナリエンコーディングを提案する。 本稿では,量子交換演算子Ansatzの変種に基づく符号化の有効性について論じる。
  論文  参考訳（メタデータ） (2023-08-17T05:14:43Z)
• Solving the capacitated vehicle routing problem with timing windows using rollouts and MAX-SAT [4.873362301533824]
  車両ルーティングはNPハード最適化問題のよく知られたクラスである。 最近の強化学習の取り組みは有望な代替手段である。 本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-14T06:27:09Z)
• Fast and computationally efficient generative adversarial network algorithm for unmanned aerial vehicle-based network coverage optimization [1.2853186701496802]
  移動ネットワークにおける動的な交通需要の課題は、無人航空機をベースとした移動セルに対処されている。 将来,無人航空機の膨大な可能性を考えると,カバー範囲最適化のための新しいアルゴリズムを提案する。 提案アルゴリズムは,一意の多層和プーリング損失関数を持つ条件付き生成逆ニューラルネットワークに基づいて実装された。
  論文  参考訳（メタデータ） (2022-03-25T12:13:21Z)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  我々は,従来の自己回帰的アプローチよりもはるかに高速に,監督や推論なしに学習できるモデルを構築することができることを示す。 また、ディープラーニングモデルに最適なトランスポートアルゴリズムを組み込むことで、エンドツーエンドのトレーニング中に割り当て制約を強制する利点を実証的に評価する。
  論文  参考訳（メタデータ） (2022-03-02T07:21:56Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  車両ルーティング問題(VRP)は典型的な離散最適化問題である。 多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。 本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
  論文  参考訳（メタデータ） (2021-07-15T02:13:03Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
  最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。 これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。 より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
  論文  参考訳（メタデータ） (2020-12-24T14:18:56Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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