論文の概要: On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints

• arxiv url: http://arxiv.org/abs/2604.14745v1
• Date: Thu, 16 Apr 2026 07:57:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:31.792918
• Title: On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints
• Title（参考訳）: 時間窓の制約が変化するトラベリングセールスマン問題に対する反復問題解決法の適用について
• Authors: Hy Nguyen, Thanh Nguyen Pham, Helen Yuliana Angmalisang, Liam Wigney, Frank Neumann,
• Abstract要約: 時間窓を用いた旅行セールスパーソン問題(TSPTW)について検討する。 TSPTWは、旅行時間行列が固定されるが、関連するタスク間で時間-ウィンドウの制約が変化する設定で発生することが多い。 我々は、従来のタスクの最良のツアーから各タスクを初期化する反復プロトコルと、標準の from-scratch プロトコルを比較した。
• 参考スコア（独自算出の注目度）: 4.734583324730717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many real-world settings, problem instances that need to be solved are quite similar, and knowledge from previous optimization runs can potentially be utilized. We explore this for the Traveling Salesperson problem with time windows (TSPTW), which often arises in settings where the travel-time matrix is fixed but time-window constraints change across related tasks. Existing TSPTW studies, however, have not systematically compared solving such task sequences independently with sequential transfer from previously solved tasks. We address this gap using a multi-task benchmark in which each base instance is expanded into five related tasks under two environments: partial time-window expansion and swap-additive time reassignment. We compare a standard from-scratch protocol with an iterative protocol that initializes each task from the best tour of the previous task, using the popular local search approaches LNS, VNS, and LKH-3 under a common penalized-score objective. Our experimental results show that the iterative protocol is consistently superior in the progressive-relaxation setting and generally competitive under swap-additive changes, with improvements increasing on more difficult instances.
• Abstract（参考訳）: 多くの実世界の環境では、解決すべき問題インスタンスはよく似ており、以前の最適化から得た知識を活用できる可能性がある。 旅行時間行列が固定されているが、関連するタスク間で時間-ウィンドウ制約が変化する設定でしばしば発生する、時間窓付きトラベリングセールスパーソン問題(TSPTW)について検討する。 しかし、既存のTSPTW研究は、これらのタスクシーケンスを、以前に解決されたタスクからのシーケンシャルトランスファーと独立に体系的に比較していない。 このギャップにはマルチタスクのベンチマークを用いて対処し、各ベースインスタンスを2つの環境下で5つの関連するタスクに拡張する。 我々は,一般的なペナル化スコアの目的の下で,LNS,VNS,LKH-3を用いて,従来のタスクの最良のツアーから各タスクを初期化するイテレーティブプロトコルと比較する。 実験の結果、反復プロトコルはプログレッシブ・ラキセーション・セッティングにおいて一貫して優れており、スワップ・アダプティブな変更の下では一般的に競争力があり、より困難なインスタンスでは改善が進んでいることがわかった。

関連論文リスト

• Learning to Solve Orienteering Problem with Time Windows and Variable Profits [5.973834170744548]
  時間ウィンドウと可変利益(OPTWVP)によるオリエンテーリング問題は、多くの実世界のアプリケーションで一般的である。 サービス時間誘導軌道(DeCoST)を用いた学習型2段階Decoupled離散連続最適化を提案する。 OPTWVPインスタンスの実験では、DeCoSTは最先端のコンストラクティブソルバと最新のメタヒューリスティックアルゴリズムの両方より優れていることが示されている。
  論文  参考訳（メタデータ） (2026-03-06T13:24:10Z)
• Towards Remote Sensing Change Detection with Neural Memory [61.39582645714727]
  ChangeTitansは、リモートセンシングによる変更検出のためのTitansベースのフレームワークである。 まず、ニューラルネットワークと局所的な注意をセグメント化して統合するVTitansを提案する。 次に,階層型VTitans-Adapterを提案する。 第3に、2ストリーム融合モジュールであるTS-CBAMを導入し、擬似変化を抑制し、検出精度を高める。
  論文  参考訳（メタデータ） (2026-02-11T03:50:51Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  本稿では,現実の調理シナリオに基づいた新しいベンチマークフレームワークRecipe2Planを紹介する。 従来のベンチマークとは異なり、Recipe2Planは並列タスク実行による調理時間を最適化するためにエージェントに挑戦する。
  論文  参考訳（メタデータ） (2025-03-04T03:27:02Z)
• FAMO: Fast Adaptive Multitask Optimization [48.59232177073481]
  本稿では,動的重み付け手法であるFast Adaptive Multitask Optimization FAMOを導入する。 この結果から,FAMOは最先端の勾配操作技術に匹敵する,あるいは優れた性能を達成できることが示唆された。
  論文  参考訳（メタデータ） (2023-06-06T15:39:54Z)
• Event-Triggered Time-Varying Bayesian Optimization [47.30677525394649]
  本稿では,対象関数の変化を検出してデータセットをリセットするまで,最適化問題を静的に扱うイベントトリガーアルゴリズムET-GP-UCBを提案する。 これにより、アルゴリズムは正確な事前知識を必要とせずに、オンラインで時間変化を実現することができる。 時間的変化を正確に知ることなく、適応的リセットに対する後悔境界を導出し、ET-GP-UCBが合成データと実世界のデータの両方で競合するGP-UCBアルゴリズムより優れていることを示す数値実験を行った。
  論文  参考訳（メタデータ） (2022-08-23T07:50:52Z)
• Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
  ジョブショップスケジューリング問題(JSP、Job-shop Scheduling Problem)は、ジョブを含むタスクをできるだけ早く完了するように、マシンを共有するタスクをシーケンスに配置する、よく知られた、困難な最適化問題である。 本稿では,ASP(Multi-shot Answer Set Programming)の解法を用いて,操作を逐次スケジュールし,最適化可能な時間窓への問題分解について検討する。
  論文  参考訳（メタデータ） (2022-05-16T09:33:00Z)
• On Steering Multi-Annotations per Sample for Multi-Task Learning [79.98259057711044]
  マルチタスク学習の研究はコミュニティから大きな注目を集めている。 目覚ましい進歩にもかかわらず、異なるタスクを同時に学習するという課題はまだ検討されていない。 従来の研究は、異なるタスクから勾配を修正しようとするが、これらの手法はタスク間の関係の主観的な仮定を与え、修正された勾配はより正確でないかもしれない。 本稿では,タスク割り当てアプローチによってこの問題に対処する機構であるタスク割当(STA)を紹介し,各サンプルをランダムにタスクのサブセットに割り当てる。 さらなる進展のために、我々は全てのタスクを反復的に割り当てるためにInterleaved Task Allocation(ISTA)を提案する。
  論文  参考訳（メタデータ） (2022-03-06T11:57:18Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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