欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2021116406299
申请人: 湖南科技大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于云边端协同的动态车辆配送路径优化方法,其特征在于,包括以下步骤:S1、对配送车辆路径规划问题进行定性分析,确定配送时间和配送成本为第一阶段路径规划的优化目标;

S2、在根据需求点提出的货物需求量和时间窗约束下,考虑配送中心的配送能力,在车辆出发前,根据第一阶段路径规划的优化目标,使用遗传算法在云端对整体配送路径提前进行优化,得到初始配送路径规划方案,该初始配送路径规划方案的整体花费的配送时间最少,耗费的配送成本最低;

S3、配送车辆出发后,对路况数据进行感应并做出判断,更新初始配送路径规划方案中相应路段的路网信息;

S4、根据动态更新的路网信息以及配送车辆所处的位置,对余下的配送路径进行动态调整,直至全部配送任务结束,计算配送花费的时间;

S5、根据路况变化对路径作出优化调整,更新当前更新后的配送路径所耗费的成本;

S6、以配送中心为车辆出发起始点,以最后一辆配送车辆完成配送任务为截止,在整个配送过程中,按照步骤S4和S5,对整个配送区域内的配送车辆路径进行动态的调整。

2.根据权利要求1所述的基于云边端协同的动态车辆配送路径优化方法,其特征在于,步骤S1中,配送成本为车辆运输成本TC、时间窗惩罚成本PC和车辆成本之和;其中,其中,K为车辆的总数量,N为待访问的需求点总数目,cij为需求点i与需求点j之间的单位运输成本,dij为需求点i与需求点j之间的距离,xijk的取值为0或1,取值为1表示车辆k从需求点i离开后前往需求点j,否则取值为0;a,b为配送时间窗惩罚系数,wik为车辆k在需求点i的等待时间,tik为车辆k到达配送点i的时间,li为需求点i的最晚服务时间窗;x0jk取值为0或1,当其值为1时表示车辆k从配送中心0出发前往需求点j。

3.根据权利要求1所述的基于云边端协同的动态车辆配送路径优化方法,其特征在于,步骤S2的具体实现过程包括:

1)构建惩罚函数p(x):

其中,x代表相应的种群个体编号,T是正数,Du_max表示第u种车型的最大行驶距离;N为待访问的需求点总数目;

2)对所述惩罚函数p(x)进行解码,构造与所述惩罚函数p(x)对应的染色体;

3)根据备件需求数据、路网数据和配送资源,随机产生初始种群;

4)通过选择、交叉和变异算子,在不满足终止条件的情况下对初始种群进行循环进化,直至产生最优解,得到初始配送路径规划方案。

4.根据权利要求1所述的基于云边端协同的动态车辆配送路径优化方法,其特征在于,步骤S3的具体实现过程包括:

A)根据每个边缘结点采集到的路况变化信息计算边缘结点所属路段的通行时间的变化,根据计算的结果,更新各个路段在道路通行时间表中的当前通行时间;

B)根据车辆速度更新配送车辆当前所处的位置,结合将要前往的下一个需求点的位置,得到两个位置之间在初始配送路径规划方案中的行进路线所需要经过的路段,完成对初始配送路径规划方案中相应路段的路网信息的更新;

C)根据所有配送车辆的当前位置及要前往的下一配送位置,查询道路通行时间表,判断发生变化的路况信息是否会对各配送车辆当前的配送任务造成恶劣影响:若车辆即将前往路段变化后的道路通行时间大于原通行时间的N倍,即视为该路况信息的变化对配送任务造成了恶劣影响,进入步骤S4。

5.根据权利要求1所述的基于云边端协同的动态车辆配送路径优化方法,其特征在于,步骤S4的具体实现过程包括:

I)取f(n)值最小的节点作为最优路径上的下一个节点,f(n)=g(n)+h(n),g(n)是起始节点到当前节点实际的通行代价,h(n)是当前节点到终点的通行代价的估计值;

II)对A*算法所维护的P表和Q表进行操作,具体包括:i)P表、Q表置空,将起点S加入P表,其g(n)值置0,父节点为空,路网中其他节点g(n)值置为无穷大;

