On the performance of local search for the biobjective traveling salesman problem

Authors

Abstract

In this chapter we investigate experimentally the performance of multiobjective local search approaches that are based on the component-wise acceptance criterion search model. This model gives a framework for many well-known evolutionary and local search algorithms. Using the biobjective traveling salesman problem as an example application, we analyse the impact of three important algorithmic components on the performance of a simple local search algorithm that follows this search model: initialization strategy, neighborhood structure and archive bounding. By following principles of experimental design, we study the effects of each component, both in terms of solution quality and computation time. The experimental analysis indicates the existence of several complex trade-offs between solution quality and run-time for many of the choices available for each component.

Book Chapter

Advances in Multi-objective Nature Inspired Computing, pp. 143-165, Springer Verlag, January 2010