(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210898652.6 (22)申请日 2022.07.28 (65)同一申请的已公布的文献号 申请公布号 CN 115062868 A (43)申请公布日 2022.09.16 (73)专利权人 北京建筑大学 地址 100066 北京市西城区展览馆路1号北 京建筑大学 (72)发明人 马晓轩　刘超　郭茂祖　李志文　 孙博洋　邓轶博　郝冬　 (74)专利代理 机构 北京中秩新创知识产权代理 有限公司 16124 专利代理师 丁海涛 (51)Int.Cl. G06Q 10/04(2012.01)G06Q 10/08(2012.01) G06K 9/62(2022.01) G06N 3/00(2006.01) G01C 21/34(2006.01) 审查员 林炜威 (54)发明名称 一种预聚类的车辆配送路径规划方法和装 置 (57)摘要 本发明涉及一种预聚类的车辆配送路径规 划方法和装置， 具体包括步骤S1： 客户订单预聚 类； 步骤S2： 建立模型： 从步骤S1中获得的多个客 户类中选 择一个未规划车辆配送路径的客户类， 建立客户类对应的车辆配送路径模型； 步骤S3： 模型最优求解： 求解车辆配送路径模型， 获得当 前客户类的最优路径； 步骤S4： 循环判断。 本发明 在规划路径之前预先对客户订单进行聚类， 基于 订单到达时间的预聚类方式在规划路径的同时 保障订单的正常配送， 满足实际配送的需求， 路 径规划过程兼顾了全局搜索能力和收敛速度。 权利要求书3页 说明书11页 附图1页 CN 115062868 B 2022.11.11 CN 115062868 B 1.一种预聚类的车辆配送路径规划方法， 其特征在于， 所述预聚类的车辆配送路径规 划方法具体包括： 步骤S1： 客户订单预聚类： 获取订单数量和各订单对应的客户的订单到达时间信息， 基 于订单数量和客户的订单到 达时间信息进行 预聚类， 获得多个客户类； 其中， 步骤S1具体包括： 步骤S101： 获取订单数量和订单到达时间跨度， 所述订单到达时间跨度是最早订单到 达时间和最晚订单到 达时间之间的时间差； 步骤S102： 根据订单数量和订单到达时间跨度确定聚类个数， ， 其中， T为订单到达时间跨度， 为第一时差阈值， Nmount为车场收到的订单总数， N1为第一订单总 量阈值， a为第一 倍率系数， n1为聚类基数； 步骤S103， 根据聚类 个数确定各个订单的订单权 重； 步骤S104， 利用k ‑means算法获得多个客户类； 步骤S2： 建立模型： 从步骤S1中获得的多个客户类中选择一个未规划车辆配送路径的 客户类， 建立 客户类对应的车辆配送路径模型； 步骤S3： 模型最优求解： 求解车辆配送路径模型， 获得当前客户类的最优路径， 其中， 所 述模型最优求 解采用蚁群算法； 步骤S4： 循环判断： 判断步骤S1获得的多个客户类中是否存在未规划车辆配送路径的 客户类， 若存在， 返回步骤S2， 否则， 完成所有客户订单的车辆配送路径规划。 2.根据权利要求1所述的预聚类的车辆配送路径规划方法， 其特征在于， 所述根据聚类 个数确定各个订单的订单权 重， 具体为： 根据聚类个数和订单到达时间跨度计算订单区间值： ， 其中，△t为订单区间 值， 为四舍五入的函数符号； 根据订单区间值划分订单区间， 设置订单区间中第一订单类型的订单权重为p1， 第二订 单类型的订单权 重为p2。 3.根据权利要求2所述的预聚类的车辆配送路径规划方法， 其特征在于， 所述第 一订单 类型具体为订单区间中订单到达时间点最靠近订单区间中间时间的订单， 第二订单类型具 体为订单区间内除第一 订单类型外的其 他订单。 4.根据权利要求1所述的预聚类的车辆配送路径规划方法， 其特征在于， 所述步骤S2具 体包括： 目标函数为车辆运输成本最小：                       (1)， 其中， z表示车辆总配送路径， M为完成任务需要的最小车辆数， 其取值如式 （2） 所示：                       (2)， N表示当前客户类的订单数量， i、 j分别表示第i、 j节点， m表示第m条线 路， dij为集合V内 任意两点i， j间的距离， V是综合集合， 包括配送中心和客户订单集合Vc = {1,2,…,N}；权　利　要　求　书 1/3 页 2 CN 115062868 B 2为第i、 j节点间路径m的决策变量：           (3)， qi为节点i代表的客户的需求 量； Q为车辆的最大承载量； 约束条件为： s. t.           (4)                        (5)                        (6)            (7)                  (8)              (9)   (10) 其中 、 分别表示节点i、 k之间和节点k、 j之间路径m的决策变量， 表示在第 m 条路线中满足节点i代表的客户的需求量， Sm表示第m条 路线中服务的客户集合； |Sm|表示集 合S中包含的元素个数。 5.根据权利要求1所述的预聚类的车辆配送路径规划方法， 其特征在于， 所述步骤S3具 体包括： 步骤S301： 初始化 参数， 从当前客户类中选择待满足需求的第一节点； 步骤S302： 规划第一节点的车辆； 步骤S303： 判断车辆到达第一节点时是否还存在待满足需求的节点， 若存在， 根据状态 转移规则选择下一节点作为最新的第一节点， 返回步骤S302， 若不存在， 记录规划完成的子 路径， 修改蚂蚁寻路状态为已寻路， 执 行步骤S3 04； 步骤S304： 判断已寻路状态的蚂蚁数量是否小于寻路阈值， 若是， 则重置客户需求量为 初始状态， 返回步骤S3 02， 否则， 执 行步骤S3 05； 步骤S305： 多个蚂蚁寻路获得的多个子路径构成子路径集合， 从子路径集合中选择路 径最短的子路径， 更新子路径信息素； 步骤S306： 判断是否满足迭代终止条件， 若满足， 完成车辆配送路径规划； 若不满足， 重 置客户需求量为初始状态， 重置蚂蚁寻路状态为未寻路， 调整节点选择干预 因子， 返回步骤 S302。 6.根据权利要求5所述的预聚类的车辆配送路径规划方法， 其特征在于， 所述从当前客 户类中选择待满足需求的第一节点具体包括： 将所有车辆放置 于车场中， 在t时刻， 车辆k选择的初始客户节点 为j， 选择公式为：           (11)权　利　要　求　书 2/3 页 3 CN 115062868 B 3