利用几何信息提升欧式旅行商问题求解效率
Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming
- 基于坐标信息设计新过滤算法，增强约束传播
- 在多个实例上显著减少搜索空间，加速求解
- 适用于物流、智能交通等实际路由场景
旅行商问题（TSP）是计算机科学中经典难题，广泛应用于智能车辆与智能交通系统。在欧式情形下，每个节点由平面上的坐标定义，距离采用欧几里得度量。传统约束规划方法通常计算完整距离矩阵，忽略点坐标的几何信息。本文提出新的过滤算法，基于坐标几何特性，在约束逻辑编程（CLP）框架中实现更强的约束传播。该方法可推广至欧式广义旅行商问题（EGTSP），在实际路径规划中具有应用价值。实验表明，所提方法在求解效率上具有明显优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。