杨文璐,宁玉富
(1、山东师范大学管理科学与工程学院,山东 济南 250014;2、德州学院不确定系统实验室,山东 德州 253023)
在物流配送活动中,如何确定车辆行驶路径既能满足所有客户的配送需求,又能保证总配送成本最低的问题,被称为是车辆路径问题(Vehicle Routing Problem,VRP)。VRP一直以来都是物流配送商最为关心的问题,也是很多相关学者竞相研究的焦点与热点问题。这一问题最早是由Dantzing和Ramser二人在1959年提出的[1],它的有效解决是减少物流费用和提高物流效率的关键。由于VRP早被证明属于NP-hard问题[2],一般对于它的研究大多都集中在如何找到极优解上。长期以来对于解决VRP的方法研究主要集中在启发式算法上,如禁忌搜索算法、模拟退火算法、遗传算法等。近年来随着很多学者对群智能算法的聚焦和大量研究,粒子群算法、蚁群算法、蜂群算法、萤火虫算法等群集智能算法也越来越多的应用于VRP的解决中。
2006年由He和Wu二人提出的群搜索优化(GSO)算法[3]也归属于众多群智能算法之中,该算法是源于对群居动物觅食行为的模拟而演化产生,并且建立在PS(Producer-Scrounger)模型基础之上,经过实验验证表明,标准GSO算法在解决高维多模态问题上具有明显的优势[4],但算法本身存在早熟收敛、搜索精度不高、后期迭代效率不高并容易陷入局部极优点的问题。本文针对标准GSO算法存在的问题进行了改进,并将改进后的CMGSO算法应用于VRP的研究,获得了较好的效果。
本文所研究的VRP可描述为:在已知可用配送车辆数量及其装载容量、客户数量及其需求量的情况下,要求承担配送任务的每辆车只能向其所配送的客户提供有且仅有一次服务,并最终回到配送中心,而所有参加配送的车辆不能对同一客户提供服务且它们能够满足所有客户的需求,但是最终却能达到运输成本(如路程、时间、花费等等)最低的目标。
根据1.1的问题描述VRP数学模型可表述为:假设用0来标识配送中心,共有n个客户需要配送服务,有m(本文在这里将不对m进行研究)辆车进行配送活动,每辆车的最大载重量为q,客户i对货物的需求量为,第k辆车从客户i到客户j记为,客户i由第k辆车负责配送记为,从客户i到客户j的运输成本记为,要求在满足所有约束条件的情况下,达到运输成本最小(本文主要研究路径最短的情形)的目标。
在建立模型前,先定义如下两个变量:
由此可以建立如下目标函数:
问题的约束条件则为:
其中,约束式(4)和(5)共同保证了有且仅有一辆车为某位客户提供配送服务,而约束式(6)则确保了每个客户的配送需求只由一辆车来满足,且所有客户的配送需求由全部的m辆车来共同满足,最后约束式(7)对每一辆进行配送服务车的载重容量进行了规定。
GSO算法根据动物觅食策略将群成员分为发现者(Producer)、加入者(Scrounger)和游荡者(Ranger)3 种[5],并利用生物学的视觉搜索原理对食物进行搜索,其中所有成员都有初始化的位置与角度。在算法开始后的迭代计算过程中,都将会对所有个体的适应值进行计算比较,并从中搜索出拥有最佳适应值的个体设置为原始发现者,之后原始发现者会在当前位置上对周围一切可行解区域进行寻优搜索,寻找是否存在比当前位置更好的位置,如果发现更好位置便向新位置移动,否则保持原位置不变;而群体中的其它成员中80%作为Scrounger按搜索公式跟随Producer进行搜索,其余的20%作为Ranger按搜索方程在觅食区域内进行随机地游弋[6]。在迭代过程中发现者始终保持最优位置,加入者则向发现者靠拢,游荡者起到了加大搜索范围的作用,每个个体都可以在3种角色中切换,直至满足结束条件时,算法结束。算法流程见图1。
图1 GSO算法流程图
在CMGSO算法中对于由交叉操作[7]更新所得到的新加入者来说,如何确定其能否成为替代原有个体,加入到本次迭代中,主要通过Metropolis准则[8]的优值增量计算来作为判定标准。上式中的f=(x)为所要满足的目标函数。将由交叉操作得到的的位置和搜索角度代入目标函数中来计算,如果△f<0,则替换原有的成员,进行下一步来判定是否用替换原有成员进入第k次迭代,即公式(8)。这样保存了较好的移动方向以便预测到更好的移动位置的同时又能达到概率性跳出局部最优值的目的。的计算,否则通过Metropolis准则中的概率exp(-△f/Maxlter)
其中,rand是[0,1]间的随机数,Maxi-ter 是最大迭代次数。
对于群体中的Ranger来说,在第k次的迭代中,对于新产生的则不选择更新,即否则,进行更新。
在GSO算法的基础上通过引入交叉因子和模拟退火算法[9]的思想改进了原算法,并提高了该算法的收敛速率和优化效率,CMGSO算法的步骤描述如下:
步骤1:选定GSO种群规模S;
步骤2:初始化每个群成员的位置和角度;
步骤3:对每个成员计算其适应度值;
步骤4:比较各个成员的适应度值,记录自身最优值和群体最优成员Producer;
步骤5:根据公式(9)(10)(11)和公式(12)改变粒子的位置和搜索角度;
步骤6:执行轮盘赌[10]选择和交叉操作,生成新一代种群;
步骤8:检查是否满足GSO算法终止条件,否则,转至步骤4,继续;若是,则求出最优解。
将改进后的群搜索算法CMGSO应用于VRP研究中的具体实现步骤如下:
1)编码及初始化。本文在这里采用自然编码的方法对物流车辆路径问题中所涉及的配送中心、客户和车辆进行编码,其中,配送中心编码为 0,客户依次编码为 1,2,…,n,配送车辆则编码为1,2,…,m。当配送中心有k辆车参与配送服务时,那么就存在k条配送路径。假设只有一个配送中心,且车辆的排序是给定已知的,则只需对客户排序进行初始化,在这里本文将采用随机生成的方式来对所有需要配送的客户进行排序。例如:存在8位客户需要由3辆车对其进行服务,假设这8位客户的随机排序为72568413,则将由1号车依次对其进行配送活动,如果客户7256的总需求量超过了1号车的最大载重量,而725的总需求量却小于其最大载重量,则1号车将只对前三位客户进行配送服务。按照同样的原则来初始化出2号、3号车的配送路径。
2)参数设置。变量的个数设为Q,种群的规模设为S,交叉的概率设为P。其中P一般设置在[0.5,1]的区间上。
其中,Fi代表第i个个体的适应度;Zi为第i个个体的目标函数值,即由公式(3)计算所得到的值;Ni为第i个个体的不可行配送路径数,而其前的系数α是对于不可行路径的损失系数。
在设置好适应度函数后,便可以计算出各个个体的适应度值并对其进行比较排序,按照CMGSO算法的要求从中找出Producer、Scrounger和Ranger三种群成员。
4)寻优搜索。在上一步中得到的Producer、Scrounger和Ranger三种群成员分别按照各自的寻优搜索公式进行计算,并最终决定这三类成员是否更新和角色变换。其寻优搜索公式请分别参见本文的公式(8)、(9)、(10)、(11)及(12)。
5)选择交叉。用轮盘赌的方式选出当前Scrounger中优良的个体作为交叉操作中的父代,并对其按公式(14)进行交叉计算。交叉后的新个体增加了粒子的多样性,便于跳出局部最优,同时还可以加快算法的收敛速度。
其中,为交叉后得到的子代;fPi(x)(i=1,2)为参与交叉运算的父代;p是D维均匀分布的随机数向量,p的每个分量都在[0,1]取值。
6)模拟退火。将上一步中获得的新个体进行模拟退火的过程,利用Metropolis准则判断是否对其进行保留。若通过验证,则将新个体保留并进入到下一步的计算中;若未通过,则对其进行舍弃操作。
7)输出最优路径。当计算出的最佳适应度值与平均适应度值小于所设定的允许误差时,或迭代次数达到所设定的最大值时,输出此时的最优结果即为最优车辆路径;否则将跳入3)并重复3)-7)的计算,直至满足终止条件,算法结束。
根据以上对于CMGSO算法在VRP中应用实现的具体步骤的表述,采用MATLAB编程,并对文献[11]中所列出的3辆车服务于8位客户的物流VRP实例进行实验。其中,种群规模,为100,运行代数为300,交叉概率取0.9,不可行路径的损失系数为10;每辆车的最大载重量设置为10t;1-8号客户的配送需求量依次为 2.5t、2t、5t、3.5t、2t、4.5t、3t、3.5t;每位被服务的客户之间的距离见表1,表中的距离单位为km。
3)适应度函数。适应度函数的选取直接影响到对每个个体好坏的判断,并最终关系到最优解的获取情况,所以恰当选择适应度函数是非常必要的。针对本文要解决的VRP,将适应度函数设置为:
表1 客户间的距离
在计算机30次的随机求解中,有23次都可求得最优解的路径总长度为850km,与之相对应的车辆路径分别为0640,03120,08570,其中0640表示第一辆车从配送中心出发先后为6号和4号客户服务再回到配送中心。将使用CMGSO算法得到的实验结果与使用标准GSO算法和PSO算法的结果进行比较后(见表2),可知在同样运行环境中且种群规模相当的情况下,本文提出的CMGSO算法对于物流中的车辆路径优化问题的解决有着较好的寻优效果和收敛效率。
表2 3种算法运行结果的比较
本文提出了一种将改进后的CMGSO算法应用于VRP研究的策略,并通过对该算法的应用实现及编程实验证明了它与标准GSO和PSO算法相比具有较好的寻优效果及收敛效率。为VRP的研究和解决提供了一种新的方案和思路。该算法的改进主要是在原有GSO的基础上加入并融合了交叉因子和模拟退火的算子,这样一来就很好的解决了标准GSO中存在的早熟收敛、搜索精度不高、后期迭代效率不高,以及在后期运算中容易陷入局部极优点等问题,并使其获得了更好的最优解。
[1]王永锋,杨育,顾永明,吴彩明.求解带时间窗车辆路径问题的混沌遗传算法[J].计算机应用研究,2012,29(7):2423-2426.
[2]陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究,2012,29(6):2031-2034.
[3]HE S,WU Q H.A novel group search optimizer inspired by animal behavioral [C].2006 IEEE Congress on Evolutionary Computation,2006:4415-4421.
[4]HE S,WU Q H,SAUNDERS J R.Group search optimizer:an optimization algorithm inspired by animal searching behavior[J].IEEE Transactions on Evolutionary Computation,2009,13(5):973-990.
[5]ZHANG Wen-wen,TENG Shao-hua,LI Li-juan.Improved group search optimization algorithm [J]. Computer Engineering and Applications,2009,45(4):48-51.
[6]房娟艳,曾建潮,崔志华.混合群搜索优化算法及其应用研究[D].太原:太原科技大学,计算机科学与技术学院,2010.
[7]刘鲭洁,陈桂明,刘小方,杨庆.基于遗传算法的SVM参数组合优化[J].计算机应用与软件,2012,29(4):94-100.
[8]CHEN Xiao-juan,XHEN Jing.QoS routing algorithm based on genetic simulated anncaling algorithm [J].Application Research of Computers,2012,29(12):4680-4682.
[9]Metropolis N,Rosenbluth A.W,Rosenbluth M.N,et al.Equations of states calulations for fast computingmachines[J].Jchem Phys,1953,21:1087-1091.
[10]向万里,马寿峰.基于轮盘赌反向选择机制的蜂群优化算法[J].计算机应用研究,2013,30(1):86-89.
[11]宾松,符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程,2003,21(6):12-14.