Evolutionary Algorithm for Vehicle Routing with Diversity Oscillation Mechanism
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
2022
chapter in monograph / paper
english
- Diversity management
- Vehicle routing
- Hybrid evolutionary algorithms
- Multi-population algorithms
EN We propose an evolutionary algorithm with a novel diversity oscillation mechanism for the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). Evolutionary algorithms are among state-of-the-art methods for vehicle routing problems and the diversity management is the key component of many of these algorithms. In our algorithm the diversity level slowly oscillates between its minimum and maximum value, however, whenever a new best solution is found the algorithm switches to decreasing the diversity level in order to intensify the search in the vicinity of the new best solution. We use also an additional population of high quality diverse solutions, which may be used to re-fill the main population when the diversification level is increased. The results of the computational experiment indicate that the proposed mechanism significantly improves the performance of our hybrid evolutionary algorithm on typical CVRPTW benchmarks and that the proposed algorithm is competitive to the state-of-the-art results presented in the literature.
14.08.2022
279 - 293
20
140