改进遗传算法求解有时间窗车辆路由问题

为了有效求解带有时间窗的车辆路由问题,在标准遗传算法的基础上,引入两代竞争近距淘汰选择算子,用欧氏距离来判断个体之间的距离作为个体的相似程度,相似程度高且适应度差的个体被淘汰,并辅以循环交叉算子和插入变异算子,构造出了一种改进的遗传算法.仿真实验表明,改进的算法在迭代过程中能有效保持群体的多样性,避免出现早熟现象而陷入局部极值点,提高遗传算法的内在并行性.同时通过竞争淘汰,使局部搜索能力得到加强,加快了搜索速度.改进算法所计算出的结果优于用轮盘赌和自适应选择作为选择算子的遗传算法的结果.

Solution to vehicle routing problem with time window based on modified genetic algorithm

To solve the vehicle routing problem with time window,a new modified genetic algorithm was proposed. In the proposed algorithm, the selection operator was developed by way of between competition two generations to get rid of the individuals of higher similarity degree and worse fitness. The Euclidean distance between individuals was calculated to evaluate the similarity degree of individuals. In one group of individuals, the one with higher degree of similarity and low fitness value was eliminated, and in the same time the cycle crossover and insertion mutation were involved. The simulation results show that the proposed algorithm can keep the diversity of population and avoid the prematurity and thus is an effective algorithm. On top of it, the local search ability was improved. The new algorithm can enhance constringency ability, with better result than that of genetic algorithm with roulette selection operator or self-adaptive selection.