論文の概要: Divide-and-Conquer Large Scale Capacitated Arc Routing Problems with Route Cutting Off Decomposition

• arxiv url: http://arxiv.org/abs/1912.12667v2
• Date: Thu, 10 Dec 2020 10:30:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-17 07:37:14.305962
• Title: Divide-and-Conquer Large Scale Capacitated Arc Routing Problems with Route Cutting Off Decomposition
• Title（参考訳）: 分解経路切断による大容量アークルータの分割・並列化問題
• Authors: Yuzhou Zhang, Yi Mei, Buzhong Zhang, Keqin Jiang
• Abstract要約: 本稿では,大規模容量アークルーティング問題に焦点をあてる。 配当戦略の成功は、適切なタスク分割に依存する。 本稿では,経路遮断演算子という問題分解演算子を提案する。
• 参考スコア（独自算出の注目度）: 0.7557957450498641
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The capacitated arc routing problem is a very important problem with many practical applications. This paper focuses on the large scale capacitated arc routing problem. Traditional solution optimization approaches usually fail because of their poor scalability. The divide-and-conquer strategy has achieved great success in solving large scale optimization problems by decomposing the original large problem into smaller sub-problems and solving them separately. For arc routing, a commonly used divide-and-conquer strategy is to divide the tasks into subsets, and then solve the sub-problems induced by the task subsets separately. However, the success of a divide-and-conquer strategy relies on a proper task division, which is non-trivial due to the complex interactions between the tasks. This paper proposes a novel problem decomposition operator, named the route cutting off operator, which considers the interactions between the tasks in a sophisticated way. To examine the effectiveness of the route cutting off operator, we integrate it with two state-of-the-art divide-and-conquer algorithms, and compared with the original counterparts on a wide range of benchmark instances. The results show that the route cutting off operator can improve the effectiveness of the decomposition, and lead to significantly better results especially when the problem size is very large and the time budget is very tight.
• Abstract（参考訳）: 容量アークルーティング問題は、多くの実用的応用において非常に重要な問題である。 本稿では大規模容量アークルーティング問題に焦点をあてる。 従来のソリューション最適化アプローチはスケーラビリティが低いため、通常は失敗する。 分割・分散戦略は、元の大きな問題を小さなサブプロブレムに分解し、個別に解決することで、大規模最適化問題の解決に大きな成功を収めた。 アークルーティングでは、タスクをサブセットに分割し、タスクサブセットによって引き起こされるサブプロブレムを解決するのが一般的である。 しかし、分割と分割戦略の成功は、タスク間の複雑な相互作用のために自明ではない適切なタスク分割に依存する。 本稿では,タスク間のインタラクションを洗練された方法で考慮し,経路切断演算子という新しい問題分解演算子を提案する。 経路カットオフ演算子の有効性を検討するために,2つの最先端の分割・結合アルゴリズムと統合し,幅広いベンチマークインスタンスで元のものと比較した。 その結果, 演算子を切断する経路は, 分解効率を向上し, 特に問題サイズが非常に大きく, 時間予算が非常にきつい場合には, 極めて良好な結果が得られることがわかった。

関連論文リスト

• UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems [8.871356150316224]
  2段階のニューラル手法は、大規模なCO問題に対処する際の効率性を示している。 本稿では,一般の大規模CO問題の解法として,統一型ニューラルディバイド・アンド・コンカー・フレームワーク(UDC)を開発する。
  論文  参考訳（メタデータ） (2024-06-29T04:29: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)
• Competitive Facility Location under Random Utilities and Routing Constraints [4.9873153106566575]
  競争市場における施設配置問題について検討し、ランダムなユーティリティ選択モデルにより顧客の需要が予測される。 我々は,選択した場所を訪問するツアーの存在を保証するために,場所の選択を必要とするルーティング制約を導入する。
  論文  参考訳（メタデータ） (2024-03-07T06:56:24Z)
• Divide-or-Conquer? Which Part Should You Distill Your LLM? [38.62667131299918]
  我々は、推論タスクを問題解決フェーズと問題解決フェーズに分解する同様の戦略を考案する。 戦略が単一ステージソリューションより優れていることを示す。
  論文  参考訳（メタデータ） (2024-02-22T22:28:46Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。 本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。 特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
  論文  参考訳（メタデータ） (2023-10-22T02:46:37Z)
• Unpaired Image Super-Resolution with Optimal Transport Maps [128.1189695209663]
  実世界の画像超解像(SR)タスクは、しばしば、教師付き技術の適用を制限するペアデータセットを持っていない。 本稿では,非バイアスのOTマップを知覚輸送コストで学習する未ペアSRのアルゴリズムを提案する。 我々のアルゴリズムは、大規模無人AIM-19データセット上で、最先端のパフォーマンスをほぼ提供する。
  論文  参考訳（メタデータ） (2022-02-02T16:21:20Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  入力摂動に対するディープニューラルネットワークの最悪の性能を分析することは、大規模な非最適化問題の解決につながる。 解析解を持つ小さなサブプロブレムに分割することで,問題の凸緩和を直接高精度に解ける新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-16T20:43:49Z)
• Theory-Inspired Path-Regularized Differential Network Architecture Search [206.93821077400733]
  差分アーキテクチャサーチ(DARTS)における高速ネットワーク最適化に対するスキップ接続の影響と,他のタイプの操作に対する競争上の優位性について検討する。 i)操作間の不当競争を避けるために各操作に導入された差分群構造スパース二乗ゲートと,(ii)浅部より収束する深部アーキテクチャの探索を誘導するために用いられる経路深度正規化の2つの主要なモジュールからなる理論に着想を得た経路規則化DARTSを提案する。
  論文  参考訳（メタデータ） (2020-06-30T05:28:23Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)
• Joint Wasserstein Distribution Matching [89.86721884036021]
  JDM問題(Joint Distribution matching)は、2つのドメインの関節分布を一致させるために双方向マッピングを学習することを目的としており、多くの機械学習およびコンピュータビジョンアプリケーションで発生している。 2つの領域における関節分布のワッサーシュタイン距離を最小化することにより、JDM問題に対処することを提案する。 そこで我々は,難解な問題を簡単な最適化問題に還元する重要な定理を提案し,その解法を開発した。
  論文  参考訳（メタデータ） (2020-03-01T03:39:00Z)

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

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