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.
Keywords for this software
References in zbMATH (referenced in 5 articles , 1 standard article )
Showing results 1 to 5 of 5.
- Drexl, Michael; Schneider, Michael: A survey of variants and extensions of the location-routing problem (2015)
- Quiroz-Castellanos, Marcela; Cruz-Reyes, Laura; Torres-Jimenez, Jose; Gómez S., Claudia; Huacuja, Héctor J. Fraire; Alvim, Adriana C. F.: A grouping genetic algorithm with controlled gene transmission for the bin packing problem (2015)
- Santos, Fernando Afonso; Da Cunha, Alexandre Salles; Mateus, Geraldo Robson: Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem (2013)
- Vidal, Thibaut; Crainic, Teodor Gabriel; Gendreau, Michel; Prins, Christian: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis (2013)
- Perboli, Guido; Pezzella, Ferdinando; Tadei, Roberto: EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem (2008)