Name
Title | ||
|---|---|---|
Perturbed Decomposition Algorithm applied to the multi-objective Traveling Salesman Problem. |
Abstract | ||
|---|---|---|
Dealing with multi-objective combinatorial optimization, this article proposes a new multi-objective set-based meta-heuristic named Perturbed Decomposition Algorithm (PDA). Combining ideas from decomposition methods, local search and data perturbation, PDA provides a 2-phase modular framework for finding an approximation of the Pareto front. The first phase decomposes the search into a number of linearly aggregated problems of the original multi-objective problem. The second phase conducts an iterative process: aggregated problems are first perturbed then selected and optimized by an efficient single-objective local search solver. Resulting solutions will serve as a starting point of a multi-objective local search procedure, called Pareto Local Search. After presenting a literature review of meta-heuristics on the multi-objective symmetric Traveling Salesman Problem (TSP), we conduct experiments on several instances of the bi-objective and tri-objective TSP. The experiments show that our proposed algorithm outperforms the best current methods on this problem. HighlightsA new Multi-Objective Decomposition algorithm called PDA is proposed.PDA introduces a new component to Decomposition algorithms: the Data Perturbation.PDA outperforms the best meta-heuristics on the MO Traveling Salesman Problem. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.cor.2016.04.025 | Computers & OR |
Keywords | Field | DocType |
Multi-objective combinatorial optimization,Multi-objective Traveling Salesman Problem,Meta-heuristics,Pareto Local search,Decomposition algorithm,Data perturbation | Bottleneck traveling salesman problem,Mathematical optimization,Algorithm,Multi-objective optimization,Combinatorial optimization,Travelling salesman problem,2-opt,Solver,Local search (optimization),Mathematics,Metaheuristic | Journal |
Volume | Issue | ISSN |
79 | C | 0305-0548 |
Citations | PageRank | References |
7 | 0.48 | 25 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cornu | 1 | 7 | 0.48 |
| Tristan Cazenave | 2 | 459 | 58.77 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |