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

人工蜂群算法在单时间窗车辆路径问题中的应用摘要：单时间窗车辆路径问题（VRPTW）是运筹学领域的经典问题在实践中有着广泛的应用。文章中我们使用人工蜂群算法（ABC）来求解该问题。针对VRPTW的特点我们用3种局部搜索算法对解进行优化。用solomon标准测试集对算法进行检验该算法的结果表明在求解此问题时表现较好。关键词：人工蜂群算法；车辆路径问题；局部搜索引言Solomon[1]在1986年最早对VRPTW进行启发式算法研究。吴勇[2]提出多群粒子群算法来求解VRPTW除了每个粒子群初始解生成不同外还在每个粒子群中加入记忆功能加速收敛。葛金辉[3]对禁忌搜索算法进行了改进首先随机构造多个初始解从中选取最好的作为算法初始解并构造了随搜索过程发生改变动态禁忌表提高优化能力。何小锋[4]针对蚁群算法易陷入局部最优和收敛速度慢的问题结合量子计算提出一种粒子蚁群算法提高了算法的全局搜索能力。杨进[5]用ABC算法对该问题进行了研究。1单时间窗车辆路径问题定义VRPTW的每一个客户都有一个与之对应的时间段[aili]称之为时间窗。车辆离开配送中心的时间车辆在边（ij）的行驶时间tij每个顾客需要的服务时间si均已知。每个客户的服务开始时间必须位于其时间窗内当服务开始后车辆必须在客户i处停留si需要注意的是当车辆在ai前到达客户i需要等待直到服务开始。VRPTW的目标是找到具有最小成本的K条线路总结如下：每条线路开始并结束于配送中心；每一个客户只能被一辆车服务一次；由一辆车服务的所有客户的总需求不能超过车辆的容量限制C；以及对于每一个客户i在时间段[aili]内开始服务且服务时间为si。2人工蜂群算法的基本原理在ABC[6]算法中人工蜜蜂种群包括3类蜜蜂：雇佣蜂、跟随蜂以及侦查蜂。跟随蜂是指在跳舞区等待食物源信息并选择食物源的蜜蜂雇佣蜂是指自己出去寻找食物源并将食物源的信息通过在跳舞区域跳舞传递给跟随蜂的蜜蜂侦查蜂是在某种条件下随机的寻找食物源。在ABC算法中雇佣蜂和跟随蜂各占种群数量的1/2每一个食物源都对应着一个雇佣蜂。当一个食物源被雇佣蜂以及跟随蜂放弃后这个食物源对应的雇佣蜂就变为侦查蜂。3人工蜂群算法在VRPTW中的简单应用3.1初始解生成文章初始解生成采用Solomon提出的插入启发式算法[7]这是一种连续构造线路的启发式方法与并行相对应。该算法是基于时间和距离两种因素每条路径首先选择一个种子客户然后选择没有分配路径的客户添加到该线路直到这条路径达到约束限制如果还存在没有分配路径线路的客户那么重复上述插入过程直到所有的客户都分配路径。3.2邻域搜索我们在ABC算法中的邻域搜索中采用3种局部搜索组合的方式其顺序为：2_opt*：任选两条路径均一分为二互换首尾重新组合；重新插入（内）：这种方法是随机选择一个客户将其插入到新的位置新的位置可以与原来的位置处于同一路径但不能与原位置重复；重新插入（外）：这种方法是随机选择一个客户将其插入到新的位置新的位置与原位置位于不同路径。3.3侦查蜂在侦查蜂阶段每次迭代只允许一个侦查蜂替换一个解但不是完全随机的产生一个新解而是在原来解的基础上进行一次搜索不论得到的新解适应度好坏都替换掉原解。（1）选中要抛弃的解F计算F中所有客户的等待时间w并进行排序选择等待时间最长的ns个客户。（2）这里要用到每个客户的邻域概念：对于客户i计算其与每一个客户的相似程度用Ne来表示Ne（i）=0.5*|li-lj|+0.5*dij然后根据nl确定与客户i相似度最高的nl个客户（Ne越小相似度越高）。（3）将第一步中选中的ns个客户并结合第二步确定这ns个客户的邻域集合S因为不同客户的邻域可能出现重叠因此集合S的最大长度为ns+ns*nl将集合S中的客户从F中移除得到F'等待重新插入。（4）用并行插入启发式算法[8]将集合S中的客户重新插入到F'中。替换掉F更新适应度值。3.4实验为了验证算法有效性我们选取了最常使用的Solomon标准测试集。在这里我们选取C1类数据共8组数据测试算法。我们采用Matlab进行编程参数设置如下：ns=10nl=6limit=50种群规模NP=10程序迭代次数为1000运行10次。从人工蜂群算法得到的结果看共有6组数据得到了最优值分别为C101C104-109成功率为66.7%。其中C101C105-1074组数据的平均值也达到了最优解表明在求解这几组数据时算法的稳定性较好从平均值来看不管是最优值误差还是平均值误差均在1%以内证