Design and analysis of stochastic local search for the multiobjective traveling salesman problem



Stochastic local search (SLS) algorithms are typically composed of a number of different components, each of which should contribute significantly to the final algorithm's performance. If the goal is to design and engineer effective SLS algorithms, the algorithm developer requires some insight into the importance and the behavior of possible algorithmic components. In this paper, we analyze algorithmic components of stochastic local search algorithms for the multiobjective travelling salesman problem. The analysis is done using a careful experimental design for a generic class of SLS algorithms for multiobjective combinatorial optimization. Based on the insights gained, we engineer SLS algorithms for this problem. Experimental results show that these SLS algorithms, despite their conceptual simplicity, outperform a wellk-nown memetic algorithm for a range of benchmark instances with two and three objectives.


Multiobjective Optimization


Computers & Operations Research, Vol. 36, #9, pp. 2619-2631, September 2009

Cited by

Year 2015 : 4 citations

 An adaptive memetic framework for multi-objective combinatorial optimization problems: studies on software next release and travelling salesman problems
X Cai, X Cheng, Z Fan, E Goodman, L Wang
Soft Computing, 2015

 Hybrid evolutionary algorithms for the Multiobjective Traveling Salesman Problem
ID Psychas, E Delimpasi, Y Marinakis
Expert Systems with Applications, 2015

 Optimum Allocation of Computer Resources through Goal Programming
Y Macha, SD Sarma, GR Babu, S Kumar
IJITR, 2015

 A Hybrid Algorithm for Stochastic Multiobjective Programming Problem
Z Wang, J Guo, M Zheng, Q He
Evolutionary Multi-Criterion Optimization, 2015

Year 2014 : 4 citations

 Alfredo Núñez, Cristián E. Cortés, Doris Sáez, Bart De Schutter and Michel Gendreau, Multiobjective model predictive control for dynamic pickup and delivery problems, Control Engineering Practice 2014

 K Florios, G Mavrotas, Generation of the exact Pareto set in Multi-Objective Traveling Salesman and Set Covering Problems, Applied Mathematics and Computation, 2014

 R Hartert, P Schaus, A Support-Based Algorithm for the Bi-Objective Pareto Constraint, Publication/NA, 2014

 L Ke, Q Zhang, R Battiti, Hybridization of Decomposition and Local Search for Multiobjective Optimization, IEEE Transactions on Cybernetics, 2014

Year 2013 : 1 citations

 JB Mendes, Uma Abordagem Multiobjetivo para o Problema de Despacho de Caminhões em Minas a Céu Aberto, Publication/NA, 2013

Year 2012 : 3 citations

 A Liefooghe, J Humeau, S Mesmoudi, L Jourdan, On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems, Journal of Heuristics, 2012

 CC Kiang, R Srinivasan, An artificial immune system for adaptive fault detection, diagnosis and recovery, International Journal of Advances in Engineering Sciences and Applied Mathematics, 2012

 Chee Chun Kiang and Rajagopalan Srinivasan, Journal of Advances in Engineering Sciences, 2012. (in press).

Year 2011 : 3 citations

 A. Segun Adeyefa, Monga K. Luhandjula, Multiobjective Stochastic Linear Programming: An Overview, American Journal of Operations Research, 2011, 1, 203-213, 2011

 Arnaud Liefooghe, Jérémie Humeau, Salma Mesmoudi, Laetitia Jourdan and El-Ghazali Talbi, On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems, Journal of Heuristics, 2011.

 C. A. Laurentys, Reinaldo M. Palhares, Walmir M. Caminhas: A novel Artificial Immune System for fault behavior detection. Expert Syst. Appl. 38(6): 6957-6966, 2011

Year 2010 : 2 citations

 Thibaut Lust and Jacques Teghem, The Multiobjective Traveling Salesman Problem: A Survey and a New Approach, Advances in Multi-Objective Nature Inspired Computing, Studies in Computational Intelligence, Springer, 2010

 J. Silberholz and B. Golden , Comparison of Metaheuristics, Handbook of Metaheuristics, International Series in Operations Research & Management Science, Vol. 146, Springer.

Year 2009 : 3 citations

 J. Silberholz and B. Golden , Comparison of Metaheuristics, Technical Report CSCAMM-09-13, Center for Scientific Computation and Mathematical Modeling, University of Maryland, USA, 2009

 S. Eppe. Application of the Ant Colony Optimization Metaheuristic to Multi-objective Optimization Problems. MSc. thesis, CoDE Department, Université Libre de Bruxelles, Brussels, Belgium, 2009.

 T. Lust,: New metaheuristics for solving MOCO problems: application to the knapsack, traveling salesman problems and IMRT optimization. PhD Thesis, University of Mons, Belgium, 2009.

Year 1999 : 1 citations

 CAC Coello, List of references on evolutionary multiobjective optimization, Laboratorio Nacional de Informática Avanzada, …, 1999