A flexible reference point-based multi-objective evolutionary algorithm: An application to the UAV route planning problem


COMPUTERS & OPERATIONS RESEARCH, vol.114, 2020 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 114
  • Publication Date: 2020
  • Doi Number: 10.1016/j.cor.2019.104811
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, ABI/INFORM, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, Metadex, zbMATH, Civil Engineering Abstracts
  • Keywords: Reference point, Preference-based evolutionary algorithms, UAV route planning, Multi-objective evolutionary optimization, Continuous terrain
  • Middle East Technical University Affiliated: Yes


We study the multi-objective route planning problem of an unmanned air vehicle (UAV) moving in a continuous terrain. In this problem, the UAV starts from a base, visits all targets and returns to the base in a continuous terrain that is monitored by radars. We consider two objectives: minimizing total distance and minimizing radar detection threat. This problem has infinitely many Pareto-optimal points and generating all those points is not possible. We develop a general preference-based multi-objective evolutionary algorithm to converge to preferred solutions. Preferences of a decision maker (DM) are elicited through reference point(s) and the algorithm converges to regions of the Pareto-optimal frontier close to the reference points. The algorithm allows the DM to change his/her reference point(s) whenever he/she so wishes. We devise mechanisms to prevent the algorithm from producing dominated points at the final population. We also develop mechanisms specific to the UAV route planning problem and test the algorithm on several UAV routing problems as well as other well-known problem instances. We demonstrate that our algorithm converges to preferred regions on the Pareto-optimal frontier and adapts to changes in the reference points quickly. (C) 2019 Elsevier Ltd. All rights reserved.