論文の概要: Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2310.14157v4
- Date: Sat, 7 Sep 2024 13:41:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-11 03:52:53.338622
- Title: Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems
- Title（参考訳）: ニューラルネットワークによる階層型車両ルーティング問題の解法
- Authors: Abhay Sobhanan, Junyoung Park, Jinkyoo Park, Changhyun Kwon,
- Abstract要約: 車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
- 参考スコア（独自算出の注目度）: 20.684353068460375
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. Examples are the multi-depot vehicle routing problem (MDVRP), where customers are assigned to depots before delivery, and the capacitated location routing problem (CLRP), where the locations of depots should be determined first. A simple and straightforward approach for such hierarchical problems would be to separate the higher-level decisions from the complicated vehicle routing decisions. For each higher-level decision candidate, we may evaluate the underlying vehicle routing problems to assess the candidate. As this approach requires solving vehicle routing problems multiple times, it has been regarded as impractical in most cases. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge and simplify algorithm developments. For each higher-level decision candidate, we predict the objective function values of the underlying vehicle routing problems using a pre-trained graph neural network without actually solving the routing problems. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems. Our numerical experiments show that this simplified approach is effective and efficient in generating high-quality solutions for both MDVRP and CLRP and has the potential to expedite algorithm developments for complicated hierarchical problems. We provide computational results evaluated in the standard benchmark instances used in the literature.
- Abstract（参考訳）: 車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
例えば、顧客が配送前にデポに割り当てられるマルチデポの車両ルーティング問題(MDVRP)や、最初にデポの位置を決定するキャパシタイトされた位置ルーティング問題(CLRP)などがある。
このような階層的な問題に対する単純で簡単なアプローチは、高レベルの決定を複雑な車両のルーティング決定から分離することである。
各上位決定候補について、その候補を評価するために、基礎となる車両経路問題を評価することができる。
このアプローチでは、車両ルーティングの問題を複数回解決する必要があるため、ほとんどの場合、非現実的とみなされている。
本稿では,遺伝的アルゴリズムとニューラルコスト予測器(GANCP)を併用した新しいディープラーニング手法を提案する。
各上位決定候補に対して,事前学習したグラフニューラルネットワークを用いて,実際のルーティング問題を解くことなく,基礎となる車両ルーティング問題の目的関数値を予測する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
この単純化手法はMDVRPとCLRPの両方の高品質な解を生成する上で効果的であり,複雑な階層問題に対するアルゴリズム開発を高速化する可能性が示唆された。
文献で使用される標準ベンチマークインスタンスで評価された計算結果を提供する。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - 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) - Solving the vehicle routing problem with deep reinforcement learning [0.0]
本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。
広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
論文 参考訳（メタデータ） (2022-07-30T12:34:26Z) - Dynamic Origin-Destination Matrix Estimation in Urban Traffic Networks [0.05735035463793007]
この問題を二段階最適化問題としてモデル化する。
内部レベルでは、暫定的な旅行需要を前提として、動的な交通割当問題を解決し、利用者の出身地と目的地間のルーティングを決定する。
外層部では,交通ネットワーク内のセンサによって測定された車両数と内層部で発生したカウンタの差を最小限に抑えることを目的として,旅行数とその出発点および目的地の調整を行う。
論文 参考訳（メタデータ） (2022-01-31T21:33:46Z) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。
量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
論文 参考訳（メタデータ） (2021-11-15T14:07:22Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。
提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。
我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文 参考訳（メタデータ） (2021-10-08T07:22:45Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Learning (Re-)Starting Solutions for Vehicle Routing Problems [14.509927512118544]
最適化問題の解決における鍵となる課題は、エージェント(ソルバ)を効率的に探索する方法である。
本稿では,機械学習を用いて探索を高速化できることを示す。
論文 参考訳（メタデータ） (2020-08-08T02:53:09Z) - Learning High-Level Policies for Model Predictive Control [54.00297896763184]
Model Predictive Control (MPC)は、ロボット制御タスクに対する堅牢なソリューションを提供する。
ニューラルネットワークの高レベルポリシーを学習するための自己教師付き学習アルゴリズムを提案する。
提案手法は, 標準的なMPCでは困難な状況に対処できることを示す。
論文 参考訳（メタデータ） (2020-07-20T17:12:34Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。