論文の概要: A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints

• arxiv url: http://arxiv.org/abs/2406.12454v1
• Date: Tue, 18 Jun 2024 09:58:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 19:27:22.565045
• Title: A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints
• Title（参考訳）: 2次元負荷と終始制約による車両走行問題に対するニューラルカラム生成手法
• Authors: Yifan Xia, Xiangyi Zhang,
• Abstract要約: 2次元負荷制約 (2L-CVRP) を持つ車両ルーティング問題は, 実用的, アルゴリズム的に重要な課題である。 本稿では,高度な機械学習技術,特に注意と再発機構の新たな組み合わせを統合した,正確なアルゴリズムを提案する。 提案アルゴリズムは、標準テストベッドにおけるオープンインスタンスの解決に成功し、機械学習モデルの導入による大幅な改善を実証する。
• 参考スコア（独自算出の注目度）: 3.9594431485015096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The vehicle routing problem with two-dimensional loading constraints (2L-CVRP) and the last-in-first-out (LIFO) rule presents significant practical and algorithmic challenges. While numerous heuristic approaches have been proposed to address its complexity, stemming from two NP-hard problems: the vehicle routing problem (VRP) and the two-dimensional bin packing problem (2D-BPP), less attention has been paid to developing exact algorithms. Bridging this gap, this article presents an exact algorithm that integrates advanced machine learning techniques, specifically a novel combination of attention and recurrence mechanisms. This integration accelerates the state-of-the-art exact algorithm by a median of 29.79% across various problem instances. Moreover, the proposed algorithm successfully resolves an open instance in the standard test-bed, demonstrating significant improvements brought about by the incorporation of machine learning models. Code is available at https://github.com/xyfffff/NCG-for-2L-CVRP.
• Abstract（参考訳）: 2次元負荷制約 (2L-CVRP) と終始優先ルール (LIFO) による車両ルーティング問題は, 実用的, アルゴリズム的に重要な課題である。 車両ルーティング問題 (VRP) と2次元ビンパッキング問題 (2D-BPP) の2つのNPハード問題に起因して、その複雑さに対処するために多くのヒューリスティックなアプローチが提案されているが、正確なアルゴリズムの開発には注意が払われていない。 このギャップを埋めて、先進的な機械学習技術、特に注意と再発機構の新たな組み合わせを統合した、正確なアルゴリズムを提案する。 この統合により、最先端の正確なアルゴリズムが、様々な問題インスタンスに対して29.79%の中央値で加速される。 さらに,提案アルゴリズムは標準テストベッドにおけるオープンインスタンスの解決に成功し,機械学習モデルの導入による大幅な改善が示された。 コードはhttps://github.com/xyfffff/NCG-for-2L-CVRPで入手できる。

関連論文リスト

• Two-Timescale Model Caching and Resource Allocation for Edge-Enabled AI-Generated Content Services [55.0337199834612]
  Generative AI(GenAI)は、カスタマイズされたパーソナライズされたAI生成コンテンツ(AIGC)サービスを可能にするトランスフォーメーション技術として登場した。 これらのサービスは数十億のパラメータを持つGenAIモデルの実行を必要とし、リソース制限の無線エッジに重大な障害を生じさせる。 我々は、AIGC品質とレイテンシメトリクスのトレードオフをバランスさせるために、AIGCサービスのジョイントモデルキャッシングとリソースアロケーションの定式化を導入する。
  論文  参考訳（メタデータ） (2024-11-03T07:01:13Z)
• 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)
• 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)
• Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem [0.0]
  容量化車両ルーティング問題(Capacitated Vehicle Routing Problem)は、複数の場所に製品を届ける車両の最適経路を見つけることの難題となるNPハード問題である。 近年,この問題に対処する構築的で摂動的なディープラーニングベースのアルゴリズムの開発が試みられている。 本稿では,2つの強力な構築型および摂動型ディープラーニングに基づくアルゴリズムを組み合わせた,複合型Deep ConstructorとPerturbatorを提案する。
  論文  参考訳（メタデータ） (2022-11-25T06:20:11Z)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。 第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。 広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
  論文  参考訳（メタデータ） (2022-07-30T12:34:26Z)
• Capacitated Vehicle Routing Problem Using Conventional and Approximation Method [0.0]
  本稿では, 静電容量化車両, 単線, 距離などの制約を考慮し, 有名な車両経路問題の解決を試みる。 ノードのクラスタリングにはDBSCANアルゴリズムを採用し,近似アルゴリズムであるChristofideのアルゴリズムを用いてルーティングを行う。 生成されたソリューションは、さまざまな需要ノードで構成されるデリバリシステムのような、現実の状況の解決に使用することができる。
  論文  参考訳（メタデータ） (2022-07-29T19:25:39Z)
• A Case Study of Vehicle Route Optimization [2.2101681534594237]
  本研究では,主に関連する実世界の制約と要件を取り入れる。 時間ウィンドウと停止時間のための2段階戦略とタイムラインアルゴリズムを提案する。 4つの最先端アルゴリズムに対する8つの異なる問題インスタンスの評価は、我々のアプローチが与えられた制約を妥当な時間で処理することを示している。
  論文  参考訳（メタデータ） (2021-11-17T13:10:55Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。 このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
  論文  参考訳（メタデータ） (2021-10-13T15:38:25Z)
• 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)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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