日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

最適制御arXiv:2005.03186

巡回セールスマン問題とその変種に対する最適制御理論

An Optimal Control Theory for the Traveling Salesman Problem and Its Variants

シェア:XThreadsFacebookLINEはてブBluesky

巡回セールスマン問題とその多くの変種を、グラフ上の汎関数最適化問題として定式化する新しい枠組みを提案した論文。連続時間の動的モデルやコスト関数を直接組み込める利点を示している。

著者: I. M. Ross, R. J. Proulx, M. Karpenko

分類: math.OC, cs.AI, cs.DM, cs.RO

原文アブストラクト

We show that the traveling salesman problem (TSP) and its many variants may be modeled as functional optimization problems over a graph. In this formulation, all vertices and arcs of the graph are functionals; i.e., a mapping from a space of measurable functions to the field of real numbers. Many variants of the TSP, such as those with neighborhoods, with forbidden neighborhoods, with time-windows and with profits, can all be framed under this construct. In sharp contrast to their discrete-optimization counterparts, the modeling constructs presented in this paper represent a fundamentally new domain of analysis and computation for TSPs and their variants. Beyond its apparent mathematical unification of a class of problems in graph theory, the main advantage of the new approach is that it facilitates the modeling of certain application-specific problems in their home space of measurable functions. Consequently, certain elements of economic system theory such as dynamical models and continuous-time cost/profit functionals can be directly incorporated in the new optimization problem formulation. Furthermore, subtour elimination constraints, prevalent in discrete optimization formulations, are naturally enforced through continuity requirements. The price for the new modeling framework is nonsmooth functionals. Although a number of theoretical issues remain open in the proposed mathematical framework, we demonstrate the computational viability of the new modeling constructs over a sample set of problems to illustrate the rapid production of end-to-end TSP solutions to extensively-constrained practical problems.

関連論文

  1. 1パナソニックHDなど、触覚に即応する両手作業AI「T-Rex」を共同開発研究・技術
  2. 2川崎重工業のロボット外販を報道新製品・発表
  3. 3Boston Dynamics、GlobalFoundriesでAtlasを試験へ 半導体製造で2027年初頭から半導体・GPU
  4. 4日経クロステック、NVIDIA取締役会のファンCEO解任議論を報道 同社は同日、辞任を発表業界動向
  5. 5NVIDIA、ヒトの動きをロボットに適応する「SOMA Retargeter」を紹介研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI