論文の概要: ViTSP: A Vision Language Models Guided Framework for Large-Scale Traveling Salesman Problems

• arxiv url: http://arxiv.org/abs/2509.23465v1
• Date: Sat, 27 Sep 2025 19:27:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:19.243071
• Title: ViTSP: A Vision Language Models Guided Framework for Large-Scale Traveling Salesman Problems
• Title（参考訳）: ViTSP:大規模旅行セールスマン問題のためのビジョン言語モデルガイドフレームワーク
• Authors: Zhuoli Yin, Yi Ding, Reem Khir, Hua Cai,
• Abstract要約: トラベリングセールスマン問題の解決 (TSP) は、NP-hard でありながら、幅広い現実世界の応用に基本である。 この研究は、事前学習された視覚言語モデル(VLM)を利用して、ソリューションプロセスを視覚的にガイドする新しいフレームワークであるViTSPを提案する。 ViTSPは、0.2%以下の平均最適性ギャップを持つソリューションを一貫して達成し、既存の学習ベースの手法より優れている。
• 参考スコア（独自算出の注目度）: 5.466485171752612
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving Traveling Salesman Problem (TSP) is NP-hard yet fundamental for wide real-world applications. Classical exact methods face challenges in scaling, and heuristic methods often require domain-specific parameter calibration. While learning-based approaches have shown promise, they suffer from poor generalization and limited scalability due to fixed training data. This work proposes ViTSP, a novel framework that leverages pre-trained vision language models (VLMs) to visually guide the solution process for large-scale TSPs. The VLMs function to identify promising small-scale subproblems from a visualized TSP instance, which are then efficiently optimized using an off-the-shelf solver to improve the global solution. ViTSP bypasses the dedicated model training at the user end while maintaining effectiveness across diverse instances. Experiments on real-world TSP instances ranging from 1k to 88k nodes demonstrate that ViTSP consistently achieves solutions with average optimality gaps below 0.2%, outperforming existing learning-based methods. Under the same runtime budget, it surpasses the best-performing heuristic solver, LKH-3, by reducing its gaps by 12% to 100%, particularly on very-large-scale instances with more than 10k nodes. Our framework offers a new perspective in hybridizing pre-trained generative models and operations research solvers in solving combinatorial optimization problems, with practical implications for integration into more complex logistics systems. The code is available at https://anonymous.4open.science/r/ViTSP_codes-6683.
• Abstract（参考訳）: トラベリングセールスマン問題の解決 (TSP) は、NP-hard でありながら、幅広い現実世界の応用に基本である。 古典的な正確な手法はスケーリングの課題に直面し、ヒューリスティックな手法はドメイン固有のパラメータの校正を必要とすることが多い。 学習ベースのアプローチは将来性を示しているが、固定されたトレーニングデータのために、一般化の貧弱さとスケーラビリティの制限に悩まされている。 この研究は、VLM(Pre-trained Vision Language Model)を活用して、大規模TSPのソリューションプロセスを視覚的にガイドする新しいフレームワークであるViTSPを提案する。 VLMs関数は、可視化されたTSPインスタンスから有望な小規模サブプロブレムを識別し、オフザシェルフソルバを用いて効率よく最適化し、グローバルソリューションを改善する。 ViTSPは、さまざまなインスタンスにまたがる有効性を保ちながら、ユーザエンドでの専用のモデルトレーニングをバイパスする。 1kノードから88kノードまでの実世界のTSPインスタンスの実験では、ViTSPは0.2%以下の平均最適性ギャップを持つソリューションを一貫して達成し、既存の学習ベースの手法より優れていることが示されている。 同じランタイム予算の下では、特に10kノード以上の大規模インスタンスにおいて、そのギャップを12%から100%削減することで、最高のパフォーマンスのヒューリスティック解決器であるLKH-3を上回っている。 我々のフレームワークは、事前学習された生成モデルと運用研究をハイブリッド化する新しい視点を提供し、より複雑なロジスティクスシステムに統合するための実践的な意味を持つ組合せ最適化問題を解く。 コードはhttps://anonymous.4open.science/r/ViTSP_codes-6683で公開されている。

関連論文リスト

• Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem [5.627942507745463]
  ラストマイル配送を動的にリルートするといった現実世界のロジスティクス問題では、高速な推論時間で解決を要求される。 ニューラルネットワークは、訓練された合成データを超えた一般化に苦慮していることを示す。 我々は,ジェネレーティブ・サンプリング(COGS)を用いたコンビニショナル・オプティマイゼーションを行い,生成型トラベリングセールスマン問題モデルからトレーニングデータをサンプリングした。
  論文  参考訳（メタデータ） (2025-08-12T08:04:16Z)
• EfficientLLaVA:Generalizable Auto-Pruning for Large Vision-language Models [64.18350535770357]
  マルチモーダル推論の効率を高めるために,大規模視覚言語モデルの自動プルーニング手法を提案する。 提案手法では,所望のプルーニングポリシーを探索するために,少数のサンプルのみを活用する。 視覚的質問応答のためのScienceQA, Vizwiz, MM-vet, LLaVA-Benchデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2025-03-19T16:07:04Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  グラフ拡散型ソリューション生成(GDSG)法を提案する。 このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。 グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
  論文  参考訳（メタデータ） (2024-12-11T11:13:43Z)
• An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems [22.792870849003137]
  本研究では、トラベリングセールスマン問題(TSP)を解決するためのデータ駆動グラフ表現学習法を提案する。 残留ゲートエンコーダは遅延エッジ埋め込みを学習するために訓練され、次いでエッジ中心のデコーダでリンク予測をエンドツーエンドに出力する。 実験結果から,提案したエッジ対応グラフオートエンコーダモデルにより,高い競合性能が得られた。
  論文  参考訳（メタデータ） (2023-10-10T11:42:49Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)

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

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