論文の概要: GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time

• arxiv url: http://arxiv.org/abs/2312.08224v2
• Date: Sun, 21 Jul 2024 10:18:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-24 05:07:10.790560
• Title: GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time
• Title（参考訳）: GLOP:大規模ルーティング問題を解決するためのグローバルパーティションとローカル構築をリアルタイムで学習する
• Authors: Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, Fanzhang Li,
• Abstract要約: GLOPは、大規模なルーティング問題に対して効率的にスケールする統一階層型フレームワークである。 粗粒度問題分割のための非自己回帰ニューラルと、細粒度経路構築のための自己回帰ニューラルを初めてハイブリダイズする。 実験により、GLOPは大規模ルーティング問題において、競争力と最先端のリアルタイム性能を達成することが示された。
• 参考スコア（独自算出の注目度）: 17.450373393248984
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The recent end-to-end neural solvers have shown promise for small-scale routing problems but suffered from limited real-time scaling-up performance. This paper proposes GLOP (Global and Local Optimization Policies), a unified hierarchical framework that efficiently scales toward large-scale routing problems. GLOP partitions large routing problems into Travelling Salesman Problems (TSPs) and TSPs into Shortest Hamiltonian Path Problems. For the first time, we hybridize non-autoregressive neural heuristics for coarse-grained problem partitions and autoregressive neural heuristics for fine-grained route constructions, leveraging the scalability of the former and the meticulousness of the latter. Experimental results show that GLOP achieves competitive and state-of-the-art real-time performance on large-scale routing problems, including TSP, ATSP, CVRP, and PCTSP.
• Abstract（参考訳）: 最近のエンドツーエンドのニューラルソルバは、小規模ルーティング問題への期待を示しているが、リアルタイムのスケーリングパフォーマンスの制限に悩まされている。 本稿では,大規模ルーティング問題に対して効率よくスケール可能な統一階層型フレームワークであるGLOP(Global and Local Optimization Policies)を提案する。 GLOPは、トラベルセールスマン問題(TSP)とTSPに分割して、最も短いハミルトンパス問題に分割する。 まず, 粗粒度問題分割のための非自己回帰型ニューラルヒューリスティックスと, 細粒度ルート構築のための自己回帰型ニューラルヒューリスティックスをハイブリダイズし, 前者のスケーラビリティと後者の繊細さを活用する。 実験結果から,TSP,ATSP,CVRP,PCTSPなどの大規模ルーティング問題に対して,GLOPは競合的かつ最先端のリアルタイム性能を実現することがわかった。

関連論文リスト

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• 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)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。 本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。 特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
  論文  参考訳（メタデータ） (2023-10-22T02:46:37Z)
• Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy [24.91781032046481]
  車両ルーティング問題(VRP)のための多くのニューラルネットワーク構築手法は、特定のノード分布と限られたスケールを持つ合成問題インスタンスに焦点を当てている。 我々は,局所移動可能な局所的特徴から学習する補助的政策を設計し,それを典型的な建設方針と統合し,アンサンブル政策を形成する。 共同トレーニングでは、集約されたポリシが協調的かつ補完的に実行され、一般化が促進される。
  論文  参考訳（メタデータ） (2023-08-27T13:22:50Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Adaptive Self-supervision Algorithms for Physics-informed Neural Networks [59.822151945132525]
  物理情報ニューラルネットワーク(PINN)は、損失関数のソフト制約として問題領域からの物理的知識を取り入れている。 これらのモデルの訓練性に及ぼす座標点の位置の影響について検討した。 モデルがより高い誤りを犯している領域に対して、より多くのコロケーションポイントを段階的に割り当てる適応的コロケーション方式を提案する。
  論文  参考訳（メタデータ） (2022-07-08T18:17:06Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  ニューラルネットワークアーキテクチャの制約に基づく表現について検討する。 本稿では,いわゆるアーキテクチャ制約を満たすのに適した簡単な最適化手法について検討する。
  論文  参考訳（メタデータ） (2020-02-18T16:47:38Z)

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

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