TY - JOUR
T1 - Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood
AU - Xin, Bin
AU - Chen, Jie
AU - Xu, Dong Ling
AU - Chen, Yu Wang
PY - 2014/7
Y1 - 2014/7
N2 - 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.
AB - 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.
KW - Curvature constraint
KW - Differential evolution
KW - Dubins traveling salesman problem with neighborhood
KW - Dubins' vehicle
KW - Path planning
UR - http://www.scopus.com/inward/record.url?scp=84905387124&partnerID=8YFLogxK
U2 - 10.7641/CTA.2014.40280
DO - 10.7641/CTA.2014.40280
M3 - Article
AN - SCOPUS:84905387124
SN - 1000-8152
VL - 31
SP - 941
EP - 954
JO - Kongzhi Lilun Yu Yinyong/Control Theory and Applications
JF - Kongzhi Lilun Yu Yinyong/Control Theory and Applications
IS - 7
ER -