On the discretized Dubins Traveling Salesman Problem
研究了一种变体旅行商问题，其中受运动学约束的车辆访问目标集的路径成本需最小化，通过离散化转化为整数优化问题，并建立了离散化水平与目标数量对性能的边界，数值实验表明低离散化水平可平衡计算时间与路径长度。
This research deals with a variation of the Traveling Salesman Problem in which the cost of a tour, during which a kinematically constrained vehicle visits a set of targets, has to be minimized. We are motivated by situations that include motion planning for unmanned aerial, marine, and ground vehicles, just to name a few possible application outlets. We discretize the original continuous problem and explicitly formulate it as an integer optimization problem. Then we develop a performance bound as a function of the discretization level and the number of targets. The inclusion of a discretization level provides an opportunity to achieve tighter bounds, compared to what has been reported in the literature. We perform a numerical study that quantifies the performance of the suggested approach. The suggested linkage between discretization level, number of targets, and performance may guide discretization-level choices for the solution of motion planning problems. Specifically, theoretical and numerical results indicate that, in many instances, discretization may be set at a low level to strike a balance between computational time and the length of a tour.