An Interactive Algorithm for Multi-objective Route Planning

Tezcaner D., Koksalan M.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, vol.150, no.2, pp.379-394, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 150 Issue: 2
  • Publication Date: 2011
  • Doi Number: 10.1007/s10957-011-9838-y
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.379-394
  • Keywords: Multi-objective decision making, Combinatorial optimization, Interactive method, Multi-objective shortest path, Multi-objective traveling salesperson problem, Unmanned Air Vehicle
  • Middle East Technical University Affiliated: Yes


We address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem, where the UAV has to visit several targets and return to the base. We model this problem as a combination of two combinatorial problems. First, the path to be followed between each pair of targets should be determined. We model this as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. We model this as a multi-objective traveling salesperson problem (MOTSP). The overall problem is a combination of these two problems, which we define as a generalized MOTSP. We develop an exact interactive approach to identify the best paths and the best tour of a decision maker under a linear utility function.