論文の概要: Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

• arxiv url: http://arxiv.org/abs/2608.10881v1
• Date: Tue, 11 Aug 2026 12:58:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-12 19:14:46.044602
• Title: Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming
• Title（参考訳）: ユークリッド旅行セールスパーソン問題に対する拡張フィルタリングアルゴリズムとその制約論理プログラミングにおける変種
• Abstract要約: トラベリングセールスパーソン問題(TSP)は、コンピュータ科学における最もよく知られた問題の1つであり、多くの工学的応用で発生している。 本稿では,制約論理プログラミング(CLP)で実装された新しいフィルタリングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 46.390064640459
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications, such as smart vehicles and intelligent transportation systems. In the "Euclidean" case, each node is defined by its coordinates in the plane and distances are computed using the Euclidean metric. In the Constraint Programming (CP) literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case; however this approach ignores the geometric information carried by the points' coordinates. In this work, we propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches. Moreover, we show how this methodology can be extended to other Euclidean variants of the TSP, including the Euclidean Generalized Traveling Salesperson Problem (EGTSP), which is relevant in practical routing and logistics applications. Experimental results demonstrate the computational advantages of the proposed approach.
• Abstract（参考訳）: トラベルセールスパーソン問題(TSP)は、コンピュータ科学における最もよく知られた問題の1つであり、スマートカーやインテリジェントトランスポートシステムなど、多くの工学的応用に現れる。 ユークリッド」の場合、各ノードは平面上の座標によって定義され、距離はユークリッド計量を用いて計算される。 Constraint Programming (CP) の文献では、ユークリッド TSP は一般に全距離行列を計算して一般の場合として扱うが、この手法は点座標が持つ幾何学的情報を無視している。 本研究では,制約論理プログラミング(Constraint Logic Programming, CLP)で実装された新しいフィルタリングアルゴリズムを提案する。 さらに,本手法を,実用的ルーティングやロジスティクスの応用に関係した,ユークリッド一般旅行販売問題 (EGTSP) など,他のTSPのユークリッド変種にも拡張可能であることを示す。 実験の結果,提案手法の計算上の利点が示された。

関連論文リスト

• Boundary condition enforcement with PINNs: a comparative study and verification on 3D geometries [0.0]
  物理インフォームドニューラルネットワーク(PINN)は物理学と工学における前方および逆問題の解法として広く研究されている。 メッシュの欠如と偏微分方程式(PDE)の強い形への依存が境界条件の強制を困難にしているため、複雑な三次元幾何学におけるPINNの研究は限られている。 本研究は, 有限要素法などの既存手法との競合が可能な, 成熟した数値法としてPINNを確立する方向への歩みを示すものである。
  論文  参考訳（メタデータ） (2025-12-16T22:15:01Z)
• Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport [0.0]
  複数のターゲットトラッキングでは、異なるトラッキングアルゴリズムの性能を評価することが重要である。 軌道一般化最適部分パターン割当量(TGOSPA)は,最近提案された評価基準である。 本稿では,TGOSPA問題を不均衡なマルチマルジナル最適輸送問題としてキャストすることで,TGOSPAメトリックを評価する近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-12T14:51:03Z)
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  ユークリッド距離情報点対を埋め込む適切な点を見つける問題は、コアタスクとサブマシン学習の問題の両方として生じる。 本稿では,最小限のサンプル数を考えると,この問題を解決することを目的とする。
  論文  参考訳（メタデータ） (2024-10-22T13:02:12Z)
• A GREAT Architecture for Edge-Based Graph Problems Like TSP [10.48061333321108]
  グラフエッジ注意ネットワーク(GREAT)と呼ばれる新しいGNNベースのエッジ指向ニューラルモデルを提案する。 GREATをエンコーダとして使用して、ルーティング問題インスタンスのプロパティをキャプチャし、強化学習フレームワークを構築する。 我々のフレームワークは、これらの問題の非ユークリッド変種と学習ベースのベンチマーク間の競合結果に最初に取り組みました。
  論文  参考訳（メタデータ） (2024-08-29T17:07:43Z)
• Fuse, Reason and Verify: Geometry Problem Solving with Parsed Clauses from Diagram [78.79651421493058]
  平面幾何学的問題解法 (PGPS) のニューラルネットワークモデルを提案し, モーダル融合, 推論過程, 知識検証の3つの重要なステップについて述べる。 推論のために、幾何学的推論過程を記述するための説明可能な解プログラムを設計し、自己限定デコーダを用いて解プログラムを自動回帰的に生成する。 また, PGPS9Kと呼ばれる大規模幾何学的問題データセットを構築し, テキスト節, 解法プログラム, 関連知識解決器の詳細なアノテーションを含む。
  論文  参考訳（メタデータ） (2024-07-10T02:45:22Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sysは、条件付き独立性(CI)制約下でのデータ修復に最適な輸送理論を利用するフレームワークである。 我々はSinkhornの行列スケーリングアルゴリズムにインスパイアされた反復アルゴリズムを開発し、高次元および大規模データを効率的に処理する。
  論文  参考訳（メタデータ） (2024-03-04T18:23:55Z)
• A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean TSP [0.0]
  本稿では,多次元スケーリングを用いて,まず非ユークリッド空間からユークリッド空間へ点を投影し,そのアルゴリズムを初期化する凸包を生成する。 提案アルゴリズムを評価するために、TSPLIBデータセットにセパレータを追加するか、L1ノルムを計量として使用することにより、非ユークリッド空間を生成する。
  論文  参考訳（メタデータ） (2023-02-05T13:56:19Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。 最終的に、より広い範囲、より広い範囲の作業を支援するのです。
  論文  参考訳（メタデータ） (2022-06-22T23:57:40Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Constraint Programming Algorithms for Route Planning Exploiting Geometrical Information [91.3755431537592]
  本稿では,経路計画問題に対する新しいアルゴリズムの開発に関する現在の研究動向について概説する。 これまでの研究は、特にユークリッド旅行セールスパーソン問題(ユークリッドTSP)に焦点を当ててきた。 目的は、将来ユークリッド自動車問題(ユークリッドVRP)など、同じカテゴリーの他の問題にも得られる結果を活用することである。
  論文  参考訳（メタデータ） (2020-09-22T00:51:45Z)

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

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