Name
Title | ||
|---|---|---|
DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic |
Abstract | ||
|---|---|---|
In this paper we propose and evaluate an evolutionary-based hyper-heuristic approach, called EH-DVRP, for solving hard instances of the dynamic vehicle routing problem. A hyper-heuristic is a high-level algorithm, which generates or chooses a set of low-level heuristics in a common framework, to solve the problem at hand. In our collaborative framework, we have included three different types of low-level heuristics: constructive, perturbative, and noise heuristics. Basically, the hyper-heuristic manages and evolves a sophisticated sequence of combinations of these low-level heuristics, which are sequentially applied in order to construct and improve partial solutions, i.e., partial routes. In presenting some design considerations, we have taken into account the allowance of a proper cooperation and communication among low-level heuristics, and as a result, find the most promising sequence to tackle partial states of the (dynamic) problem. Our approach has been evaluated using the Kilby’s benchmarks, which comprise a large number of instances with different topologies and degrees of dynamism, and we have compared it with some well-known methods proposed in the literature. The experimental results have shown that, due to the dynamic nature of the hyper-heuristic, our proposed approach is able to adapt to dynamic scenarios more naturally than low-level heuristics. Furthermore, the hyper-heuristic can obtain high-quality solutions when compared with other (meta) heuristic-based methods. Therefore, the findings of this contribution justify the employment of hyper-heuristic techniques in such changing environments, and we believe that further contributions could be successfully proposed in related dynamic problems. |
Year | DOI | Venue |
|---|---|---|
2010 | https://doi.org/10.1007/s10732-010-9126-2 | Journal of Heuristics |
Keywords | Field | DocType |
Hyper-heuristics,Dynamic vehicle routing problem,Evolutionary algorithms,Heuristic search | Heuristic,Mathematical optimization,Vehicle routing problem,Evolutionary algorithm,Constructive,Hyper-heuristic,Network topology,Heuristics,Artificial intelligence,Dynamic problem,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 6 | 1381-1231 |
Citations | PageRank | References |
18 | 0.71 | 55 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pablo Garrido | 1 | 282 | 12.57 |
| María Cristina Riff | 2 | 200 | 23.91 |