論文の概要: Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints

• arxiv url: http://arxiv.org/abs/2604.13469v1
• Date: Wed, 15 Apr 2026 04:47:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.384076
• Title: Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints
• Title（参考訳）: 決定的・確率的制約を伴う旅行中のパッケージングに対するグリーディアプローチ
• Authors: Thilina Pathirage Don, Aneta Neumann, Frank Neumann,
• Abstract要約: 旅行時パッキング(英: packing while travelling problem, PWT)は、最適化問題 TTP のNPハードサブプロブレムである。 本稿では,PWTに適した新たな報酬関数を導入し,それを超ヒューリスティックなフレームワークに拡張する。
• 参考スコア（独自算出の注目度）: 8.727449523567673
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The travelling thief problem (TTP) is a well-known multi-component optimisation problem that captures the interdependence between two components: the tour across cities and the packing of items. The packing while travelling problem (PWT) is an NP-hard subproblem of TTP where the packing of items should be optimised for a given fixed tour. In many solvers, the packing component is often addressed using greedy heuristics. Here, the use of suitable greedy functions is essential for the success of greedy algorithms. In this paper, we introduce new reward functions tailored to the PWT and extend them to a hyper-heuristic framework to achieve further advantage. Furthermore, we investigate the chance constrained PWT for greedy approaches and adopt the newly introduced reward functions for stochastic weights. The experimental results clearly demonstrate the benefit of the tailored heuristics over the standard heuristics in both deterministic and stochastic constraints.
• Abstract（参考訳）: トラベリング泥棒問題(TTP)は、都市を横断する旅行とアイテムの梱包という2つのコンポーネント間の相互依存を捉える、よく知られた多成分最適化問題である。 旅行時パッキング (PWT) は、TTPのNPハードサブプロブレムであり、アイテムのパッキングは所定のツアーのために最適化されるべきである。 多くの解法では、パッキング成分は強欲なヒューリスティックによって対処されることが多い。 ここでは、greedyアルゴリズムの成功には、適切なgreedy関数の使用が不可欠である。 本稿では,PWTに適した新たな報酬関数を導入し,それを超ヒューリスティックなフレームワークに拡張し,さらなる優位性を実現する。 さらに, 難解なアプローチに対する制約付きPWTについて検討し, 確率重みに対する新たな報酬関数を適用した。 実験結果は、決定論的制約と確率論的制約の両方において、標準ヒューリスティックスに対する調整されたヒューリスティックスの利点を明らかに示している。

関連論文リスト

• Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem [10.506038775815094]
  古典的トラベリング泥棒問題 (TTP) のバリエーションとして, 確率制約型トラベリング泥棒問題 (TTP) が導入された。 本研究では,限られた重み付きシナリオを用いて,確率制約付きTPを特徴付ける。 古典的TTPのために開発された進化的アルゴリズムと手順の集合を組み込み、問題を重み付けしたシナリオベース表現に適応する公式を組み込む。
  論文  参考訳（メタデータ） (2025-05-01T03:30:21Z)
• Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
  我々は、モデルフリーQ値ポリシー近似をPointer Networks(Ptr-Nets)と統合したハイブリッドニューラルネットワークであるPointer Q-Network(PQN)を紹介する。 実験により,本手法の有効性を実証し,不安定な環境でモデルをテストする。
  論文  参考訳（メタデータ） (2023-11-05T12:03:58Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Dealing with Sparse Rewards in Continuous Control Robotics via Heavy-Tailed Policies [64.2210390071609]
  本稿では,連続制御問題におけるスパース報酬の課題に対処するため,HT-PSG(Heavy-Tailed Policy Gradient)アルゴリズムを提案する。 高平均累積報酬の観点から,全タスクに一貫したパフォーマンス向上を示す。
  論文  参考訳（メタデータ） (2022-06-12T04:09:39Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  フロゼットボン2021ローランで提唱された低ランク最適輸送(LOT)アプローチ LOTは興味のある性質と比較した場合、エントロピー正則化の正当な候補と見なされる。 本稿では,これらの領域のそれぞれを対象とし,計算OTにおける低ランクアプローチの影響を補強する。
  論文  参考訳（メタデータ） (2022-05-24T20:51:37Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• 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)
• Surrogate Assisted Optimisation for Travelling Thief Problems [14.836145520657592]
  トラベリング泥棒問題(TTP)は、2つの相互依存NPハードコンポーネントを含む多成分最適化問題である。 最近の最先端TTP解法は、根底にあるTPとKPの解を反復的かつインターリーブ的に修正している。 そこで本研究では,TTP ソリューションに繋がる初期 TSP ツアーの特徴を学習する適応的サロゲートモデルにより,探索をより効率的にすることを提案する。
  論文  参考訳（メタデータ） (2020-05-14T02:49:16Z)

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

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