模糊需求可丁基取货车辆路径问题的改进人工鱼群算法

模糊需求可丁基取货车辆路径问题的改进人工鱼群算法

1优化方法与问题模型需求的可追溯性车辆路径问题（模型需求的背对角和虚脱率的实现，无论是实现还是减少，都是模型对带回货物路径问题的发展，并考虑了模糊客户需求下车辆路径优化的问题。目前，研究主要集中在单一模糊变量的车辆路径问题（模型，芦苇）或确定的车辆路径问题（勤奋和后门，虚拟现实，芦苇）。张建勇设计了一种改进的遗传算法，通过推覆和推理过程改进了遗传计算方法，解决了模糊的预测器问题。吴泰熙、陈正芳应用禁忌搜索法获得了几乎有效的虚拟现实。模型和随机算法的一致性。遗传计算方法具有鲁棒性强、适应性好的优点，但复杂函数的快速发展无法满足期望。基于经验，传统的优化方法对模糊用件的车辆路径问题的优化具有一定的局限性，可以应用新的集群智能优化方法来研究这个问题。人工鱼群算法是根据鱼群的行为特点,运用动物自治体模型的群智能优化方法,它采用的是一种自下而上设计的寻优策略.该算法简单易实现,对初值与参数选择不敏感,具有较好的全局优化能力.同时对搜索空间也具有一定的自适应能力,具有较强的鲁棒性和较好的收敛性能.目前,已成功运用于神经网络优化、石油运输系统多级站定位和多用户检测器优化设计等领域.因此,本文应用人工鱼群算法来求解具有模糊需求性质的可回程取货车辆路径问题,根据VRPBFD问题的特点改进人工鱼群算法的移动步长、人工鱼视野和觅食行为公式,以提高算法的收敛速度和运算精度.2对于模糊需求，可返回收集车辆路径问题的描述及数学模型2.1取货需求的确定具有需求信息模糊的VRPBFD问题可描述为,某个物流网络中有一个配送中心和n个待服务的节点,车辆由配送中心出发服务一定数量的节点后返回配送中心结束服务.已知每辆车的运输能力为D,每个节点的取送货需求量为一模糊数F,求满足运输要求的费用最小的车辆路线问题.对于节点不确定的取货需求量采用三角模糊数F=(f1,f2,f3)来表示,如图1所示,其中f1、f3表示该模糊数的左、右边界,f2表示其隶属度为1的点.该模糊数用隶属度函数表示为μf(x)={x-f1f2-f1,f1≤x＜f2d3-xf3-f2,f2≤x＜f30,其它μf(x)=⎧⎩⎨⎪⎪⎪⎪⎪⎪x−f1f2−f1,d3−xf3−f2,0,f1≤x＜f2f2≤x＜f3其它为了将VRPBFD问题抽象为模糊的数学模型,建立如下的基本假设条件.1)只有一个初始点,即为配送中心,每辆车都从初始点出发,完成任务后回到初始点.2)配送及回收的货物可混装.3)每个客户节点的送货需求量已知,但取货需求量不确定.4)每辆车的载重能力已知,单个客户货物质量不能超过车辆的载重能力.5)客户节点的具体位置坐标己知,即各客户之间以及客户与初始点之间的距离己知.6)每个客户节点只能由一辆车服务一次,在客户处可同时完成送货和取的任务.2.2客户节点的营造模型具体BRPBFD问题的模糊数学模型如下:mink∑k=1(βkn∑i=0m∑j=0cijxijk+λkn∑i=1uikτi+θkn∑i=1uikei),(1)s.tn∑j=1xijk=n∑j=1xjik=uik,i∈Ι,k∈Μ;(2)min∑k=1k(βk∑i=0n∑j=0mcijxijk+λk∑i=1nuikτi+θk∑i=1nuikei),(1)s.t∑j=1nxijk=∑j=1nxjik=uik,i∈I,k∈M;(2)m∑k=1uik={1,i∈Ιk,i=0(3)n∑i=1diuik-n∑j=1y0jk=0,k∈Μ;(4)∑k=1muik={1,k,i∈Ii=0(3)∑i=1ndiuik−∑j=1ny0jk=0,k∈M;(4)n∑j=0yijk-n∑j=0yjik=-diuik,i∈Ι,k∈Μ,i≠j;(5)∑j=0nyijk−∑j=0nyjik=−diuik,i∈I,k∈M,i≠j;(5)¯zijk(∑f1i,∑fΜi,∑f2i)=(z1ijk,zmijk,z2ijk);(6)zijk¯¯¯¯¯(∑f1i,∑fMi,∑f2i)=(z1ijk,zmijk,z2ijk);(6)pos{(1+α¯zijkQk)yijk+zijk≤Qkxijk}≥π,pos{(1+αzijk¯¯¯¯¯Qk)yijk+zijk≤Qkxijk}≥π,i,j∈V,k∈M;(7)xijk∈{0,1},uik∈{0,1},yijk≥0,zijk≥0,i∈V,j∈V,k∈M,(8)其中,式(1)是求最优解目标函数,使运输成本最小;式(2)是目标约束,保证每个节点只被一辆车服务一次;式(3)表明客户节点只可以被一辆车访问,而初始节点被所有车辆访问;式(4)、(5)表明为各客户节点的送货需求量;式(6)、(7)为各节点的模糊取货量¯f1=(f1i,fΜi,f2i)f1¯¯¯=(f1i,fMi,f2i)为三角模糊数,则车辆k上的取货量之和zijk=(z1ijk,zmijk,z2ijk)为三角模糊数;式(8)为各个决策变量取值约束.3基本人工鱼群算法1)人工鱼群初始化.随机生成初始N规模鱼群,人工鱼个体在t时期的状态可表示为向量X=(Xi(t),i=1,2,…,F_number),其中,Xi(t)为欲寻优的变量,即当前车辆的载货量.目标函数式(1)决定人工鱼当前所在位置的食物浓度,表示为Y=F(Xi(t)).人工鱼个体之间的距离表示为Di,j=‖Xi-Xj‖.Visual表示人工鱼的感知范围.step表示人工鱼移动的步长.δ表示拥挤度因子.对于VRPBFD问题需要将人工鱼的初始位置放在起点和终点上,因为车辆只有从起点出发到达终点,或从终点出发回到起点才是一个有效解.2)自适应的邻域搜索范围.在基本人工鱼群算法中,人工鱼Xi的邻域定义为Ν={Xj|di,j＜Visual}N={Xj|di,j＜Visual},其中邻域半径Rn的确定非常关键,如果太大不足以发现一些重要个体,如果太小会形成局部极值点,降低算法搜索速度.根据文献引入鱼群感知范围的概念:排斥区、中性区和吸引区,如图2所示.假设鱼的邻域距离为R1,在这个距离之内的其他鱼对此鱼有排斥作用.邻域距离在R1和R2之间为中性区域,在这个范围内的其他鱼对此鱼的作用可能为排斥,也可能为吸引.邻域距离R2和R3之间的区域为吸引区,在此区域的其他鱼对此鱼有吸引作用.距离R3之外不属于鱼的感知范围.3)自适应的觅食行为.由于基本人工鱼群算法中,人工鱼只能向前不能后退,即使在人工鱼的后方发现食物,也不能改变人工鱼的运动方面.因此,根据文献引入αk(t)、βk(t)为速度向量与两个坐标轴的方向角,根据αk(t)=1nk(t+1)∑j∈Νk(t-1)αj(t+1),βk(t)=1nk(t+1)∑j∈Νk(t-1)βj(t+1)αk(t)=1nk(t+1)∑j∈Nk(t−1)αj(t+1),βk(t)=1nk(t+1)∑j∈Nk(t−1)βj(t+1)分别确定参数α、β的值,决定人工鱼群下一步的移动方向.并且根据文献引入交换序操作符“⊕”重构人工鱼群算法的觅食公式:Xi(k+1)=αk(t)Xik⊕βk(t)Random(Step)Xjk-Xik∥Xj-Xi∥,αk(t)Xik⊕βk(t)Random(Step)Xjk−Xik∥Xj−Xi∥,Yj>Yi,其中,Xjk、Xik和Xi(k+1)分别表示状态向量Xi、Xj以及人工鱼下一步状态向量Xi(k+1)的第k个元素,Random()表示间的随机数.这样就扩大人工鱼群算法的搜索范围,加快人工鱼群的寻优速度.4)聚群行为.设人工鱼当前状态为Xi,整个人工鱼群的中心位置为Xck,如果Yc/δ>Yi(δ>1)表明伙伴中心位置有较多食物且不太拥挤,则按Xi=Xi+rand(Step)Xck-Xi∥Xck-Xi∥向鱼群中心位置移动,否则执行觅食行为.5)追尾行为.设人工鱼群当前邻域内伙伴Xmax的位置最优,最优值为Ymax>Yi,表明伙伴Xmax具有较高的食物浓度并且不太拥挤,则按Xi=Xi+rand(Step)Xmax-Xi∥Xmax-Xi∥向伙伴Xmax前进一步,否则执行觅食行为.6)根据决策者主观偏好动态调整人工鱼视野和步长.根据文献引入决策者主观偏好,当车辆服务k个节点后其总运载量为D′k=k∑i=1Di,车辆k剩余运载能力Qk=C-D′k,即Qk是一个三角模糊数,下一节点需求量小于车辆剩余运输能力可能性为p=pos{dk+1≤Qk}=sup{min{μQk+1(x),μQk(y)}x≤y}={0,d2,k+1≤q2kq3k-d1,k+1(q3k-q2k)+(d2,k+1-d1,k+1),d2,k+1≥q2k,d1,k+1≤q3k1,d1,k+1≥q3k车辆服务时通过对比自身剩余空间Qk和待服务节点k+1的需求Dk+1,得出k点的置信水平,来确定该车辆是否有能力继续服务.对下一节点需求量小于剩余车辆容量的可能性表示为P=pos{Dk+1≤Qk},很明显P值越大该车能够完成下一任务的可能性越大.在此,令P*(P*∈)表示决策者主观偏好值.当P≥P*时,该车继续完成下一运输任务;若P<P*,该车返回车场,新派车完成剩余运输任务.根据决策者主观偏好值P*来动态调整T时刻人工鱼的视野和步长,即{Step=Step×Ρ*+StepminVisual=Visual×Ρ*+Visualmin7)局部最优逃逸策略.通过鱼群的拥挤程度判断实际问题出现“失败”的情况,采用邻域搜索策略实施逃逸,以当前新的客户点(xadd,yadd)为圆心,以其到车场的距离为半径的圆形范围内寻找能对新的客户点进行服务的在途车辆,即满足√(xk-xadd)2+(yk-yadd)2≤√(x0-xadd)2+(y0-yadd)2其中,(yk,yk)为干扰发生时刻车辆k所在的位置,(x0,y0)为车场的位置,从而得到能服务新的客户点的在途车辆集合.当所有在途车辆均无法为新客户点服务时,则需从车场中增派车辆为其服务,而增派车辆从车场到达新客户点.4模糊参数设计为验证改进人工鱼群算法的有效性,将Solomon的实例R101改造成为25、50个节点VRPBFD问题,并将每组的实验结果与文献中的实验数据进行比较.当主观临界值P*≤0.6时,预计行驶距离的增加量小于额外行驶距离的减小量,从而使得随着P*值增加,总行驶距离逐渐递减.而当P*>0.6时,预计行驶距离的增加量大于额外行驶距离的减小量,从而使得随着P*值增加,总行驶距离逐渐增加.仿真结果如表1所示.将Solomon的实例R102改造成为一个25个节点模糊需求的带回程取货车辆路径问题,设3的倍数节点为送货节点,所有模糊参数设计为峰值已知的精确参数.令P=0.8,α=β=0.9.将改进人工鱼群算法的运行结果与文献模糊推理的Sweeping算法进行比较,10次随机实验的结果如表2和图3所示.实验结果表明在车辆使用