黄 震，罗中良，黄时慰

(惠州学院 计算机科学系，广东惠州，516007)



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

黄 震，罗中良，黄时慰

(惠州学院 计算机科学系，广东惠州，516007)

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

蚁群算法；遗传算法；车辆路径问题；时间窗

车辆路径问题(Vehicle Routing Problem,VRP)是一类经典的组合优化问题。一般指对一系列的客户点组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、车辆容量限制等)下，达到一定的目标(如距离最短、费用最少等)，带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)是在VRP的基础上要求在配送过程中按照客户要求在一定的时间窗内到达客户点，即在不违背车辆容量限制、时间限制等约束条件的前提下，合理制定运输时的车辆配送路径方案，以尽可能小的成本满足处在不同地理位置的客户对货物运送和服务时间的要求[1]。由于VRPTW带有服务时间的访问限制，VRPTW比VRP更贴近实际应用，广泛地应用于交通和物流领域，由于VRPTW是NP难问题，主要都是使用启发式算法[2-3]来求解，已有不少学者对该问题进行了相关的研究[4-11]。……