Metaheuristics Hybridizing Various Components
Résumé
Research in metaheuristics for combinatorial optimization problems, and thus for vehicle routing problems (VRP), significantly shifts toward a trend of hybridization. This chapter illustrates the main approaches that can be used to design hybrid metaheuristics either by combining only heuristics methods or by associating exact and heuristic paradigms. Hybridization design can be based on enrichment of a given metaheuristic by adding restart procedures, with a population generation, probabilistic acceptance of deteriorating moves, variable neighborhood structures or long-term memories and penalty functions. Many hybrids were also designed by combining greedy randomized adaptive search procedure (GRASP) with evolutionary local search (ELS) or iterated local search (ILS) to solve extensions of the capacitated VRP (CVRP). The chapter also presents an effective hybrid metaheuristic proposed by Repoussis to solve the open VRP (OVRP). The OVRP consists of designing least cost routes from a depot to a set of customers.