A study of global convexity for a multiple objective travelling salesman problem

Global convexity, or heuristic concentration, has been mentioned in the literature as a reason for the success of many single objective metaheuristics. Global convexity is not an intrinsic characteristic of a combinatorial problem, but rather a property of the topology induced in a solution space by, for example, a neighborhood operator. This paper presents a study of global convexity for a multiple objective travelling salesman problem using the 2-0PT operator. The analysis is based on local search and includes extensive experimentation with the weighted sums program and augmented Tchebycheff program. We study the concentration of local optima for instances of scalarizing programs, the differences observed between solutions and points generated with different weights, and the stability of the best local optima for small weight variations. The exact global optima for weighted sums programs are also generated and exhibit concentration characteristics. The results are promising in that they confirm the existence of global convexity and might be used as a basis for understanding and building new metaheuristics for multiple objective optimization problems.