EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem |
| |
Authors: | Guido Perboli Ferdinando Pezzella Roberto Tadei |
| |
Institution: | (1) Dipartimento di Automatica ed Informatica, Politecnico di Torino, C.so Duca degli Abruzzi 24, 10129 Torino (TO), Italy;(2) Dipartimento di Ingegneria Informatica, Gestionale e dell’Automazione, Università Politecnica delle Marche, Via Brecce Bianche 12, 60131 Ancona (AN), Italy |
| |
Abstract: | This paper presents EVE-OPT, a Hybrid Algorithm based on Genetic Algorithms and Taboo Search for solving the Capacitated Vehicle
Routing Problem. Several hybrid algorithms have been proposed in recent years for solving this problem. Despite good results,
they usually make use of highly problem-dependent neighbourhoods and complex genetic operators. This makes their application
to real instances difficult, as a number of additional constraints need to be considered. The algorithm described here hybridizes
two very simple heuristics and introduces a new genetic operator, the Chain Mutation, as well as a new mutation scheme. We
also apply a procedure, the k-chain-moves, able to increase the neighbourhood size, thereby improving the quality of the solution with negligible computational
effort. Despite its simplicity, EVE-OPT is able to achieve the same results as very complex state-of-the art algorithms. |
| |
Keywords: | Vehicle routing Hybrid algorithm Genetic algorithm Taboo search |
本文献已被 SpringerLink 等数据库收录! |
|