An evolutionary approach to generalized biobjective traveling salesperson problem

Koksalan M., Ozturk D. T.

COMPUTERS & OPERATIONS RESEARCH, vol.79, pp.304-313, 2017 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 79
  • Publication Date: 2017
  • Doi Number: 10.1016/j.cor.2016.04.027
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.304-313
  • Middle East Technical University Affiliated: Yes


We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approxiMation of nondominated points. For this, we approximate the efficient tours using approximate representations of the efficient edges between node pairs in the objective function space. We test the algorithm on several randomly-generated problem instances and our experiments show that the evolutionary algorithm approximates the nondominated set well. (C) 2016 Elsevier Ltd. All rights reserved.