(19)中华 人民共和国 国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202111585222.0 (22)申请日 2021.12.23 (65)同一申请的已公布的文献号 申请公布号 CN 113962639 A (43)申请公布日 2022.01.21 (73)专利权人 湖北普罗格科技股份有限公司 地址 430000 湖北省武汉市硚口区中山大 道1号硚口金三角A 地块6号楼、 购物中 心6号楼24层1-4号 (72)发明人 周志刚　 (74)专利代理 机构 北京集智东方知识产权代理 有限公司 1 1578 代理人 吴倩　龚建蓉 (51)Int.Cl. G06Q 10/08(2012.01)G06Q 10/04(2012.01) G06F 16/29(2019.01) (56)对比文件 CN 112053117 A,2020.12.08 CN 110645983 A,2020.01.0 3 审查员 张雅琳 (54)发明名称 一种基于全域地图的配送路径规划方法和 系统 (57)摘要 本发明涉及物 流配送技术领域， 具体涉及一 种基于全域地图的配送路径规划方法和系统。 该 方法包括： 格栅化载入的全域地图数据， 生成道 路路网矢量地图； 获取配送中心和各自提点地理 位置坐标， 并匹配到道路路网矢量地图上； 以配 送中心为扩展源向四周扩张直到相遇为止， 划分 形成配送分区区域； 获取待配送订单属性， 对订 单划分配送中心， 并标记单独配送订单位置坐 标； 以配送中心位置为起始坐标点， 以各自提点 及单独配送 订单位置为节点坐标， 计算每条线性 栅格道路途经节点坐标的运载量代价； 基于 Dijkstra算法计算道路路网矢量地 图中配送车 辆最大载货量条件下途经所有节 点的最优路径。 本发明提高了全域地图中各配送中心派件的作 业效率。 权利要求书2页 说明书9页 附图8页 CN 113962639 B 2022.03.08 CN 113962639 B 1.一种基于全域 地图的配送路径规划方法， 其特 征在于， 包括： 载入全域地图数据， 格栅 化全域地图数据， 生成道路 路网矢量 地图； 获取配送中心和各自提 点地理位置坐标， 并匹配到道路 路网矢量 地图上； 以配送中心为扩展源向四周扩 张直到相遇为止， 划分形成道路路网矢量地图上的配送 分区区域； 获取待配送订单属性， 对订单进行聚类， 根据获取的待配送订单属性， 按照待配送订单 的地址对应的位置派单至对应的配送分区区域， 根据对应的配送分区区域将待配送订单划 分至配送中心， 并根据订单属性在道路 路网矢量 地图中标记单独 配送订单位置坐标； 以配送中心位置为起始坐标点， 以各自提点及单独配送订单位置为节点坐标， 计算道 路路网矢量 地图中每条线性 栅格道路途经节点 坐标的运载量代价； 基于Dijkstra算法计算道路路网矢量地图中配送车辆最大载货量条件下途经所有节 点的最优路径。 2.如权利要求1所述的基于全域地图的配送路径规划方法， 其特征在于， 所述格栅化全 域地图数据， 生成道路 路网矢量 地图， 包括： 获取全域 地图数据， 基于所述全域 地图数据读取道路 路网矢量数据； 根据道路 路网矢量数据进行道路 路网规划， 得到道路 路网规划结果； 将道路路网规划结果剖分成连续分布的线性 栅格道路场景模型； 对场景模型的线性栅格道路进行矢量扩展， 确定相邻线性栅格道路的最大配送覆盖范 围； 将矢量扩展后的线性栅格道路场景模型叠置于全域地图的空间向量场中， 建立生成道 路路网矢量 地图。 3.如权利要求2所述的基于全域地图的配送路径规划方法， 其特征在于， 所述确定相邻 线性栅格道路的最大配送 覆盖范围的方法， 包括： 遍历获取的场景模型的线性 栅格道路； 计算所述场景模型中相邻线性 栅格道路 之间的最大间距值； 在最大间距值至最大间距值一半的数值范围内设定所述线性栅格道路矢量扩展的阈 值； 以阈值为矢量扩展标准， 生成线性 栅格道路上最大配送 覆盖范围。 4.如权利要求1所述的基于全域地图的配送路径规划方法， 其特征在于， 划分配送分区 区域的方法为： 获取配送中心地理位置坐标， 并匹配到道路 路网矢量 地图上； 以配送中心地理位置坐标作为扩展源向四周扩 张直到相遇为止， 形成道路路网矢量地 图空间中的Voro noi图； 以每个配送中心所在的Voro noi图区域确定为划分的配送分区 区域。 5.如权利要求4所述的基于全域地 图的配送路径规划方法， 其特征在于， 构建Voronoi 图时， 以相邻两个配送中心地理位置坐标作为两个扩展源， 绘制连接两个扩展源线段的垂 直平分线， 将全域地图中所有配送中心作为扩展源绘制的垂直平分线组合， 形成全域地图 中连续多边形组成的配送分区 区域。 6.如权利要求3所述的基于全域地图的配送路径规划方法， 其特征在于， 所述待配送订权　利　要　求　书 1/2 页 2 CN 113962639 B 2单属性包括待配送 订单的地址、 订单重量、 包裹体积、 自提点代签收许可情况以及订单送达 时限。 7.如权利要求6所述的基于全域地图的配送路径规划方法， 其特征在于， 对订单进行聚 类的方法， 包括： 根据获取的待配送订单属性， 按照待配送订单的地址对应的位置派单至对应的配送分 区区域； 根据待配送订单属性的自提点代签收许可情况， 对许可代签收订单分配至最短距离的 自提点， 并更改道路 路网矢量 地图中许 可代签收订单的位置坐标至自提 点位置； 对不许可代签收订单在道路 路网矢量 地图中标记出 单独配送订单位置坐标； 根据自提点位置及单独配送订单位置所在的最大配送覆盖范围， 匹配对应的线性栅格 道路。 8.如权利要求7所述的基于全域地图的配送路径规划方法， 其特征在于， 所述每条线性 栅格道路途经节点 坐标的运载量代价的计算方法为： 统计每条线性 栅格道路途经节点 坐标的数量以及每 个节点的订单属性信息； 根据订单属性信息计算该 条线性栅格道路上每 个节点的订单重量和包裹体积； 累加该条线性栅格道路上 所有节点的订单重量和包裹体积； 将订单重量总和以及包裹体积总和定义为该条线性栅格道路途经节点坐标的运载量 代价。 9.如权利 要求8所述的基于全域地图的配送路径规划方法， 其特征在于， 基于Dijkstra 算法计算道路 路网矢量 地图中途经 所有节点的最优路径的方法， 包括： 以道路路网矢量 地图中配送中心坐标为 起始点坐标； 以配送车辆最大 载货量为途经节点数量选择依据； 满足配送车辆最大载货量的前提下， 以配送中心起始点坐标为中心向外层层扩展， 直 至扩展到所有待配送节点均对应一条线性栅格道路及配送车辆， 得到道路路网矢量地图中 途经所有节点的最优路径。 10.一种基于全域地图的配送路径规划系统， 其特征在于， 所述基于全域地图的配送路 径规划系统采用权利要求 1‑9中任意一项 所述基于全域地图的配送路径规划方法得到所有 订单配送的最优路径； 所述基于全域 地图的配送路径规划系统包括： 道路路网矢量地图生成模块， 基于载入的全域地图数据进行格栅化处理， 得到道路路 网矢量地图； 订单划分模块， 用于根据订单属性划分至对应的配送分区 区域的配送中心； 运载量代价计算模块， 用于计算每条线性栅格道路途经节点所对应的订单的所需运载 量； 以及 配送路径生成模块， 基于Dijkstra算法计算道路路网矢量地图中配送车辆最大载货量 条件下途经 所有节点的最优路径。权　利　要　求　书 2/2 页 3 CN 113962639 B 3