一种带时间窗车辆路径问题的混合蚁群算法

针对带时间窗车辆路径问题求解时蚁群算法存在容易陷入局部最优,而遗传算法初始种群的优劣对算法有效性存在直接影响,提出一种混合蚁群优化算法。算法首先在蚁群算法的节点选择概率公式中引入时间窗因素,以得到初始种群,然后通过遗传算法的交叉算子和变异算子对初始种群中的较优路径进行交叉和变异操作,从而得到更优的路径。通过Matlab环境下对文中混合算法进行仿真实验,在车辆利用率和路径规划上效果明显,表明了算法的高效性,同时混合算法可以避免陷入局部最优。

Application Research of Hybrid ant Colony Algorithm in Vehicle Routing Problem with Time Windows

A hybrid ant colony algorithm was proposed.Because, ant colony algorithm used to solve the vehicle routing problem with time windows (VRPTW) is easy to fall into local optimum, and the quality of initial population in genetic algorithm affects the effectiveness of the algorithm directly. Firstly, the algorithm introduces the factors of time windows into node selection probability formula of ant colony algorithm to get the initial population. Secondly， the crossover and the mutation were operated to get a better path for the initial population. Applying Matlab environment for hybrid algorithm simulation, the effects on the vehicle utilization and path planning is obvious. It shows the algorithm is efficient, and can avoid falling into local optimum.