A Dynasearch Neighborhood for the Bicriteria Traveling Salesman Problem

In this paper we extend the dynasearch approach proposed by Congram, Potts and van de Velde [4, 17] in the context of multicriteria optimization for the bicriteria traveling salesman problem. The idea is to use local search with an exponential sized neighborhood which can be searched in polynomial time using dynamic programming and a rounding technique. Experimental results are presented to verify the quality of the proposed approach to obtain approximate Pareto curves for the bicriteria traveling salesman problem.