2008年6月系统工程理论与实践第6期 文章编号:100026788(2008)0620081213开放式车辆路径问题的蚁群优化算法李相勇,田 澎(上海交通大学安泰经济与管理学院,上海200052)摘要: 研究了开放式车辆路径问题,该问题中车辆在服务完最后一个顾客点后不需要回到车场,若要求回到车场,则必须沿原路返回.提出了一种混合蚁群优化算法,该算法主体是一个在超立方框架下执行的M AX2MI N蚂蚁系统,算法混合了禁忌搜索算法作为局部优化算法,同时算法集成了一个后优化过程来进一步优化最优解.基于标准测试问题,最后给出了算法同文献中其它算法的性能比较结果,计算结果表明本文提出的算法是一个有效的求解开放式车辆路径问题的方法.关键词: 开放式车辆路径问题;蚁群优化算法;禁忌搜索算法;现代启发式算法;后优化过程中图分类号: O221 文献标志码: A Research on ant colony optimization alg orithm for theopen vehicle routing problemLI X iang2y ong,TI AN Peng(Antai C ollege of Economics&Management,Shanghai Jiaotong University,Shanghai200030,China)Abstract: This paper studies the open vehicle routing problem,in which the vehicles do not return to the startingdepot after serving the last customers or,if they do,they must make the same trip in the reverse order.We propose anAnt C olony Optimization metaheuristic hybridized with tabu search alg orithm for the open vehicle routing problems.Theproposed alg orithm is a M AX2MI N Ant System hybridized with tabu search,which is im plemented in the hyper2cubeframew ork.Additionally,a post-optimization procedure is incorporated in the proposed alg orithm to further im provethe best-found s olutions.The com putational results of the proposed alg orithm com pared to those of other alg orithmsare reported.The com putation results experimentally indicate that the proposed alg orithm is an efficient method fors olving the open vehicle routing problems.K ey w ords: open vehicle routing problem;ant colony optimization;tabu search;metaheuristic;post2optimizationprocedure1 引言开放式车辆路径问题(Open Vehicle R outing Problem,OVRP)是经典车辆路径问题(Vehicle R outing Problem,VRP)的拓展问题.OVRP和VRP最显著的区别在于:VRP中车辆路线是一个哈密尔顿巡回(Hamiltonian tour),而OVRP中,则是一个哈密尔顿路径(Hamiltonian path).这主要是由于在OVRP中,车辆在服务完最后一个顾客点后,不要求其回到出发车场,若需要回到车场,则必须沿原路返回.OVRP是配送管理中广泛存在的问题,它可以用来对很多实际应用问题来进行建模.比如一个没有自有车队的配送公司,为了完成对顾客的配送任务而将其业务分包给其它雇佣的车辆,上述问题即为一个OVRP,该问题中配送公司并不关心车辆是否回到车场(配送公司),其也不支付车辆从最后一个服务顾客点到配送公司之间的旅行费用.OVRP在现实中有很多应用,特别是在具有外包业务特点的经济活动中具有重要的应用价值,比如报纸配送、牛奶配送、校园班车问题等,在这类问题中,企业没有自己的自有车辆,而是将其配送业务外包给其它的车辆或车队,这些企业并不需要车辆在服务完顾客后回到车场点,因此如何合理的安排车收稿日期:2007201217作者简介:李相勇(1978-),男,江苏建湖人,上海交通大学安泰经济与管理学院博士研究生,研究方向:应用运筹学、智能优化算法分析与设计.28系统工程理论与实践2008年6月辆路线对于企业提高运营效率、改善顾客服务质量具有重要的价值.尽管文献中对于经典VRP进行了大量富有成效的研究工作,但是关于OVRP算法研究较少.对于OVRP,最早的文献要追溯到1981年Schrage的文章[1].从1981年开始的20多年,OVRP很少引起学者们的注意,也没有关于OVRP求解算法的论文发表.从2000年起部分学者开始研究OVRP的求解算法,并提出了如下一些算法.Sariklis和P owell[2]提出了一个求解OVRP的两阶段启发式算法,即先分组后安排路线.第一阶段分组阶段又分为两个步骤:在考虑车辆装载能力约束,顾客点首先被进行分组,然后在已经形成的分组间重新分配顾客,从而优化分组,即优化车辆路径距离.算法的第二阶段,通过求解一个最小生成树问题来将分组转化为OVRP的车辆路线.～o[3]提出了一个求解OVRP的禁忌搜索算法(T abu Search,TS).作者通过两种方法来产生初始解: Branda一个是用最近邻居法产生;一个是用K度方法(K表示车辆数的下界).在开始禁忌搜索算法之前,作者首先用两种方法来优化车辆路线距离:最近邻居法(Nearest Neighbor method)和改进的US过程(The unstringing and stringing procedure)[4].TS算法中使用了两种邻域结构:插入算子(Insert)和交换算子(S wap)来产生邻居解.在Fu等[5]、符卓[6]提出的求解OVRP的禁忌算法中,作者用两种方法来产生初始解,随机的方法和最远者优先启发式算法FFH(farthest first heuristic).FFH的基本思想是:一条新线路从离车场最远且尚未指派给任何线路的顾客点i开始.沿着从点i到车场的最短路,依次将客户分配给这条新线路(这辆车),直到车辆足够满为止;若车辆未达到足够满,则舍弃这条线路而转为尝试其次短路.重复这个过程直到一条线路被接受.算法定义了四种邻域结构:顶点重新指派、顶点交换、22opt以及“尾巴”交换.所谓顶点重新指派是指将所挑选的第一个顶点从线路上当前的位置中取出,并将其插入到所挑选的第二个顶点的位置之前.顶点交换将所挑选的两个顶点的位置互换.若所挑选的两个顶点在同一线路内,则象在TSP中标准的22 Opt一样,将所挑选的两个顶点间的所有顶点的排列顺序逆转.“尾巴”交换.若所挑选的两个顶点位于不同的线路上,则将所挑选的两个顶点后面的“尾巴”(从被选顶点至线路终点,两个顶点都必须是客户点)互换.T arantilis等[7]提出了一个求解OVRP的决策支持系统,该系统集成了地理信息系统和一个启发式算法BoneR oute[8].BoneR oute算法是一个类似于自适应记忆的算法,算法从一个解集中提取节点序列(文章中将其称为Bone),然后利用自适应记忆的方法来构造车辆路线.算法分为两个阶段:第一个阶段:P ool产生阶段(pool generation phase).该阶段首先利用加权节约算法(the weighted savings)[9]来产生一系列的初始解,然后用标准的禁忌搜索算法来改进这些解.算法第二个阶段:P ool利用阶段(P ool exploitation phase).算法从自适应记忆中选择好的节点序列来构造车辆路线,然后同样利用一个标准的禁忌搜索算法来改进这些解,最后用好的解来更新自适应记忆.作为BoneR oute局部优化算法的禁忌算法,其使用的邻域结构为:22Opt、121交换、120交换.121交换是指交换路线中的两个顾客点,这两个顾客点可以同属于一个路线或者两个不同的路线.120是指将一个顾客重新定位到另一个合适的位置(所在路线的其它位置、或者其它路线),具体内容请读者参阅文献[7].文献[10,11]提出了基于阈值接收算法(threshold accepting,T A)的启发式算法.T A算法是模拟退火算法的确定性变型算法,它同标准的模拟退火算法的不同在于:模拟退火算法以一定的概率来接受较差的解,而T A中则是通过设定一个阈值T(表示目标函数允许的增加值的上界),通过阈值来决定是否接受一个解.文献[11]提出的基于列表的T A算法(alist based threshold accepting,LBT A)则使用了一个阈值的列表,算法迭代每次则从阈值表中选择最大的元素作为阈值,算法迭代过程阈值列表不断更新.同文献[7]一样,算法也使用了局部搜索算子22Opt、121交换、120交换.OVRP的子问题是:为分配给车辆的每一组顾客点寻找最佳的哈密尔顿路径,其已经被证明为NP2hard 问题[12].因为OVRP可以转化为等价的哈密尔顿循环,所以整个OVRP也为一个NP2hard问题[3].鉴于OVRP固有的计算复杂性,在中等计算时间(m oderate com putation cost)内寻找问题的最优解变得不现实,一个比较合理的选择是采用启发式算法或者现代启发式算法来较快地产生好的解(尽管不是最优解).作为一个成功的现代启发式算法,蚁群优化算法(Ant C olony Optimization ,AC O )最早是由D orig o 等提出,AC O 是目前许多广泛应用的蚂蚁算法(Ant Alg orithm )及其变形算法的一般框架[13].自提出以来,AC O 以其作为求解组合优化问题的替代算法的巨大潜力,引起了广泛的关注,其已经被成功地用来求解了许多经典的组合优化问题的算法,比如旅行商问题、序列排序问题(sequential ordering problem )、二次指派问题(quadratic assignment problem )、Job 2shop 问题等,更详细的关于AC O 应用方面的综述,读者可以参考D orgio 和St ützle 出版的专著《Ant C olony Optimization 》[13].本文应用AC O 算法来求解OVRP ,并提出了一个集成了AC O 、禁忌搜索算法以及一个后优化过程(post optimization )的混合算法.本文的组织结构如下:第二部分详细给出了本文所提出的混合蚁群优化算法.第三部分给出算法的计算结果,同时比较了算法和文献中其它9种算法的求解质量.第四部分总结了全文并给出了一些将来的研究方向.2 求解OVRP 的蚁群优化算法211 问题定义OVRP 是经典VRP 的一个重要的松弛问题,从图论的角度,OVRP 可以表示为一个完全的赋权图,G =(V ,E ),这里V ={0,1,2,…,n }为节点集,E ={(i ,j )|i ,j ∈V ,i ≠j }为边集.0表示车场点,C ={1,2,…,n }表示顾客点集,n 为车辆服务的顾客点数目.每一条边赋有一个旅行距离d ij 或旅行费用c ij .每一个顾客点i ,有一个固定需求q i 和服务时间δi .所有车辆具有相同的最大装载能力Q 和最大允许旅行距离L (L 包括了车辆旅行距离以及对应的服务顾客点的服务时间).OVRP 问题中,每个车辆从车场出发对一组顾客点进行服务,其车辆路线开始于车场点终止于最后一个服务的顾客点,OVRP 的目标是确定一组具有最小车辆数以及最小旅行距离的哈密尔顿路径,这些车辆路线满足以下约束条件:1)车辆路线始于车场点,车辆服务完最后一个顾客点后无需回到车场点,若需要,则须沿原路返回;2)顾客点需求必须且只能由一辆车来服务完成;3)每一条车辆路线上客户点的需求量之和不超过车辆装载能力Q ;4)每一条车辆路线总的旅行距离与对应的顾客点的服务时间之和不超过车辆最大允许旅行距离L .文献中,学者们通常考虑一个层次目标函数(hierachical objectives ),即最小化车辆数作为首要优化目标,然后对应于给定的最小车辆数,最小化其车辆旅行距离,也就是说一个具有最小车辆数和较大车辆旅行距离的OVRP 解比一个具有较小车辆旅行距离和较大车辆数的OVRP 解好.在本文接下来的部分中,对于每一个蚂蚁发现的最优解通过下式最小化函数来进行适应度评价:f =M ・v +D ,f 为解所对应的总的旅行费用;v 为每个解所对应的车辆数;D 为车辆的旅行距离;M 为一个充分大的数,比如100000.通过引入参数M ,算法AC O 2OVRP 可以保证车辆数作为第一优化目标函数,在本文考虑的测试问题中,顾客点之间的旅行时间等于顾客点之间的旅行距离,顾客点服务时间和顾客点间的距离具有相同的量纲.212 蚁群优化算法概述蚁群优化算法AC O 是由D orig o 和其同事提出的受自然启发的(nature 2inspired )和基于群体(population 2bsed )的现代启发式算法[13].AC O 算法是一种受蚂蚁觅食行为启发而产生的计算范型(coputation paradigm ).自然界中,蚂蚁初始随机地搜索洞穴周围来寻找食物.当蚂蚁发现了食物回到洞穴时,会在路径上释放化学物质———信息素(pherom one ),信息素的数量依赖于所发现食物的数量和质量.在蚂蚁觅食过程中,蚂蚁在路径上释放的信息素作为蚂蚁通信和协调的媒介引导其它蚂蚁来寻找食物,那些具有较大信息浓度的路径将以较大的概率被蚂蚁在后续觅食过程中所选择.基于信息素的间接通信使蚂蚁能够发现洞穴和食物间的最短路径.生物蚁群基于信息素的简单的信息通信和正反馈,导致了复杂的群体智能(发现洞穴到食物间的最短路径)的涌现,是蚁群优化算法求解复杂组合优化问题的基础.AC O 算法的主要部分是一个由信息素迹(pherom one trail )所标定的参数概率模型,信息素模型(pherom one m odel ).在AC O 现代启发式算法中,人工蚂蚁基于信息素模型,随机地将解的组分(比如TSP 和OVRP 中为边(i ,j ))随机地添加到局部解(partial s olution )中,迭代构造求解问题的解.每个解的组分被赋有一个信息素值(pherom one value ),在算法迭代中,38第6期开放式车辆路径问题的蚁群优化算法利用蚂蚁所发现的较高质量的解来更新信息素,信息素更新的目的是使算法搜索集中于搜索空间中包含有较高质量解的区域[13].作为各种蚂蚁算法(ant alg orithm)的一般框架,AC O算法包括许多蚂蚁算法及其变形算法,比如蚂蚁系统(Ant System,AS)算法、精英蚂蚁系统(E litist Ant System,E AS)算法、等级蚂蚁系统(Rand2based Ant System,RAS)算法、蚁群系统(Ant C olony System,ACS)算法以及MAX2MI N蚂蚁系统(MAX2 MI N Ant System,M MAS)算法等.这些蚂蚁算法之间的主要区别在于:信息素的更新规则,对于详细的蚂蚁算法特征描述,感兴趣的读者可以参阅文献[13].213 求解OVRP的蚁群优化算法本文所提出的求解OVRP的AC O现代启发式算法,是一个集成了禁忌搜索算法和后优化过程的M MAS算法,且在超立方框架中执行M MAS.下文中我们简记所提出的算法为AC O2OVRP.作为对基本蚂蚁系统算法AS的改进,M MAS算法是由Stützle于1999年提出的[14],其与AS相比,通过对信息素值设置上界τmax和下界τmin来防止AS算法较早的陷入局部最优解.超立方框架(Hyper2CubeFramew ork,HCF)则是由Christian Blum提出的AC O算法的执行框架[15,16].HCF通过引入新的信息素更新规则(具体见下文)将信息素的值限制在区间[0,1]中,如文献[15]所指出的那样,在HCF中,执行AC O算法具有理论和实践价值. HCF中,对OVRP目标函数的自动标定(automatic scaling)能够降低问题维度和规模对算法参数选择和性能的影响,从而大大地提高了算法AC O2OVRP的鲁棒性.图1给出了算法AC O2OVRP的策略框架,图中使用的符号有:t:算法迭代计数器;E litist-num:使用局部搜索算法的蚂蚁数;num-iter:用来控制使用局部搜索算法的蚂蚁数目的参数;s i:蚂蚁i构造的解;s ib:算法AC O2OVRP当前代所有蚂蚁中发现的最好解;s rb:算法AC O2OVRP自重启以来所发现的最好解;s bs:算法AC O2OVRP自启动以来所发现的最好解;NU LL:表示解为空;f:OVRP的目标函数;m od:取模函数.Π3S tep1.初始化3Π初始化信息素矩阵参数设置S tep2.当算法满足终止条件时,转到Step3.否则重复执行下列过程:Π3S tep2.1确定使用局部搜索算子的蚂蚁数3Π 若m od(t,num-iter)=0且num-iter<10,则,Elitist-num=Elitist-num+1Π3S tep2.2解构造过程3Π for i=1to m 根据式(1)和(2)蚂蚁i构造解s iΠ3S tep2.3局部搜索过程3Π 确定算法当前代E litist-num个精英蚂蚁 for i=1to Elitist-num 对Elitist-num个精英蚂蚁发现的最优解使用禁忌搜索算法,进一步优化解Π3S tep2.4更新参数s ib,s rb和s b s的值3Π s ib=arg min(f(s1),f(s2),…,f(s m)) 若s rb=NU LL或f(s rb)>f(s ib),则,s rb=s ib 若s b s=NU LL或f(s b s)>f(s ib),则,s bs=s ibΠ3S tep2.5信息素更新过程3Π 根据式(3)～(6)更新信息素矩阵Π3S tep2.6收敛因子计算过程3Π 根据式(7)计算收敛因子c f的值Π3S tep2.7信息素重新初始化过程3Π 若c f≥0199,则 重置信息素值为015 s rb=NU LLΠ3S tep3.后优化过程3Π执行后优化过程进一步改进最优解S tep4.输出结果图1 算法AC O2OVRP的策略框架48系统工程理论与实践2008年6月算法AC O 2OVRP 工作流程如下.算法每一代,人工蚁群首先利用给定的信息素模型概率地构造OVRP 解,然后算法利用局部搜索算法改进部分精英蚂蚁发现的最优解解.当所有蚂蚁构造完解后,算法选择较好的解来更新信息素矩阵.算法主循环结束后,启动一个后优化过程来进一步优化算法发现的最优解.最后算法输出计算结果.下面我们详细给出算法AC O 2OVRP 的主要部分.21311 信息素初始化AC O 2OVRP 需要一个初始化的信息素矩阵来开始迭代搜索,即τ={τij },i ,j =1,2,…,n .τij 为边(i ,j )上的信息素,它表示蚂蚁在访问完顾客点i 后直接访问j 的愿望(desirability ).在M MAS 算法的原始文献中[14],为了增强算法在开始阶段的多样化探索(exploration )的能力,St ützle 将信息素值初始化为τmax .同文献[15,16]中一样,算法AC O 2OVP 的信息素都初始化为015.21312 OVRP 解的构造算法AC O 2OVRP 中,最重要的部分是其概率地构造OVRP 解的机理.在解的构造阶段,蚂蚁从节点0(车场)出发,概率地选择节点(OVRP 解的组分)添加到局部解中,直到所有的节点都包含在解中.当蚂蚁k 在顾客点i ,利用下述伪随机概率模型来选择下一个访问的顾客点j [13]:j =arg max l ∈Nki {τil },若q ≤q 0J ,否则(1)J 为基于下式概率分布利用轮盘赌方法选择的顾客点:p ij =τij ∑l ∈Nk iτil ,若j ∈N ki 0,否则(2)式中,N ki 表示所有未访问的可行顾客点j 的集合(可行顾客点插入到局部解中产生的解必须满足车辆能力Q 约束和车辆最大旅行距离L 约束).若N ki 为空集,则蚂蚁k 重新从车场点出发构造车辆路线,直到所有的顾客点都被访问完.q 为区间[0,1]上均匀分布随机数.q 0(0≤q 0≤1)为算法参数,其控制算法在集中搜索(exploitation )(exploration )之间取得平衡.由式(1)和(2)可知,蚂蚁以概率q 0从N ki 中选择具有最大信息值的顾客点j 作为下一个访问的顾客点,相反以概率1-q 0选择式(2)确定的顾客点作为下一个访问的顾客点.换句话说,算法以概率q 0利用信息素标定的学习经验来进行集中搜索,而以概率1-q 0在解空间中进行多样化搜索.21313 局部搜索大量的文献表明:在AC O 算法中,集成局部搜索算法可以提高AC O 算法的性能,获得较高质量的解[13].本节我们也考虑在算法AC O 2OVRP 中引入局部搜索算法来改进解.对于VRP 和OVRP ,禁忌搜索算法TS 已经被证明为高效的局部搜索算法,并且发现了较好的解[17],因此在图1中算法AC O 2OVRP 局部搜索阶段,我们考虑使用禁忌搜索算法.TS 是由G lover 提出的一种迭代局部搜索启发式算法[18],它利用短期或长期记忆使得算法跳出局部最优解.AC O 2OVRP 中,我们使用具有短期记忆的禁忌搜索算法.禁忌搜索算法使用的是一种典型的“侵略性”局部搜索,在算法每一代,算法探索整个搜索空间,寻求当前解x 到其邻域N (x )中最好解x ′的最好的可能移动(即使产生的邻居解x ′可能使目标函数值增加).为了避免算法迂回搜索,算法将刚刚访问的局部最优解的某些属性状态标记为禁忌,其禁忌的周期长度称为禁忌表长度,算法只接受处于非禁忌状态的移动.作为算法AC O 2OVRP 局部搜索算法的禁忌搜索算法包括以下几个重要组成部分:1)初始解:为了开始序列搜索,TS 需要产生一个初始解,初始解的产生方法有:随机产生、最近邻居法、利用其它启发式算法产生等几种方法.本文TS 作为局部搜索算法嵌入在算法AC O 2OVRP 中,因此如图1所示,算法选择的每一个使用局部搜索算法的蚂蚁所发现的最优解作为TS 算法的初始解.2)解的评价:为了增强算法AC O 2OVRP 搜索的多样性和促进在解空间的探索,算法接受任何移动(即使移动产生的解为非可行解).每一个产生的邻居解的评价基于一个新的考虑了两种惩罚项的目标函数.58第6期开放式车辆路径问题的蚁群优化算法这两个惩罚项分别度量产生的邻居解对两种约束的违背程度,即车辆装载能力和车辆最大允许旅行距离限制.算法AC O2OVRP使用了和文献[17]类似的目标函数,并且约束违背的惩罚参数动态调整.3)邻域结构:算法AC O2OVRP中执行禁忌搜索算法时,对当前解随机地使用不同的算子来产生邻居解:类22Opt和22Opt3算子[19]、交换算子(S wap operator)以及重置算子(Relocate operator).这里说的类22Opt 和22Opt3算子是指将原来针对VRP的22Opt和22Opt3算子修改为适应OVRP解特点的算子.交换算子是指交换同一条路线或两条不同路线不同位置的顾客点以寻求对解的改进.重置算子是指某一个顾客从当前位置移出,然后重新插入到解的不同位置(同一条路线的不同位置或者不同路线的不同位置).在TS执行的每一步迭代中,算法随机的选择一个算子作用于当前解以产生邻域解,为了减少算法计算时间,算法采用首次接受(First2accectp,FA)标准,即在发现第一个改进的邻居解后邻域算子停止搜索.4)禁忌对象和禁忌表:为了避免算法迂回搜索,刚刚被选择的解被禁止,置入禁忌表中.通常,对于产生一个邻居解的“改进”(m odification),将其“逆改进”设置为禁忌,并存储在禁忌表中.对于类22Opt3算子、交换算子和重置算子,“改进”定义为产生邻域解而从当前解中删除的边.而“逆改进”则定义为添加的边.对于类22Opt算子,我们定义禁忌对象为节点对,比如(i,j).对于四个不同的邻居算子,算法定义四个不同的禁忌表,相应的存储不同的禁忌对象.同文献[17]一样,这里我们也使用随机禁忌表长度,对于每一个禁忌对象其禁忌长度设置为取值于区间[θ,θ],比如[5,10]的随机整数.5)特赦标准(Aspiration criterion):在禁忌搜索算法中,可能会出现全部候选邻居解均被禁忌,或者存在一个比算法到目前为止发现的最好解更好的禁忌候选解,为了促进算法在解空间的探索,AC O2OVRP采用如下特赦准则将禁忌解解禁:若某个禁忌解优于算法到当前代为止发现的最优可行解,则解禁此候选解并选择其为算法新的当前解.在算法AC O2OVRP中,选择禁忌搜索算法作为局部搜索算法,我们需要考虑如何在解的质量和算法计算时间之间获得较好的平衡.如果在AC O2OVRP每一步迭代后,对所有蚂蚁发现的最优解都使用局部搜索算法,则计算时间将非常大.这里我们采用一种逐步增加使用局部搜索算法的蚂蚁数目的方法[14]:AC O2 OVRP首先只允许当前代最好的蚂蚁使用局部搜索算法,然后算法每隔num-iter次迭代,将使用局部搜索算法的蚂蚁数E litist-num增加1,但是其上限为10.21314 信息素更新在算法每一次迭代中,当所有蚂蚁构造完解,并且使用了局部搜索算法后,算法更新信息素矩阵.那些好解所包含的边上的信息素将得到加强,其基本的思想是:好的解所包含的信息通过信息素的量来标定,以此使得好解所包含的边将会在后续的算法迭代中受到其它蚂蚁的偏爱,即以较大的概率被蚂蚁所选择.这里,我们考虑利用三种不同的解所包含的信息来更新信息素:・s ib:算法当前迭代中所有蚂蚁中发现的最好解;・s rb:算法自重启起来所发现的最好解;・s bs:算法自启动以来所发现的全局最好解.算法AC O2OVRP首先确定边(i,j)上额外释放的信息素量.蚂蚁释放的信息素的量由下式来计算:Δτij=γ1δ(s ib,(i,j))+γ2δ(s rb,(i,j))+γ3δ(s bs,(i,j))(3)式中,γ1,γ2和γ3为三个权重参数,它标定三个不同的解在信息素更新中的相对重要性,三个权重参数满足以下条件:γi≥0(i=1,2,3)且γ1+γ2+γ3=1.函数δ(x,(i,j))定义如下:δ(x,(i,j))=1,若边(i,j)包含在解x中0,否则(4) 算法AC O2OVRP中信息素的更新规则为:τij=G mmas((1-ρ)・τij+ρ・Δτij)(5)G mmas(x)=τmin,if x<τminx,ifτmin≤x≤τmaxτmax,if x>τmax(6)68系统工程理论与实践2008年6月式中,0<ρ≤1为信息素蒸发率.1-ρ则表示边(i ,j )信息素的持久度.在式(5)和(6)所示的更新规则中,每条边(i ,j )上的信息素首先以固定的蒸发率ρ进行蒸发,然后在上述三种解对应包含的边上释放一定量的附加信息素.考虑到OVRP 中车辆路线是一个哈密尔顿路径的特点,每条路线上连接最后一个顾客点和车场点的边上面的信息素不更新,即边(i ,0),i ∈C .式(6)中,函数G m max 使得信息素的取值位于区间[τmin ,τmax ].所有边上信息素的值大于τmax ,其值被强制设为τmax ,所有边上信息素的值小于τmin ,其值被强制设为τmin .在关于M MAS 的原始文献[14]中,信息素值的上界设置为其最大值的渐进估计,即τmax =1(1-ρ)・1f (s opt ),这里f (s opt )表示最优解s opt 的目标函数值.信息素值的下界τmin 则根据上界值τmax 来设置,其值为τmax 的函数,比如τmin =12τmax.由于本文提出的算法AC O 2OVRP 是一个在超立方框架中执行的M MAS 现代启发式算法,因此信息素值的上下界分别为0和1.同文献[15]一样,在实验中我们将其值分别设置为τmax =01999和τmin =01001.如前文所述,我们考虑利用三种不同的解所提供的信息来更新信息素矩阵.s ib,s rb和s bs三者的相对重要性由式(3)中的参数γ1,γ2和γ3来标定,不同的γ1,γ2和γ3组合确定了不同的附加信息素释放值.这里我们考虑一种混合策略来动态确定s ib,s rb和s bs三者的相对重要性程度,如表1所示.表1 γ1,γ2和γ3的设置策略c f <0150150≤c f <01700170≤c f <01850185≤c f <01950195≤c f <01999γ110.70.40.10γ200.30.50.80γ30.00.10.11表1中,根据算法搜索过程中停滞的程度(extent of stagnation ),动态的调整三种不同解的相对重要性程度.这里我们定义指标收敛因子cf 来测度算法AC O 2OVRP 的收敛行为,cf 计算如式(7)所示:cf =2・∑ni =0∑nj =0max (τmax-τij ,τij -τmin )|τ|(τmax -τmin )-1(7)式中,|τ|表示信息素矩阵的大小.cf 表示收敛因子,其取值范围为cf ∈[0,1],其给出了算法搜索停滞状态的一种刻画和度量.当cf 取值接近于1时,算法陷入局部最优.当信息素值初始化为015时,cf =0,算法具有最大的多样化搜索能力.通过一些初步的实验,我们选择表1所示的设置策略.根据收敛因子的不同取值,算法动态的调整三个不同的解对信息更新的贡献程度.在迭代的早期阶段,算法当前代发现的最优解s ib 控制着信息素的更新.相反在算法的后期(接近于收敛),则s gb具有最大的贡献值.当cf ≥0199时,搜索过程的的多样性急剧下降,算法收敛于局部最优解,此时算法AC O 2OVRP 启动信息素重置过程,重新初始化信息素的值.21315 信息素重新初始化为了增强算法搜索的多样性、促进算法在搜索空间的探索,信息素不定期的被重新初始化.如图1所示当算法AC O 2OVRP 接近收敛时,比如cf ≥01999,所有边上的信息素被重新初始化为015,以增强算法在搜索空间多样化探索的能力.21316 后优化过程为了进一步优化算法发现的最优解,在我们提出的算法AC O 2OVRP 集成了一个后优化过程.如图1所示,当算法的主循环终止条件满足时,算法考虑使用一个后优化过程进一步改进算法主循环发现的最优解.这里考虑的后优化过程也是一个禁忌搜索过程,其执行过程同21313节“局部搜索”中给出的描述,我们将在下一节通过实验观察后优化过程的效应.当然我们也可以选择其它复杂的算法作为算法AC O 2OVRP 的后优化过程,比如GE NI US 算法等[17].78第6期开放式车辆路径问题的蚁群优化算法。
