論文の概要: Solving Travelling Thief Problems using Coordination Based Methods
- arxiv url: http://arxiv.org/abs/2310.07156v1
- Date: Wed, 11 Oct 2023 03:03:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-13 00:35:51.911911
- Title: Solving Travelling Thief Problems using Coordination Based Methods
- Title（参考訳）: コーディネーションに基づく手法による盗賊問題の解法
- Authors: Majid Namazi, M.A. Hakim Newton, Conrad Sanderson, Abdul Sattar
- Abstract要約: 旅行盗難問題(TTP)は、郵便物収集などの実生活問題の代名詞である。
TTPでは、泥棒の移動速度がクナプサックの重量に依存するため、都市選択とアイテム選択の決定は緊密な調整が必要である。
既存のTPソルバは、都市選択とアイテム選択を別々に扱い、一方のタイプの決定は、他方のタイプを扱いながら変更しない。
- 参考スコア（独自算出の注目度）: 16.685542610215286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A travelling thief problem (TTP) is a proxy to real-life problems such as
postal collection. TTP comprises an entanglement of a travelling salesman
problem (TSP) and a knapsack problem (KP) since items of KP are scattered over
cities of TSP, and a thief has to visit cities to collect items. In TTP, city
selection and item selection decisions need close coordination since the
thief's travelling speed depends on the knapsack's weight and the order of
visiting cities affects the order of item collection. Existing TTP solvers deal
with city selection and item selection separately, keeping decisions for one
type unchanged while dealing with the other type. This separation essentially
means very poor coordination between two types of decision. In this paper, we
first show that a simple local search based coordination approach does not work
in TTP. Then, to address the aforementioned problems, we propose a human
designed coordination heuristic that makes changes to collection plans during
exploration of cyclic tours. We further propose another human designed
coordination heuristic that explicitly exploits the cyclic tours in item
selections during collection plan exploration. Lastly, we propose a machine
learning based coordination heuristic that captures characteristics of the two
human designed coordination heuristics. Our proposed coordination based
approaches help our TTP solver significantly outperform existing
state-of-the-art TTP solvers on a set of benchmark problems. Our solver is
named Cooperation Coordination (CoCo) and its source code is available from
https://github.com/majid75/CoCo
- Abstract（参考訳）: 旅行盗難問題(TTP)は、郵便物収集などの実生活問題の代名詞である。
TTPは、旅行セールスマン問題(TSP)と、KPのアイテムがTSPの都市に散らばっているため、knapsack問題(KP)の絡み合いを含み、泥棒は、アイテムを集めるために都市を訪れなければならない。
TTPでは、泥棒の移動速度がクナップサックの重量に依存し、訪問都市の順序がアイテム収集の順序に影響を与えるため、都市選択とアイテム選択の決定は緊密な調整が必要である。
既存のTPソルバは、都市選択とアイテム選択を別々に扱い、一方のタイプの決定は、他方のタイプを扱いながら変更しない。
この分離は、本質的には2つのタイプの意思決定間の調整が極めて貧弱なことを意味します。
本稿では,TTPにおいて単純な局所探索に基づくコーディネートアプローチが機能しないことを示す。
そこで,上記の問題に対処するために,循環ツアーの探索中に収集計画の変更を行う,人間設計の協調ヒューリスティックを提案する。
さらに,収集計画の探索において,項目選択における巡回ツアーを明示的に活用する,人間設計の協調ヒューリスティックを提案する。
最後に,2つの人間設計協調ヒューリスティックの特徴を捉える機械学習に基づく協調ヒューリスティックを提案する。
提案手法は,TTPソルバが既存のTTPソルバをベンチマーク問題で大幅に上回るのに有効である。
ソースコードはhttps://github.com/majid75/CoCoから入手可能です。
関連論文リスト
- Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。
1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
論文 参考訳（メタデータ） (2024-04-17T15:05:51Z) - Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
協力的な車両ルーティングは、キャリアがそれぞれの輸送要求を共有し、互いに代表して輸送要求を実行することで協力するときに発生する。
従来のゲーム理論解の概念は、特性関数がエージェントの数とともに指数関数的にスケールするので、計算に費用がかかる。
我々は,この問題を,深層マルチエージェント強化学習を用いて解決した連立交渉ゲームとしてモデル化することを提案する。
論文 参考訳（メタデータ） (2023-10-26T15:42:29Z) - AffineGlue: Joint Matching and Robust Estimation [74.04609046690913]
AffineGlue, 連立2視点特徴マッチングとロバストな推定法を提案する。
AffineGlueは、最小限のモデルを推定するために、1対多の対応から潜在的なマッチを選択する。
ガイドマッチングはモデルと一致した一致を見つけるために使用され、1対1の一致の曖昧さに悩まされる。
論文 参考訳（メタデータ） (2023-07-28T08:05:36Z) - Keypoint-Guided Optimal Transport [85.396726225935]
最適マッチングを探索するリレーション保存(KPG-RL)によるキーポイント誘導モデルを提案する。
提案した KPG-RL モデルはシンクホーンのアルゴリズムで解くことができ、異なる空間で分布がサポートされている場合でも適用可能である。
二重KPG-RLからの学習された輸送計画に基づき、ターゲット領域にソースデータを転送する新しい多様体バリ中心射影を提案する。
論文 参考訳（メタデータ） (2023-03-23T08:35:56Z) - GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。
不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。
我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
論文 参考訳（メタデータ） (2022-11-04T16:10:50Z) - On the Use of Quality Diversity Algorithms for The Traveling Thief
Problem [11.590506672325668]
現実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。
本稿では,旅行セールスパーソン問題(TSP)とクナップサック問題(KP)の相互依存性を品質多様性(QD)アプローチを用いて検討する。
論文 参考訳（メタデータ） (2021-12-16T05:08:39Z) - Solving the Travelling Thief Problem based on Item Selection Weight and
Reverse Order Allocation [8.620967398331265]
旅行泥棒問題(TTP)は多くの学者を引き付ける挑戦的な最適化問題です。
本論文では,TTPを理論的および実証的に検討する。
提案した選択項目と逆順序のソート項目の定式化によって算出されたスコア値に基づくアルゴリズムを提案し,この問題を解く。
論文 参考訳（メタデータ） (2020-12-16T12:06:05Z) - Optimising Tours for the Weighted Traveling Salesperson Problem and the
Traveling Thief Problem: A Structural Comparison of Solutions [13.026567958569965]
トラベリング・ティーフ問題(TTP)は、2つの最適化問題を組み合わせることでそのような相互作用に対処する。
ノードウェイト依存トラベリングセールスパーソン問題(W-TSP)と呼ばれる新しい問題が導入され、ノードがツアーのコストに影響を与える重みを持つ。
W-TSP と TTP の最適ツアーの構造と適合度関数の相互利用の影響について検討した。
論文 参考訳（メタデータ） (2020-06-05T07:07:28Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z) - Learning to Recover Reasoning Chains for Multi-Hop Question Answering
via Cooperative Games [66.98855910291292]
本稿では,弱い教師付き信号から推論連鎖を復元する学習法を提案する。
証拠通路をどのように選択し、どのように選択された通路を接続するかを2つのモデルで処理する。
評価のために、2つのマルチホップQAデータセットに基づいたベンチマークを作成しました。
論文 参考訳（メタデータ） (2020-04-06T03:54:38Z) - A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm
for the Bi-Objective Traveling Thief Problem [7.088487500434561]
本稿では,よく研究されたトラベリングティーフ問題 (TTP) の2目的変種を解く方法を提案する。
BI-TTPは、旅行時間全体の最小化と、収集したアイテムの利益の最大化を目的としている。
提案手法は,問題固有の特徴をカスタマイズしたバイアスランダム鍵遺伝的アルゴリズムに基づく。
論文 参考訳（メタデータ） (2020-02-11T10:56:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。