A hybrid evolution strategy for the open vehicle routing problem

作者：Repoussis P P^*; Tarantilis C D; Braysy O; Ioannou G

来源：Computers & Operations Research, 2010, 37(3): 443-455.

DOI：10.1016/j.cor.2008.11.003

• Evolution strategies
• Guided local search
• Tabu search
• Open vehicle routing

This paper presents a hybrid evolution strategy (ES) for solving the open vehicle routing problem (OVRP), which is a well-known combinatorial optimization problem that addresses the service of a set of customers using a homogeneous fleet of non-depot returning capacitated vehicles. The objective is to minimize the fleet size and the distance traveled. The proposed solution method manipulates a population of mu individuals using a (mu + lambda)-ES; at each generation, a new intermediate population of lambda offspring is produced via mutation, using arcs extracted from parent individuals. The selection and combination of arcs is dictated by a vector of strategy parameters. A multi-parent recombination operator enables the self-adaptation of the mutation rates based on the frequency of appearance of each arc and the diversity of the population. Finally, each new offspring is further improved via a memory-based trajectory local search algorithm, while an elitist scheme guides the selection of survivors. Experimental results on well-known benchmark data sets demonstrate the competitiveness of the proposed population-based hybrid metaheuristic algorithm.

• 出版日期2010-3