Improving Neighborhood Exploration Mechanism to Speed up PLS
Open Access
- 12 July 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 688-694
Abstract
As an extension of local search for multiobjective case, the basic version of Pareto Local Search (PLS) suffers from a poor anytime behavior. Researches have been carried out to overcome this drawback from different aspects. In this paper, we focus on the mechanism of neighborhood exploration in bi-objective Travelling Salesman Problems (bTSPs). Inspired by existing fast local search strategies for single objective TSP, we propose two speed-up strategies to help PLS quickly find promising neighboring solutions in bTSPs. In the experimental studies, we investigate the sensitivity of parameters and test the performance of several PLS variants with different combinations of the two strategies. The experimental results verify the effectiveness of the two strategies and their combination.Keywords
This publication has 15 references indexed in Scilit:
- Anytime Pareto local searchEuropean Journal of Operational Research, 2015
- Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategiesJournal of Heuristics, 2012
- On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problemsJournal of Heuristics, 2011
- Speed-up techniques for solving large-scale biobjective TSPComputers & Operations Research, 2010
- Two-phase Pareto local search for the biobjective traveling salesman problemJournal of Heuristics, 2009
- MOEA/D: A Multiobjective Evolutionary Algorithm Based on DecompositionIEEE Transactions on Evolutionary Computation, 2007
- Pareto Local Optimum Sets in the Biobjective Traveling Salesman Problem: An Experimental Study2004
- A fast and elitist multiobjective genetic algorithm: NSGA-IIIEEE Transactions on Evolutionary Computation, 2002
- On the performance of multiple-objective genetic local search on the 0/1 knapsack problem - a comparative experimentIEEE Transactions on Evolutionary Computation, 2002
- Fast Algorithms for Geometric Traveling Salesman ProblemsINFORMS Journal on Computing, 1992