1.一种考虑装卸约束的多车厢点对点取送货路径规划方法,其特征在于,包括:采集天气情况、载重、道路条件、交通状况、时间窗和货物特殊性信息;
将所述采集到的信息,结合多车厢点对点取送货的特点,录入计算机分析处理;
所述分析处理后,生成初始种群解决方案,并基于种群的元启发式方法以及局部搜索策略,得到合适的车货匹配、装卸方案以及路径规划;
所述的考虑装卸约束的多车厢点对点取送货路径规划方法还包括:预处理方法,分别为多信息录入分析和生成初始种群方案;
种群优化方法,对预处理方法中的初始种群方案进行分析生成初始种群解决方案进行优劣度策略排序并分组,利用计算机支持多进程的特点,对每个分组内的种群方案进行自适应概率吸引以及交叉操作;
方案优化方法,分别为车辆数目优化、局部搜索和车厢空间优化,该方法在插入准则的约束下对单一解进行持续优化;在种群优化方法中的算法迭代达到阈值后,导出全局最优解;
所述多信息录入分析,包括:
综合考虑载重、天气情况、道路条件和交通状况因素,对车辆行驶速率、货物运送路线和空调开启的影响;同时,将天气情况根据风力、雨雪和大雾进行分级;道路条件根据道路的颠簸度进行分级;交通状况根据路宽下的拥堵程度进行分级;气温根据温度分级;载重根据车厢内的装载率对车辆的平均速度进行预估;
建立分级表将天气、道路和交通分为A、B、C、D四个等级,每个等级对应0到1间的数值,综合后节点i到节点j的路径上路况因素为δi,j:δi,j=α·Weather+β·Bump+γ·Congestion其中,α、β、γ分别为三种相应影响因子的权值,取值范围为[0,1.5];Weather表示天气,Bump表示道路,Congestion表示交通;根据实际情况设定,一般情况下0≤δi,j<1,若出现δi,j大于等于1的情况,则表示节点i到节点j的路径不予通过;
所述载重、天气情况、道路条件和交通状况因素,对车辆行驶速率、货物运送路线和空调开启的影响,包括:通过工作时长计算司机配送费,计算公式为:
其中,A是任意节点i到节点j的弧集合,即车库到取送货点和取送货点之间的路线;R表示车辆集合; 分为两种情况,若取值为1,则r车经过弧(i,j),若取值为0,则r车没经过弧(i,j);c为单位时间司机的配送费用;ti,j是无干扰下经过弧(i,j)所花费的基础时间;Tbase为空载时对行驶时间的影响率且Tbase=1,Tmax是满载情况下对行驶时间的影响率,Tmax>Tbase; 为经过弧(i,j)时车辆r的载重率,计算公式为:其中,Dvi是划分车厢数;Q是车厢的最大负载;si,k为节点i处车厢k经过装卸后的负载情况,0≤si,k≤Q;根据车厢划分数Dvi,车辆r的车厢k范围为[Dvi×r+1,Dvi×(r+1)];
根据载重对于车辆行驶速率的影响,计算燃油消耗费用Oil,计算公式为:其中,di,j为弧(i,j)的长度;o为单位里程基础油耗费用;Lbase为空载时对基础油耗的影响率且Lbase=1,Lmax是满载情况下对油耗的影响率Lmax>Lbase;
根据气温级别确定是否打开空调,并结合载重、天气情况、道路条件和交通状况对于车辆行驶速率的影响,计算空调油耗费用AirCon,计算公式为:其中,εi,j为弧(i,j)在气温影响下,开启空调后的单位时间油耗,默认为0;
基于所述司机配送费、燃油消耗费用、空调油耗费用的计算结果,计算总费用TotalCost,计算公式为:TotalCost=min(Oil+Driver+AirCon+mv)其中,m为使用的车辆数目,v为单辆车派出的固定成本;
所述货物特殊性,包括:
货物特殊性包含抗颠簸能力、负相关性及强相关性;
在模型中设计公式对强相关性进行约束;
强相关性指若干货物拥有相同取货点或送货点,设计的强相关性约束公式表示如下:di+n,j+n=0,cori+n,j+n=1,i,j∈P其中,cori,j表示节点i和节点j的强相关性,分为两种情况,若取值为1,则表示强相关,若取值为0,则表示不强相关;n为取送节点对个数,P表示n个取货节点集合P={1.....,n};
此公式的含义为,若送货点i+n与送货点j+n之间的距离为0,则送货点i+n与送货点j+n强相关,车辆必须同时卸载这两个送货点的货物;
di,j=0,cori,j=1,i,j∈P
其中,此公式的含义为,若取货点i与取货点j之间的距离为0,则取货点i与取货点j强相关,车辆必须同时装载这两个取货点的货物;
其中,yi,k表示在节点i时车厢k的操作情况,若对k车进行操作,值为1,否则为O;S表示车厢集合;此公式的含义为,若取货点i与取货点j,或送货点i+n与送货点j+n强相关,则两个取货点的货物必须由同一车辆配送;
所述基于种群的元启发式方法以及局部搜索策略,得到合适的车货匹配、装卸方案以及路径规划,包括:对于种群优化方法中的任一方案,设计编码方式以实现常见编码方式无法将路径顺序、车辆和车厢操作同时对应的问题;
设计编码方式表示为:
(0 x1 x2 0 x3 ... x2n 0;0 p1 p2 0 p3 ... p2n 0)其中,在左侧编码中,xi代表访问的节点,顺序解析左侧编码,若遇到0则代表访问了车库节点,以0分割,获取车辆子路径;在右侧编码中,pi代表操作的车厢;根据适用场景中的Dvi,在[0,Dvi‑1]中取整数值,以0分割后可作为分组遗传算法的染色体进行交叉操作;
所述种群进行优劣度策略排序并分组,包括:
优劣度策略结合适应度与可优化程度进行排序和分组;
结合后的优劣度策略公式表示为:
其中,Residual表示为平均最大车厢剩余空间,Quality表示为优劣度,max(Cost)表示当前种群中适应度的最大值,α、β、γ、δ分别表示各影响因子的权值,取值范围为[0,1];
排序,将解决方案集中的所有解决方案按照优劣度从大到小进行排序,并去除相同方案,排序后的解决方案集为X=(X1,X2,...,XNM),方案集中的方案适应度满足Quality(X1)≥Quality(X2)≥……≥Quality(XNM);
分组,将前N个方案作为主方案,剩下N(M‑1)个作为猎物方案,每一组由1个主方案与M‑
1个猎物组成,最优的猎物与最好的主方案一组,次优的与次好的主方案一组,直到第(N+1)个最优的猎物与最好的主方案一组,最后的猎物与第N个主方案一组,完成分组;
可优化程度包含路径稀松度与平均最大车厢剩余空间;
所述对每组内的方案群体进行自适应概率吸引以及交叉操作,包括:计算与主方案的自适应吸引概率,若猎物方案被主方案吸引,则进行交叉操作产生子方案,并让子方案通过方案优化方法进行优化,若猎物方案没被主方案吸引,则猎物逃脱,猎物方案进行解决方案优化;
方案细化为:
解析主方案和猎物方案;主方案和猎物方案各自转换成子路径集合,集合中的子路径编码不包括节点操作的车厢号,设count=0;
子路径集合排序;将每个子路径集合按照子路径覆盖节点的数量,由大到小进行排序;
选取主方案子路径集合的子路径A;根据所述子路径集合排序,遍历主方案的子路径集合,选取主方案的子路径A;
计算子路径A与猎物方案子路径集合中的子路径的最近距离;若猎物方案的子路径集合不存在可遍历的子路径,跳转至计算主方案与猎物方案的吸引概率γ,否则,根据所述子路径集合排序,遍历猎物方案的子路径集合,设遍历到子路径B,距离r的计算公式为:其中,Ai、Bi分别是A与B子路径编码的第i个访问的节点,n为A与B中的最小的节点覆盖数,若A与B覆盖节点数不同,需要从左至右、从右至左计算两次距离,取最小值;r随着两条子路径间距离的提升而提升,r越小,代表两条子路径的相似度越高;
所述遍历通过遍历终止准则约束,分为两种情况,A覆盖节点数比B多且连续m次A覆盖节点数与B不同(m为任意正整数),或者集合遍历结束;
遍历终止后,记录本次最短距离rcount以及对应的子路径A与B,将A与B分别在其集合中标记,不参与之后的遍历;若主方案子路径集合仍有待遍历的子路径,则count=count+
1,并返回所述选取主方案子路径集合的子路径A;
计算主方案与猎物方案的吸引概率γ;吸引概率Y的计算公式为:k
γ=e
其中,n为取送货对的个数,α和β分别为最短距离与取送货点对个数对于吸引概率的影响权重,取值范围为[0,2],取平均值后参与计算总体的吸引概率,α和β的具体数值根据实际的实验样本参数改变;
产生随机数μ(μ在[0,1]范围内随机产生),若μ<γ,则猎物被吸引,否则猎物逃离;
其中,主方案和猎物方案都是解决方案种群中的解;解代表解决的是车货匹配、装卸方案以及路径规划问题的一种可行解。
2.如权利要求1所述的考虑装卸约束的多车厢点对点取送货路径规划方法,其特征在于,所述插入准则,包括:道路条件约束、强相关约束及顺路程度;
通过所述顺路程度,计算插入的取送货节点对于相邻位置的影响;
顺利程度的函数表示为:
其中,i与i+n为待插入的取货点与送货点;函数分为取送节点分开、取送节点相邻两种情况;取送节点分开的情况,指的是取货点在节点a与b间插入且送货点在节点c与d间插入;
取送节点相邻的情况,指的是取货点送货点在a与b间插入;(Px,Dy)表示所有可能的插入方式的其中一种,设定M为所有可能的插入方式集合表示为(x,y)∈M;通过轮盘的方式进行选择,则插入方式(Px,Dy)被选择的概率表示为:
3.如权利要求2所述的考虑装卸约束的多车厢点对点取送货路径规划方法,其特征在于,所述解决方案优化,包括:减少车辆数目,通过局部搜索包括路径间、路径内和车厢间3类算子,生成对多车厢的车厢空间优化方案;
多车厢的车厢空间设计优化如下:
A车厢路径的待移动的i取货点和对应i+n送货点之间,对应在B车厢路径中,货物都有的取送流程,即表示都取货且配送完毕,也表示货物满足后进先出原则;
A车厢内的i货物装配到B车厢后,取送点间的所有取货点处堆栈满足容量要求,判断堆栈容量要求的公式表示为:qi+max{Sj,B,...,Sk,B}≤Q,j,...,k∈M其中,qi为货物i所需占用的车厢容量,即车厢长度;sj,B为B车厢路径途径节点中j节点的车厢占用情况,选取途径节点中占用车厢长度最多的节点进行容量判断,若加上货物i的占用车厢长度后满足容量需求,则满足所述取货点处堆栈满足容量要求;
针对满足车厢间可移动条件的货物,通过贪心策略,将车厢利用率小的车厢内对应货物放入其它车厢。