摘要
针对标准遗传算法在求解车辆路径问题中出现的早熟、收敛,易陷入局部极值点的问题,提出双种群遗传算法求解车辆路径问题的方法。在求解过程中,初始化两个种群,分别选择不同的交叉、变异概率,在一次迭代完成后,交换种群间的优秀个体所携带的遗传信息,以打破种群内的平衡态,跳出局部最优解。通过实验仿真,将双种群遗传算法与其他各种启发式算法进行比较,双种群遗传算法比标准遗传算法显著提高了全局收敛性能,是解决车辆路径问题的有效方法。
The standard Genetic Algorithm has been applied into Vehicle Routing Problem, and it has the common defects of early convergence and easily falling into local minimization. According to it, the double populations genetic algorithm is applied into Vehicle Routing Problems. During the course of optimization, two populations is initialization, each has its probability of crossover and mutation. After every iteration, the two populations exchange the better chromosome. It can break the balance of inter-population in the local minimization and escape the local minimization. According to computational experiment result, the double populations algorithm find the optimal or nearly optimal solution effectively in comparison with other meta-heuristic algorithms. So, it is an efficient method for Vehicle Routing Problem.
基金
国家863/CIMS主题资助项目(2002AA412610)
浙江省重大科技攻关项目(2003C11033)
浙江省科技计划项目(2004C33084)。~~
关键词
车辆路径问题
双种群遗传算法
计算智能
物流
vehicle routing problem
genetic algorithm
computation intelligence
logistics
