(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111640629.9 (22)申请日 2021.12.2 9 (71)申请人 湖南科技大 学 地址 411201 湖南省湘潭市雨湖区石码头2 号 (72)发明人 李天才　文一凭　 (74)专利代理 机构 长沙正奇专利事务所有限责 任公司 431 13 代理人 王娟 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06N 3/12(2006.01) (54)发明名称 基于云边端协同的动态车辆配送路径优化 方法及装置 (57)摘要 本发明公开了一种基于云边端协同的动态 车辆配送路径优化方法及装置， 涉及备品备件物 流配送领域。 根据各个需求位置的备品备件请求 以及企业的配送资源， 在配送 开始前使用遗传算 法， 按照配送的时效、 总体所耗费的成本等优化 目标， 对全部的配送需求做出相应的路径规划。 通过在道路边缘的边缘计算设备， 可以实时地对 道路状况进行监听， 并判断出当前路段的通行时 间是否会大幅度发生变化。 本发 明方法采用在边 缘端对路况变化进行处理， 并根据实际情况， 采 用动态通行时间表和改进的A *算法， 实时地优化 调整车辆剩余配送任务的配送路径。 权利要求书3页 说明书10页 附图2页 CN 114399095 A 2022.04.26 CN 114399095 A 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)根据车辆速度更新配送车辆当前所处的位置， 结合将要前往的下一个需求点的位权　利　要　求　书 1/3 页 2 CN 114399095 A 2置， 得到两个位置之间在初始配送路径规划方案中的行进路线所需要经过的路段， 完成对 初始配送路径规划方案中相应路段的路网信息的更新； 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表 中； 判断B T是否为终点T， 若 是， 转到步骤iii)； 否则根据路网拓扑属性和交通规则找到B T的 每个邻接节点 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)+co st(BT， NT)， 将NT的父节点设为BT， 并将NT移出到P表中； ④若NT既不在P表， 也 不在Q表中， 则将NT的父节点设为BT， 并将NT移到P表中； ⑤返回步骤i i)； 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的取值满足如下约束： 权　利　要　求　书 2/3 页 3 CN 114399095 A 3