引用本文:辛斌,陈杰,徐冬玲,陈玉旺.混合编码差分进化算法求解含邻域Dubins旅行商问题(英文)[J].控制理论与应用,2014,31(7):941~954.[点击复制]
XIN Bin,CHEN Jie,XU Dong-ling,CHEN Yu-wang.Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood[J].Control Theory and Technology,2014,31(7):941~954.[点击复制]
混合编码差分进化算法求解含邻域Dubins旅行商问题(英文)
Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood
摘要点击 3047  全文点击 2143  投稿时间：2014-04-05  修订日期：2014-05-17
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2014.140280
  2014,31(7):941-954
中文关键词  Dubins车  路径规划  曲率约束  含邻域Dubins旅行商问题  差分进化
英文关键词  Dubins’ vehicle  path planning  curvature constraint  Dubins traveling salesman problem with neighbor- hood  differential evolution
基金项目  
作者单位E-mail
辛斌* 北京理工大学 自动化学院
复杂系统智能控制与决策国家重点实验室 		brucebin@bit.edu.cn 
陈杰 北京理工大学 自动化学院
复杂系统智能控制与决策国家重点实验室 		 
徐冬玲 曼彻斯特大学 商学院 认知与决策科学研究中心  
陈玉旺 曼彻斯特大学 商学院 认知与决策科学研究中心  
中文摘要
      含邻域Dubins旅行商问题(DTSPN)是一个具有挑战性的混合变量优化问题, 它源于Dubins车的运动规划, 例如轨迹受曲率约束的高速飞行器. 本文在对DTSPN的相关研究进行综述的基础上, 提出两种混合编码差分进化 算法来有效求解DTSPN, 这两种算法分别采用完整编码方案和部分编码方案. 完整编码差分进化算法在整个解空 间中搜索最优的Dubins路径, 有利于充分探索搜索空间. 通过对Dubins车在相邻两点间移动时的终端朝向进行松 弛, 本文提出一种部分编码差分进化算法, 在解的质量和计算时间方面实现了较好的权衡. 比较性计算实验包含两 种差分进化算法以及现有文献中的两种先进DTSPN算法, 实验结果表明基于终端朝向松弛和部分编码的差分进化 算法能够以较小的计算代价得到DTSPN的高质量解, 明显优于其他算法.
英文摘要
      The Dubins traveling salesman problem with neighborhood (DTSPN) is a challenging mixed-variable optimization problem, stemming from the motion planning of a Dubins vehicle, e.g. an aircraft moving at a high speed, whose trajectory is restricted by curvature constraints. In this paper, a survey result of DTSPN is firstly provided; then, in order to solve DTSPN efficiently, we propose two hybrid encoding-based differential evolution (DE) algorithms, which adopt complete encoding scheme and partial encoding scheme, respectively. The DE algorithm with complete encoding searches for optimal Dubins tours in the entire solution space, in favor of a sufficient exploration of the search space. By relaxing the terminal heading of a Dubins vehicle when it moves from one point to another, a novel DE with partial encoding is proposed to achieve a better tradeoff between solution quality and computational time. Comparative experiments, involving the two DE algorithms and two state-of-the-art DTSPN algorithms identified in literature, show that the DE based on terminal heading relaxation and partial encoding can find high-quality solutions to DTSPN with lower computation cost, and has remarkable advantages over the other algorithms.