Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood

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.