Abstract: Aiming at the characters of vehicle routing problem,the chemical reaction optimization was proposed to handle the Capacitated Vehicle Routing Problem (CVRP).The molecules of CRO were constructed which included integer coding of customer points,and the molecules'chemical reaction such as on-wall collision,decomposition and exchange were designed by means of crossing and variation of Genetic Algorithm (GA).In view of the local optimization,the synthetic reaction of molecules was designed to obtain the improvement of solution.The values of parameter α and β were controlled by dynamic change,which could balance the relationship between local search and global search.Through the experimental simulation,the results showed that the deviation ratio of the optimal solution obtained by CRO were less than 5% compared with the standard library,and the CRO algorithm had the advantage in the computation time by comparing with other LNS algorithms.

Key words: vehicle routing problem, chemical reaction optimization, logistic distribution, routing optimization

摘要： 针对车辆路径问题的特点,提出应用化学优化算法解决带容量限制的车辆路径问题。首先构建包括顾客与配送中心的整数序列分子,然后借鉴遗传算法的交叉、变异方法设计分子的撞墙、分解、碰撞反应,采用局部优化方法设计其合成反应,通过上述4种反应改变分子结构获得解的改善;提出采用动态变化方法控制关键参数α,β的取值来提高求解效率,平衡局部搜索与全局搜索的关系。通过实验仿真,将求解结果与BKS标准库进行对比,结果显示所提算法在多个案例中获得的最优解与标准库最优解的误差比例不超过5%,与大规模邻域搜索算法比较表明,该算法在运算时间上具有一定优势,是解决该问题的一种有效算法。

关键词: 车辆路径问题, 化学反应优化算法, 物流配送, 路径优化