我们研究了欧几里得平面上（$\RR^2$）的邻域旅行商问题（TSPN），并提出了一个多项式时间近似方案（PTAS），当邻域为平行线段且长度在$[1, \lambda]$之间时，其中$\lambda \geq 1$为任意常数值。在TSPN（经典TSP的推广）中，每个客户代表度量空间中的一个点集（或邻域），目标是找到一条最小成本的旅行商巡回路径，访问每个客户集合至少一点。在欧几里得设定下，每个邻域是平面上的一个区域。即使在欧几里得设定下，TSPN比经典的TSP显著更难，因为它捕获了群体TSP。TSPN的一个显著情况是每个邻域都是一个线段。尽管对于肥体对象（具有有限重叠）的邻域存在PTAS，但对于长度统一的线段，TSPN仍然是\textbf{APX}-困难的。对于平行（单位长度）线段，二十多年前的最佳近似因子为$3\sqrt{2}$ \cite{DM03}。本文提出的算法解决了这一问题情形的近似性。我们的算法可以在时间$n^{O(\lambda/\eps^3)}$内找到问题实例的$(1+\eps)$-因子近似解，其中$n$为线段数量，长度范围在$[1,\lambda]$之间。

We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane ($\RR^2$) and present a Polynomial-Time Approximation Scheme (PTAS) when the neighbourhoods are parallel line segments with lengths between $ [1, \lambda] $ for any constant value $ \lambda \ge 1 $. In TSPN (which generalizes classic TSP), each client represents a set (or neighbourhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighbourhood is a region on the plane. TSPN is significantly more difficult than classic TSP even in the Euclidean setting, as it captures group TSP. A notable case of TSPN is when each neighbourhood is a line segment. Although there are PTASs for when neighbourhoods are fat objects (with limited overlap), TSPN over line segments is \textbf{APX}-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is $3\sqrt2$ from more than two decades ago \cite{DM03}. The PTAS we present in this paper settles the approximability of this case of the problem. Our algorithm finds a $ (1 + \eps) $-factor approximation for an instance of the problem for $n$ segments with lengths in $ [1,\lambda] $ in time $ n^{O(\lambda/\eps^3)} $.