論文の概要: Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions

• arxiv url: http://arxiv.org/abs/2006.03260v1
• Date: Fri, 5 Jun 2020 07:07:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-25 03:16:34.675031
• Title: Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
• Title（参考訳）: 重み付きトラベリングセールスマン問題とトラベリングティーフ問題に対する最適ツアー:ソリューションの構造的比較
• Authors: Jakob Bossek, Aneta Neumann, Frank Neumann
• Abstract要約: トラベリング・ティーフ問題(TTP)は、2つの最適化問題を組み合わせることでそのような相互作用に対処する。 ノードウェイト依存トラベリングセールスパーソン問題(W-TSP)と呼ばれる新しい問題が導入され、ノードがツアーのコストに影響を与える重みを持つ。 W-TSP と TTP の最適ツアーの構造と適合度関数の相互利用の影響について検討した。
• 参考スコア（独自算出の注目度）: 13.026567958569965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. However, many real-world problems are composed of several interacting components. The Traveling Thief Problem (TTP) addresses such interactions by combining two combinatorial optimisation problems, namely the TSP and the Knapsack Problem (KP). Recently, a new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. In this paper, we compare W-TSP and TTP. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function. Our experimental results suggest (1) that the W-TSP often can be solved better using the TTP fitness function and (2) final W-TSP and TTP solutions show different distributions when compared with optimal TSP or weighted greedy solutions.
• Abstract（参考訳）: トラベリングセールスパーソン問題(TSP)は、最もよく知られた組合せ最適化問題の1つである。 しかし、現実世界の多くの問題はいくつかの相互作用するコンポーネントで構成されている。 トラベリング・ティーフ問題(TTP)は、TSPとKnapsack問題(KP)という2つの組合せ最適化問題を組み合わせることでそのような相互作用に対処する。 近年,ノード重み依存型トラベルセールスパーソン問題(w-tsp)と呼ばれる新たな問題が発生し,ノードがツアーの費用に影響を与える重みを持つようになった。 本稿では,W-TSPとTPを比較した。 W-TSP と TTP の最適ツアーの構造と適合度関数の相互利用の影響について検討した。 実験結果から,(1)TTP適合関数を用いてW-TSPをよりよく解けることが示唆され,(2)最終W-TSPおよびTTP解は,最適TSPや重み付きグリーディ解と比較して異なる分布を示す。

関連論文リスト

• Semi-Supervised Coupled Thin-Plate Spline Model for Rotation Correction and Beyond [84.56978780892783]
  制御点が限られている複数のTPSを、より柔軟で強力な変換に繰り返し結合するCoupledTPSを提案する。 注記コストを考慮に入れた半教師付き学習手法を開発し、ラベルのないデータを活用することにより、ワープ品質を向上させる。 実験は、回転補正のための既存の最先端解よりもCoupledTPSの優位性と普遍性を示す。
  論文  参考訳（メタデータ） (2024-01-24T13:03:28Z)
• Equivariant Deep Weight Space Alignment [54.65847470115314]
  本稿では,ウェイトアライメント問題を解決するための学習を目的とした新しいフレームワークを提案する。 まず、重み調整が2つの基本対称性に一致することを証明し、それからこれらの対称性を尊重する深いアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2023-10-20T10:12:06Z)
• Solving Travelling Thief Problems using Coordination Based Methods [16.685542610215286]
  旅行盗難問題(TTP)は、郵便物収集などの実生活問題の代名詞である。 TTPでは、泥棒の移動速度がクナプサックの重量に依存するため、都市選択とアイテム選択の決定は緊密な調整が必要である。 既存のTPソルバは、都市選択とアイテム選択を別々に扱い、一方のタイプの決定は、他方のタイプを扱いながら変更しない。
  論文  参考訳（メタデータ） (2023-10-11T03:03:50Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。 RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2023-06-04T09:18:02Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Different Tunes Played with Equal Skill: Exploring a Unified Optimization Subspace for Delta Tuning [95.72622659619445]
  デルタチューニング(DET)は、事前学習言語モデル(PLM)を使用するための新しいパラダイムであると考えられている。 これまでのところ、異なる設計要素を持つ様々なDETが提案されており、微調整と同等のパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2022-10-24T14:57:35Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。 これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
  論文  参考訳（メタデータ） (2022-07-04T14:31:47Z)
• 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)
• Surrogate Assisted Optimisation for Travelling Thief Problems [14.836145520657592]
  トラベリング泥棒問題(TTP)は、2つの相互依存NPハードコンポーネントを含む多成分最適化問題である。 最近の最先端TTP解法は、根底にあるTPとKPの解を反復的かつインターリーブ的に修正している。 そこで本研究では,TTP ソリューションに繋がる初期 TSP ツアーの特徴を学習する適応的サロゲートモデルにより,探索をより効率的にすることを提案する。
  論文  参考訳（メタデータ） (2020-05-14T02:49:16Z)
• The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics [10.946271021892922]
  車両経路の領域におけるいくつかの重要な最適化問題は、古典的旅行セールスパーソン問題(TSP)の変種と見なすことができる。 本稿では,ツアー中に訪れたノードの重みに関して,旅行コストが増大するという意味で,ウェイトがそのような問題に与える影響について検討する。
  論文  参考訳（メタデータ） (2020-02-04T00:57:35Z)

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

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