由于带邻域的Dubins旅行商问题（Dubins traveling salesman problem with neighborhoods, DTSPN）是无人机执行多目标区域侦察任务需要解决的核心问题，国内外学者对DTSPN问题的快速求解方法进行了广泛研究。本文针对目前已有方法存在计算资源消耗大等情况，设计了一种用于求解DTSPN问题的无梯度坐标下降方法。该方法的核心步骤是将DTSPN问题分解为一系列子问题，对于每个子问题仅需计算从初始点经过一个区域到达目标点的最短路径。通过研究子问题最短路径的几何特征，并将几何特征与二分法相结合，可得到快速计算子问题的鲁棒算法。然后，将子问题计算方法与坐标下降法相结合，构建了能快速求解DTSPN问题的计算方法。最后，为验证所提方法的有效性和快速性，将所提方法与几种传统算法进行仿真对比。
Abstract：
In this study, we focus mainly on the problem of finding the minimum-length path through a set of circular regions by a fixed-wing unmanned aerial vehicle. Such a problem is referred to as the Dubins traveling salesman problem with neighborhoods (DTSPN). Algorithms developed in the literature for solving DTSPN either are computationally demanding or generate low-quality solutions. To achieve a better trade-off between solution quality and computational cost, an efficient gradient-free descent method is designed. The core idea of the descent method is to decompose DTSPN into a series of subproblems, each of which consists of finding the minimum-length path of a Dubins vehicle from a configuration to another configuration via an intermediate circular region. By analyzing the geometric properties of the subproblems, we use a bisection method to solve the subproblems. As a result, the descent method can efficiently address DTSPN by successively solving a series of subproblems. Finally, several numerical experiments are carried out to demonstrate the descent method in comparison with several existing algorithms.
