swMATH ID: 2695
Software Authors: Perboli, Guido; Pezzella, Ferdinando; Tadei, Roberto
Description: EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem. 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.
Homepage: http://link.springer.com/article/10.1007%2Fs00186-008-0236-7
Keywords: vehicle routing; hybrid algorithm; genetic algorithm; taboo search
Related Software: VRP; OR-Library; Scatter Search; Bison; DIMACS; SSPMO; SPOT; Tabu search; METSlib; CVRPSP; BoneRoute
Referenced in: 5 Publications

Referencing Publications by Year