ii)若P表为空,则算法失败,否则选取P表中f(n)值最小的节点,记为BT,将其加入Q表中;判断BT是否为终点T,若是,转到步骤iii);否则根据路网拓扑属性和交通规则找到BT的每个邻接节点NT,执行以下步骤:

①计算NT的启发值

f(NT)=g(NT)+h(NT);

g(NT)=g(BT)+cost(BT,NT);

其中,cost(BT,NT)是BT到NT的通行代价;

②若NT在P表中,且通过公式g(NT)=g(BT)+cost(BT,NT)计算的通行代价值比NT的通行代价值小,则

将NT的通行代价值更新为g(NT)=g(BT)+cost(BT,NT),并将NT的父节点设为BT;

③如果NT在Q表中,且通过g(NT)=g(BT)+cost(BT,NT)计算的通行代价值比NT的通行代价值小,则将NT的通行代价值更新为g(NT)=g(BT)+cost(BT,NT),将NT的父节点设为BT,并将NT移出到P表中;

④若NT既不在P表,也不在Q表中,则将NT的父节点设为BT,并将NT移到P表中;

⑤返回步骤ii);

iii)从终点T回溯,依次找到父节点,并加入优化路径中,直到起点S,即得出优化路径;

III)计算车辆通过所述优化路径所需的通行时间,优化路径包含多个路段,将多个路段编号为1,2,3,...,k;以[tk,tk′]表示车辆经过路段k的通行时间Tk,则Tk=tk′‑tk;车辆通过多个路段所花费的通行时间与T′k1,T′k2,T′k3...相对应;fk表示车辆经过路段k起点的时刻对应的时段, 利用下式计算车辆通过路段k的通行时间Tk:

m的取值满足如下约束:

ΔT表示时段长度,t0表示开始时刻;

IV)利用下式计算处理路况变化所需花费时间:gn(r)=bn(r)+cn(r)+kn(r)+hn(r);

θn,n′表示数据从车辆Vn传递到车辆Vn′所经过的车辆数;

M表示边缘节点数量,D表示边缘计算设备集合,D={d1,d2,...,dm},V表示车辆集合,V={v1,v2,...,vn},λV2V表示基于V2V方法的数据传输速率,λV2I表示基于V2I方法的数据传输速率,ωn表示被传输计算任务的数据量,vn表示编号为n的配送车辆,dm表示编号为m的边缘计算设备,ln表示计算任务n是否在某边缘计算设备上进行处理,ln取值为0或1,p表示每个边缘计算设备的处理能力,un是计算任务n所请求的资源数量。

V)利用下式计算完成配送任务整体所需时间:K表示编号为r_s的路径所经过的路段总数;R表示至完成配送时,所处理过的由路况变化而对道路通行时间造成恶劣影响的道路事件总数。

6.根据权利要求1所述的基于云边端协同的动态车辆配送路径优化方法,其特征在于,步骤S5的具体实现过程包括:

a)所有配送车辆根据初始路径规划,开始配送;

b)将需要配送的需求点按r*r划分为多个配送区域,并为每个所述配送区域编号,r为单位长度;

c)边缘结点监听道路状况发生的变化,按照时间长度将产生影响路况的事件记录到events列表,events列表中的每个event对通往各配送区域内需求点的道路的通行时间产生不同大小的影响;

d)将对应配送区域内路段的道路通行时间变更为影响后的值;

e)判断当前时间片段内是否需要对原规划路径进行调整;如需调整,按照寻找两点间最短路径的A*算法进行再规划;

f)对其余每个时间片段,重复步骤a)~f),直至完成全部配送任务,即所有车辆将初始规划中所有的需求点都遍历完,并回到配送中心。

7.一种计算机装置,包括存储器、处理器及存储在存储器上的计算机程序;其特征在于,所述处理器执行所述计算机程序,以实现权利要求1~6之一所述方法的步骤。

8.一种计算机程序产品,包括计算机程序/指令;其特征在于,该计算机程序/指令被处理器执行时实现权利要求1~6之一所述方法的步骤。

9.一种计算机可读存储介质,其上存储有计算机程序/指令;其特征在于,所述计算机程序/指令被处理器执行时实现权利要求1~6之一所述方法的步骤。