一种求解带邻域的Dubins旅行商问题的坐标下降法（英文）

作者：陈征; 孙晨浩; 邵雪明^*; 赵文杰

来源：Frontiers of Information Technology & Electronic Engineering, 2021, 22(05): 732-741.

• Dubins飞行器
• 坐标下降法
• Dubins旅行商问题

由于带邻域的Dubins旅行商问题(Dubins traveling salesman problem with neighborhoods, DTSPN)是无人机执行多目标区域侦察任务需要解决的核心问题,国内外学者对DTSPN问题的快速求解方法进行了广泛研究。本文针对目前已有方法存在计算资源消耗大等情况,设计了一种用于求解DTSPN问题的无梯度坐标下降方法。该方法的核心步骤是将DTSPN问题分解为一系列子问题,对于每个子问题仅需计算从初始点经过一个区域到达目标点的最短路径。通过研究子问题最短路径的几何特征,并将几何特征与二分法相结合,可得到快速计算子问题的鲁棒算法。然后,将子问题计算方法与坐标下降法相结合,构建了能快速求解DTSPN问题的计算方法。最后,为验证所提方法的有效性和快速性,将所提方法与几种传统算法进行仿真对比。

• 单位
  流体动力与机电系统国家重点实验室; 航天学院; 浙江大学