論文の概要: Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks

• arxiv url: http://arxiv.org/abs/2605.14662v1
• Date: Thu, 14 May 2026 10:16:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-15 21:45:34.77278
• Title: Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks
• Title（参考訳）: ニューラルネットワークによる確率的マルチパストラベリングセールスマン問題のスケーラブル解法
• Authors: Xiaochen Chou, Ludovica Di Marco, Enza Messina,
• Abstract要約: 問題の目的は、不確実性の下で期待される総コストを最小限に抑えるハミルトンツアーを決定することである。 この研究の革新は、第2段階のリコース問題の期待値を近似するために、ニューラルネットワークベースの代理モデルを統合することである。
• 参考スコア（独自算出の注目度）: 1.5484595752241122
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multi-path Traveling Salesman Problem with stochastic travel costs arises in hybrid vehicle routing applications designed for Smart City and City Logistics, where multiple paths exist between each pair of locations. Travel times along these paths are typically affected by real-time traffic conditions and therefore modeled as stochastic. The objective of the problem is to determine a Hamiltonian tour that minimizes the expected total travel cost under uncertainty. In this work, we adopt a two-stage stochastic programming formulation. In the first stage, a predefined route specifying the sequence of locations to be visited is determined, while taking into consideration a second-stage recourse problem that selects the optimal path from the feasible set of alternative paths for each pair of locations, once real-time traffic conditions are realized. To reduce the computational burden imposed by the large number of scenarios required to capture travel time uncertainty, the innovation of this work is the integration of neural network-based surrogate models to approximate the expected value of the second-stage recourse problem. Different architectures and training strategies for the neural networks are proposed and analyzed, with performance evaluated in terms of computation time, solution quality, and generalization capability. Preliminary findings demonstrate the enhanced scalability and practical applicability of the approach for complex vehicle routing problems under uncertainty.
• Abstract（参考訳）: 確率的な旅行コストを伴うマルチパストラベリングセールスマン問題は、スマートシティとシティロジスティックス向けに設計されたハイブリッドカールーティングアプリケーションで発生し、それぞれの場所間で複数の経路が存在する。 これらの経路に沿った走行時間は、通常、リアルタイムの交通条件に影響され、確率的にモデル化される。 問題の目的は、不確実性の下で予想される総旅行コストを最小限に抑えるハミルトンツアーを決定することである。 本研究では,2段階確率計画法を採用する。 第1段階では、リアルタイムの交通条件が実現すれば、各一対の代替経路の集合から最適な経路を選択する第2段の経路問題を考慮して、訪れた場所の順序を規定する予め定義された経路を決定する。 旅行時間不確実性を捉えるのに必要なシナリオの多さによって課される計算負担を軽減するため、この研究の革新は、第2段階のリコース問題の期待値を近似するために、ニューラルネットワークベースの代理モデルを統合することである。 ニューラルネットワークの異なるアーキテクチャとトレーニング戦略を提案し,その性能を計算時間,ソリューション品質,一般化能力の観点から評価した。 予備的な知見は、不確実性下での複雑な車両ルーティング問題に対するアプローチのスケーラビリティと実用性の向上を示す。

関連論文リスト

• NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem [53.70554593151033]
  NaviFormerは、高レベル経路と低レベル軌道の両方を予測することによって、グローバルナビゲーション問題を解決する深層強化学習モデルである。 結果は,各サブプロブレムの制約や難易度を理解することができるため,NaviFormerの競合精度を示す。 計算速度が優れていることは、リアルタイムのミッションに適していることを証明している。
  論文  参考訳（メタデータ） (2026-04-18T11:32:34Z)
• Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM [0.0]
  構造化マルチエージェントプロジェクトでは、エージェントは事前に定義されたルートをたどらなければならず、リルーチンや不可能となる。 本稿では,各エージェントの割り当てられた経路の順序と名前付き経路の割り当てを保ちながら,経路制約付きマルチエージェント協調に対処する。
  論文  参考訳（メタデータ） (2026-03-23T12:34:18Z)
• Learning Minimally-Congested Drive Times from Sparse Open Networks: A Lightweight RF-Based Estimator for Urban Roadway Operations [0.0]
  本稿では,最小渋滞車走行時間に対する軽量な推定器を開発した。 オープンなロードネットワークデータ、速度制約、スパース制御/ターン機能をランダムなフォレストフレームワークに統合する。 大都市圏でのポイント・ツー・ポイントの忠実さを保ち、資源の要求を減らし、防御可能な性能推定を供給している。
  論文  参考訳（メタデータ） (2026-01-04T09:54:44Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。 本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。 このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。 ToP-Formerは、チームのオリエンテーリング問題を効率的に正確に解くために設計されたマルチエージェント経路計画ニューラルネットワークである。
  論文  参考訳（メタデータ） (2023-11-30T16:10:35Z)
• Dynamic Origin-Destination Matrix Estimation in Urban Traffic Networks [0.05735035463793007]
  この問題を二段階最適化問題としてモデル化する。 内部レベルでは、暫定的な旅行需要を前提として、動的な交通割当問題を解決し、利用者の出身地と目的地間のルーティングを決定する。 外層部では,交通ネットワーク内のセンサによって測定された車両数と内層部で発生したカウンタの差を最小限に抑えることを目的として,旅行数とその出発点および目的地の調整を行う。
  論文  参考訳（メタデータ） (2022-01-31T21:33:46Z)
• Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP [9.434400627011108]
  ニューラルネットワークモデルを用いてアーク確率を推定し、追加機能と自動パラメータ推定を可能にする。 本稿では,従来のマルコフ計数手法との違いについて検討し,この設定におけるニューラルネットワークの適用性について検討する。
  論文  参考訳（メタデータ） (2021-08-10T10:53:44Z)
• Learning-based Preference Prediction for Constrained Multi-Criteria Path-Planning [12.457788665461312]
  自動地上車両(AGV)の制約された経路計画法はそのような適用例である。 我々は、ニューラルネットワークモデルをトレーニングして、オフラインシミュレーションによって得られた知識を活用し、不確実な基準を予測する。 私たちはこのモデルをパスプランナに統合し、オンラインの問題を解決することができます。
  論文  参考訳（メタデータ） (2021-08-02T17:13:45Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  最適輸送のためのニューラルネットワークに基づく解法の性能を評価する。 既存の解法では,下流タスクでは良好に機能するにもかかわらず,最適な輸送マップを復元できないことがわかった。
  論文  参考訳（メタデータ） (2021-06-03T15:59:28Z)

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

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