基于强基因模式组织算法的VRPTW研究

提出一种强基因模式组织算法,给出了强基因模式、连续模式以及对称模式的定义,使用节约法提取强基因模式.设计了选择、变异和模式重组算子,同时建立了以运输成本为目标、具有时间窗等约束的车辆路径问题模型.将该算法与改进的遗传算法、改进的差分进化算法和节约法对模型进行仿真实验.结果表明,强基因模式的应用及模式重组算子大大缩小了解的搜索空间,提高了算法的收敛速度和解的精度,其性能优于其他3种算法.

Research on vehicle routing problem with time window based on strong gene schema combination algorithm

A method named strong gene schema combination algorithm(GSCA) is proposed based on evolutionary
algorithm, which gives the definitions of strong gene schema, continuous schema and symmetrical schema. Then the strong
gene schemas are extracted by using saving algorithm. Operators of selection, mutation and schema recombination are
designed. At the same time, the mathematical model of vehicle routing problem is established with the goal of transportation
cost and the restraints of customer requirements, truckload ability and time window(VRPTW). The effect of GSCA compared
with improved genetic algorithm(IGA), improved differential evolution algorithm(IDEA) and saving algorithm(SA) for
capturing the global optimum is tested on the VRPTW model in Matlab. The results show that the application of strong
gene schema and the operator of schema recombination reduce the number of searches greatly within the solution space and
enhance the convergence capability and the precision of the solution, and its performance is demonstrated better than the
compared three algorithms.