Two-phase Pareto local search for the biobjective traveling salesman problem

作     者：Lust, Thibaut Teghem, Jacques 

作者机构：Fac Polytech Mons Lab Math & Operat Res B-7000 Mons Belgium 

出 版 物：《JOURNAL OF HEURISTICS》 (试探法杂志)

年 卷 期：2010年第16卷第3期

页      面：475-510页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金："Fonds National de la Recherche Scientifique" 

主　　题：Combinatorial multiobjective optimization Biobjective traveling salesman problem Two-phase method Supported efficient solutions Pareto local search Data perturbation technique Performance assessment of multiobjective metaheuristics 

摘      要：In this work, we present a method, called Two-Phase Pareto Local Search, to find a good approximation of the efficient set of the biobjective traveling salesman problem. In the first phase of the method, an initial population composed of a good approximation of the extreme supported efficient solutions is generated. We use as second phase a Pareto Local Search method applied to each solution of the initial population. We show that using the combination of these two techniques: good initial population generation plus Pareto Local Search gives better results than state-of-the-art algorithms. Two other points are introduced: the notion of ideal set and a simple way to produce near-efficient solutions of multiobjective problems, by using an efficient single-objective solver with a data perturbation technique.