1.一种多车场多车型的车辆路径规划方法,包括如下步骤:
步骤1,以车辆配送的总成本最低为目标建立目标函数如下:
其中,目标函数的第一部分为配送车辆的固定成本,第二部分为配送车辆的可变成本;
目标函数的相关约束如下:
以上公式中,式(1)表示目标函数,即配送任务的最低总成本;式(2)表示所使用的车辆不能超过当前所拥有的车辆总和;式(3),式(4)表示一个客户只能被一辆车服务一次;式(5)表示一辆车所服务的客户的需求总量不超过该车的载重;式(6)表示车辆从车场出发并返回原车场;式(7)表示一辆车不能从一个车场直接进入另一个车场;
其中,Z表示目标函数的值,即配送方案的总成本;M表示客户的数量,K表示多个车场内的所有可用的车辆的总数量;k表示车辆的编号;Qk表示车辆k的最大装载量;qi表示客户i的需求量;dij表示从客户i所在位置到客户j所在位置的距离;ck1表示车辆k的固定成本;ck2表示车辆k的可变成本;如果车辆k从客户i所在位置到客户j所在位置,则xijk=1,否则,xijk=
0;
步骤2,编码并重新定义相关操作方式:
步骤2.1,编码:对于一个共有M个客户,K辆不同车型的车辆路径规划问题,将客户的编号设置为1~M,车辆的编号为(M+1)~(M+K),表示共有K辆车,则人工鱼的位置编码由两部分组成,第一部分的编码为车辆的编号,第二部分的编码为客户的编号;
步骤2.2,重新定义人工鱼之间的距离:人工鱼Fa和人工鱼Fb之间的距离dis(Fa,Fb)为Fa与Fb编码的对应位置上的不相同的编号的个数,对于车辆部分的编码,如果不同编号代表的是同车场同车型的车辆,则认为编号相同;
步骤2.3,重新定义视野范围内的人工鱼集合:对于人工鱼Fa,在其视野范围V内得到的其他人工鱼的集合Sa,即当人工鱼Fb满足dis(Fa,Fb)≤V时,称人工鱼Fb为人工鱼Fa的邻域内的伙伴;设集合内人工鱼的数目为na;
步骤2.4,重新定义中心位置:当集合 时,表明人工鱼Fa的感知范围内存在其他伙伴,则该集合的中心位置定义为:集合Sa内na条人工鱼客户编码对应位置上出现最多的值作为中心位置对应的客户编码值,人工鱼集合Sa中心位置Facen的车辆编码为Fa的车辆编码;
如果出现次数最多的值不止一个,则采用顺序靠前的值;
步骤2.5,重新定义人工鱼的移动方式:人工鱼Fa向Fb移动,从Fa客户编码的第一位客户编号开始起,在步长L内,L小于客户的数量,比较Fb和Fa的编码序列;从Fb客户编码的第一个客户编号开始,依次与Fa在L长度内的客户编号进行比较;如果L长度内,Fb的某一个客户编号在Fa的L长度内出现,则按照其出现的先后次序记录在F′a的客户编码中,直至所有L长度内的客户比对完毕,剩余的部分按照在Fa中的先后顺序依次填入F′a,得到新的位置F′a;
步骤2.6,重新设计随机算子:人工鱼Fa尝试向种群最优个体Fbest移动到新的位置F′a,适应度为f′a,如果f′a>fa,则令Fa=F′a,其中fa为人工鱼Fa的适应度;否则,采用2‑opt搜索算子对Fa的客户编码部分进行操作,随机产生一个新的位置F′a,令Fa=F′a;
步骤2.7,重新定义人工鱼的步长L:人工鱼在移动时,人工鱼位置与目标位置的客户编码对比的长度,即在步长L内对比两者的客户编号;
步骤3,种群初始化,种群规模为P,人工鱼的视野范围为V,试探次数为N,拥挤度因子δ,迭代总次数G,种群最优个体为Fbest,最优适应度为fbest,移动的步长为L;模拟退火算法的初始温度T,降温系数为r,终止温度为T2,内循环迭代次数为H,具体操作如下:步骤3.1,建立二维坐标系,根据各个车场的坐标位置,将所有车场用线段连接起来,形成一个多边形U,求出该多边形的重心U0作为扫描算法的原点O;
步骤3.2,以原点O为中心,随机选择一个客户i,从客户i按照顺时针或者逆时针方向依次扫描所有的客户点,记录扫描到的客户顺序A;
步骤3.3,人工鱼编码的车辆编码部分随机生成,将A作为客户编码部分;
步骤3.4,重复操作,生成P个个体,计算个体适应度;
步骤4,计算人工鱼的适应度:按照人工鱼Fa中的客户编码部分的顺序,依次取出未分配的客户,按照车辆编码部分的顺序取出未分配的车辆k,将客户依次分配给车辆k,计算所分配客户的配送总重量,直到超出车辆k的最大装载量Qk,此时为第i位客户,获得车辆k的客户服务序列;然后,再根据编码顺序,取出下一辆车,从第i位客户继续分配,直到超出当前车辆的载重为止;依次进行以上操作,直到所有的客户都被分配完毕,获得车辆的配送路线,再计算适应度fa;
步骤5,对每条鱼进行评价,同时对每条鱼的行为进行选择,包括觅食行为、聚群行为、追尾行为和随机行为,操作的具体步骤如下:步骤5.1,计算人工鱼Fa与视野范围内其他人工鱼的距离,获得当前邻域内人工鱼的集合Sa,集合内人工鱼的数目为na;
步骤5.2,尝试对人工鱼执行聚群算子,人工鱼Fa的适应度为fa,拥挤度因子为δ,视野内人工鱼集合Sa的中心位置为Facen;
步骤5.2.1,判断集合Sa是否为空,若是,转步骤5.4,完成后再转步骤5.2.4;若不为空,转步骤5.2.2;
步骤5.2.2,计算中心位置Facen及其适应度facen;
步骤5.2.3,判断,如果facen>fa且facen/na<δ×fa,则向中心位置Facen前进一步;否则,转步骤5.4,完成后再转步骤5.2.4;
步骤5.2.4,记录聚群行为得到的新的位置Fa1以及适应度fa1;
步骤5.3,尝试对人工鱼执行追尾算子,人工鱼为Fa,拥挤度因子为δ;
步骤5.3.1,判断集合Sa是否为空,若是,转步骤5.4,完成后再转步骤5.3.4;若不为空,转步骤5.3.2;
步骤5.3.2,找到集合Sa内的最优人工鱼Fb,如果fb≤fa,转步骤5.4,完成后再转步骤
5.3.4,其中fb为人工鱼Fb的适应度;否则,执行步骤5.3.3;
步骤5.3.3,判断,如果fb>fa且fb/na<δ×fa,则向视野范围内的最优人工鱼Fb前进一步;否则,转步骤5.4,完成后再转步骤5.3.4;
步骤5.3.4,记录追尾行为得到的新的位置Fa2以及适应度fa2;
步骤5.4,执行觅食算子,设置一个0‑1之间的数ran,用来随机选择对车辆编码部分或客户编码部分进行搜索;
步骤5.4.1,产生一个随机数Rand,如果Rand<ran,则对Fa车辆编码部分进行搜索;否则对客户编码部分搜索;
步骤5.4.2,从1‑opt交换搜索算子、2‑opt交换搜索算子、3‑opt交换搜索算子中随机选择一个,对5.4.1中的选择结果进行搜索,得到F′a;
步骤5.4.3,计算F′a的适应度为f′a,如果f′a>fa,则将F′a向种群最优Fbest移动,转步骤
5.4.5;否则,转步骤5.4.4;
步骤5.4.4,判断尝试次数是否超过N,若小于,则转步骤5.4.1;否则,转步骤5.4.5;
步骤5.4.5,判断是否进行了移动,若是,记录移动后的位置Fa3及其适应度fa3;否则,执行随机算子,记录新的位置Fa3并计算适应度fa3;
步骤5.5,进行行为的评价,如果max{fa1,fa2,fa3}>fa,则将对应操作的得到的值作为操作之后的值;否则,保持原来的人工鱼Fa不变;
步骤5.6,对每一条人工鱼执行步骤5.1至步骤5.5,更新人工鱼种群;
步骤6,计算新种群的适应度,并更新种群中的最优解Fbest;
步骤7,对种群最优解Fbest进行模拟退火搜索,初始温度T,降温系数为r,当前温度T1=T,终止温度为T2,内循环迭代次数为H;记录退火之前的种群最优解为Fbest,最优适应度为fbest;
步骤7.1,执行内循环的前H/2次,对人工鱼编码的客户编码部分进行操作,车辆编码部分不变,具体操作为:对人工鱼的客户编码采用逆序邻域搜索算子产生候选解,如果min{1,exp[‑(Z(Fb)‑Z(Fa))/T1]}≥random[0,1],则令Fa=Fb;记录退火搜索到的最优的适应度为fsa,最优解Fsa;
步骤7.2,执行内循环的后H/2次,对人工鱼编码的车辆编码部分进行操作,客户编码部分不变,具体操作为;对人工鱼的车辆编码采用2‑opt交换搜索算子产生候选解,如果min{1,exp[‑(Z(Fb)‑Z(Fa))/T1]}≥random[0,1],则令Fa=Fb;记录退火搜索到的最优的适应度为fsa,最优解Fsa;
步骤7.3,令T1=T1*r,如果T1≤T2,则模拟退火搜索终止,进行判断:如果fsa>fbest,则令Fbest=Fsa,fbest=fsa,否则保持Fbest不变,避免出现退化;如果T1>T2,继续执行步骤7.1;
步骤8,一次迭代结束,迭代次数g=g+1;
步骤9,判断是否满足终止条件,若g=G,记录最优个体Fbest,执行步骤10;否则,返回执行步骤5,进行新一轮迭代;
步骤10,对最后记录的最优个体Fbest进行解码,计算适应度fbest,目标函数的值为Z=1/fbest;解码后,两个相同车辆编号之间的客户即为该车辆的配送路线,未被使用的车辆不在解码序列中出现,输出最优方案。