論文の概要: Solving NP-hard Min-max Routing Problems as Sequential Generation with Equity Context

• arxiv url: http://arxiv.org/abs/2306.02689v1
• Date: Mon, 5 Jun 2023 08:29:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-06 16:10:30.645289
• Title: Solving NP-hard Min-max Routing Problems as Sequential Generation with Equity Context
• Title（参考訳）: 列生成におけるNP-hard Min-maxルーティング問題の解法
• Authors: Jiwoo Son, Minsu Kim, Sanghyeok Choi, Jinkyoo Park
• Abstract要約: ミニマックスルーティング問題は、各エージェントがすべての都市、すなわち完了時刻を共同で訪問する際に、最大ツアー期間を最小化することを目的としている。 既存の手法は、特に数千の都市をカバーするために多数のエージェントの調整を必要とする大規模な問題において、課題に直面している。 本稿では,大規模なmin-maxルーティング問題を解決するための新しいディープラーニングフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 13.54697305625963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Min-max routing problems aim to minimize the maximum tour length among agents as they collaboratively visit all cities, i.e., the completion time. These problems include impactful real-world applications but are known as NP-hard. Existing methods are facing challenges, particularly in large-scale problems that require the coordination of numerous agents to cover thousands of cities. This paper proposes a new deep-learning framework to solve large-scale min-max routing problems. We model the simultaneous decision-making of multiple agents as a sequential generation process, allowing the utilization of scalable deep-learning models for sequential decision-making. In the sequentially approximated problem, we propose a scalable contextual Transformer model, Equity-Transformer, which generates sequential actions considering an equitable workload among other agents. The effectiveness of Equity-Transformer is demonstrated through its superior performance in two representative min-max routing tasks: the min-max multiple traveling salesman problem (min-max mTSP) and the min-max multiple pick-up and delivery problem (min-max mPDP). Notably, our method achieves significant reductions of runtime, approximately 335 times, and cost values of about 53% compared to a competitive heuristic (LKH3) in the case of 100 vehicles with 1,000 cities of mTSP. We provide reproducible source code: https://github.com/kaist-silab/equity-transformer
• Abstract（参考訳）: ミニマックスルーティング問題は、各エージェントがすべての都市、すなわち完了時刻を共同で訪問する際に、最大ツアー期間を最小化することを目的としている。 これらの問題には影響のある実世界の応用が含まれるが、NPハードとして知られている。 既存の手法は、特に数千の都市をカバーするために多数のエージェントの調整を必要とする大規模な問題に直面している。 本稿では,大規模min-maxルーティング問題を解決するための新しいディープラーニングフレームワークを提案する。 我々は,複数のエージェントの同時意思決定を逐次生成プロセスとしてモデル化し,スケーラブルなディープラーニングモデルを逐次決定に活用する。 逐次近似問題では、他のエージェントの作業負荷を考慮した逐次動作を生成するスケーラブルな文脈変換器モデルEquity-Transformerを提案する。 Equity-Transformerの有効性は、min-max多重走行セールスマン問題(min-max mTSP)とmin-max多重ピックアップ・デリバリ問題(min-max mPDP)の2つの代表的なmin-maxルーティングタスクにおいて、優れた性能で実証されている。 特に,mTSP1000都市100台において,競争的ヒューリスティック(LKH3)と比較して,約335倍,コストが約53%のランタイムの大幅な削減を実現している。 再現可能なソースコードはhttps://github.com/kaist-silab/equity-transformerです。

関連論文リスト

• MultiMax: Sparse and Multi-Modal Attention Learning [60.49318008131978]
  SoftMaxは現代の機械学習アルゴリズムのユビキタスな成分である。 分散性はSoftMaxの変種族によって達成できるが、それらはしばしば代替損失関数を必要とし、多重モダリティを保たない。 入力入力範囲に応じて出力分布を適応的に変調するMultiMaxを提案する。
  論文  参考訳（メタデータ） (2024-06-03T10:51:43Z)
• DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems [26.48767051423456]
  本稿では、分割とナビゲーションのための異なる埋め込みを学習する、新しいアテンションベースのパーティション・アンド・ナビゲーション・エンコーダ(P&N)を提案する。 エージェント置換対称損失関数(APS)を開発した。
  論文  参考訳（メタデータ） (2024-05-27T15:33:16Z)
• iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
  MTSP(Min-Max Multiple Traveling Salesman)問題の検討 目標は、最長ツアーの長さを最小化しながら、各エージェントが一括してすべての都市を訪れるツアーを見つけることである。 我々は、命令型MTSP(iMTSP)と呼ばれる、新しい自己教師型双方向エンドツーエンド学習フレームワークを導入する。
  論文  参考訳（メタデータ） (2024-05-01T02:26:13Z)
• Robust Multi-Task Learning with Excess Risks [24.695243608197835]
  マルチタスク学習(MTL)は、全てのタスク損失の凸結合を最適化することにより、複数のタスクのジョイントモデルを学ぶことを検討する。 既存の方法は適応的な重み更新方式を用いており、各損失に基づいてタスク重みを動的に調整し、困難なタスクを優先順位付けする。 本稿では,過度リスクに基づくタスクバランス手法であるMulti-Task Learning with Excess Risks (ExcessMTL)を提案する。
  論文  参考訳（メタデータ） (2024-02-03T03:46:14Z)
• Parameter-efficient Tuning of Large-scale Multimodal Foundation Model [68.24510810095802]
  我々はこれらの課題を克服するために、クロスモーダル転送(Aurora)のための優雅なプロンプトフレームワークを提案する。 既存のアーキテクチャの冗長性を考慮すると、まずモード近似を用いて0.1Mのトレーニング可能なパラメータを生成し、マルチモーダルプロンプトチューニングを実装する。 6つのクロスモーダルベンチマークの徹底的な評価は、最先端のベンチマークを上回るだけでなく、完全な微調整アプローチよりも優れていることを示している。
  論文  参考訳（メタデータ） (2023-05-15T06:40:56Z)
• M$^3$ViT: Mixture-of-Experts Vision Transformer for Efficient Multi-task Learning with Model-Accelerator Co-design [95.41238363769892]
  マルチタスク学習(MTL)は、複数の学習タスクを単一のモデルにカプセル化し、それらのタスクを共同でよりよく学習できるようにする。 現在のMTLレギュレータは、1つのタスクだけを実行するためにさえ、ほぼすべてのモデルを起動する必要がある。 効率的なオンデバイスMTLを実現するためのモデル-アクセラレータ共設計フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-10-26T15:40:24Z)
• Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
  ビジョントランスフォーマー(ViT)は、様々なコンピュータビジョンタスクに対して印象的なパフォーマンスを実現している。 トレーニング済みのViTを効率よく自動圧縮するSPViT(Single-Path Vision Transformer pruning)を提案する。 われわれのSPViTはDeiT-Bで52.0%のFLOPをトリミングできる。
  論文  参考訳（メタデータ） (2021-11-23T11:35:54Z)
• DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem [5.137147284997655]
  我々は、DANと呼ばれるMinMax mTSPを解くために、分散注意に基づくニューラルネットワーク手法を導入する。 DANでは、エージェントは、他のエージェントの将来の決定を予測することによって、ツアーを共同で構築するための完全に分散されたポリシーを学ぶ。 我々は50から1000の都市、5から20のエージェントを含む小規模から大規模mTSPインスタンスで実験を行い、最先端のベースラインと比較した。
  論文  参考訳（メタデータ） (2021-09-09T12:26:04Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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