Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem

Local search has been widely used in combinatorial optimization (Local Search in Combinatorial Optimization, Wiley, New York, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate "good" solutions with performance guarantee. In this paper, we introduce such an approach for the classical traveling salesman problem (TSP) problem (Proc. STOC'00, 2000, pp. 126-133). We show that it is possible to get in linear time, a 3/2-approximate Pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria TSP(1,2) problem where every edge is associated to a couple of distances which are either I or 2 (Math. Oper. Res. IS (1) (1993) 1). (C) 2003 Elsevier B.V. All rights reserved.