On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems

This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such metho...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2012-04, Vol.18 (2), p.317-352
Main Authors: Liefooghe, Arnaud, Humeau, Jérémie, Mesmoudi, Salma, Jourdan, Laetitia, Talbi, El-Ghazali
Format: Article
Language:English
Subjects:
Approximation
Archives & records
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Computer Science
Genetic algorithms
Management Science
Mathematics
Mathematics and Statistics
Neighborhoods
Operations Research
Operations Research/Decision Theory
Optimization
Scheduling
Searches
Studies
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition. The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental results and a statistical comparison are reported in the paper, and some directions for future research are highlighted.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-011-9181-3