人工蜂群算法在单时间窗车辆路径问题中的应用

作者：于晓东 廉莲

来源：《科技创新与应用》2016年第19期

        摘 要：单时间窗车辆路径问题（VRPTW）是运筹学领域的经典问题，在实践中有着广泛的应用。文章中我们使用人工蜂群算法（ABC）来求解该问题。针对VRPTW的特点，我们用3种局部搜索算法对解进行优化。用solomon标准测试集对算法进行检验，该算法的结果表明在求解此问题时表现较好。

        关键词：人工蜂群算法；车辆路径问题；局部搜索

        引言

        Solomon[1]在1986年最早对VRPTW进行启发式算法研究。吴勇[2]提出多群粒子群算法来求解VRPTW，除了每个粒子群初始解生成不同外，还在每个粒子群中加入记忆功能加速收敛。葛金辉[3]对禁忌搜索算法进行了改进，首先随机构造多个初始解，从中选取最好的作为算法初始解，并构造了随搜索过程发生改变动态禁忌表，提高优化能力。何小锋[4]针对蚁群算法易陷入局部最优和收敛速度慢的问题，结合量子计算提出一种粒子蚁群算法，提高了算法的全局搜索能力。杨进[5]用ABC算法对该问题进行了研究。

        1 单时间窗车辆路径问题定义

        VRPTW的每一个客户都有一个与之对应的时间段[ai，li]，称之为时间窗。车辆离开配送中心的时间，车辆在边（i，j）的行驶时间tij，每个顾客需要的服务时间si均已知。每个客户的服务开始时间必须位于其时间窗内，当服务开始后车辆必须在客户i处停留si，需要注意的是当车辆在ai前到达客户i，需要等待直到服务开始。

        VRPTW的目标是找到具有最小成本的K条线路，总结如下：每条线路开始并结束于配送中心；每一个客户只能被一辆车服务一次；由一辆车服务的所有客户的总需求不能超过车辆的容量限制C；以及对于每一个客户i，在时间段[ai，li]内开始服务，且服务时间为si。

人工蜂群算法在单时间窗车辆路径问题中的应用