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

Bin Xin*, Jie Chen, Dong Ling Xu, Yu Wang Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)941-954
Number of pages14
JournalKongzhi Lilun Yu Yinyong/Control Theory and Applications
Volume31
Issue number7
DOIs
Publication statusPublished - Jul 2014

Keywords

  • Curvature constraint
  • Differential evolution
  • Dubins traveling salesman problem with neighborhood
  • Dubins' vehicle
  • Path planning

Fingerprint

Dive into the research topics of 'Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood'. Together they form a unique fingerprint.

Cite this