带容量约束车辆路径问题的一个新遗传算法

A New Genetic Algorithm for the Capacity Constraints Vehicle Routing Problem

摘要: 本文研究了一个配送中心多个客户的带容量限制的车辆路径问题，该问题以总距离最短为目标。针对该问题，提出了一个带局部搜索程序的遗传算法。首先，设计了一个基于父代个体求和的杂交算子，该算子的特点是能在父代个体相同的情况下产生不同的后代个体，保持种群的多样性；其次，为了有效改进遗传算法产生的后代个体，引入了一个基于概率选择的局部搜索程序。数值实验表明该算法是有效的。

Abstract: In this paper, a capacitated vehicle routing problem is studied, in which a distribution center and multiple customers are involved, and the optimization objective is to minimize the distance. For this kind of problem, a genetic algorithm based on a local search scheme is proposed. First, a crossover operator is investigated by the sum of parents. The crossover operator is different from most of traditional crossover procedures in that it can generate new offspring when parents are same, thus maintaining the diversity of population. In addition, in order to efficiently improve the offspring individuals in the iteration process, a local search scheme based on probability selection is presented. The simulation results show that the proposed algorithm is efficient.