(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 20221094386 5.6 (22)申请日 2022.08.08 (65)同一申请的已公布的文献号 申请公布号 CN 115018211 A (43)申请公布日 2022.09.06 (73)专利权人 北京建筑大学 地址 100066 北京市西城区展览馆路1号北 京建筑大学 (72)发明人 马晓轩　刘超　郭茂祖　张翰韬　 孙博洋　邓轶博　郝冬　 (74)专利代理 机构 北京中秩新创知识产权代理 有限公司 16124 专利代理师 丁海涛 (51)Int.Cl. G06Q 10/04(2012.01)G06N 3/00(2006.01) G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06F 17/10(2006.01) (56)对比文件 CN 114118597 A,202 2.03.01 CN 112508235 A,2021.0 3.16 CN 112085349 A,2020.12.15 CN 113947310 A,202 2.01.18 WO 2021189720 A1,2021.09.3 0 Zhiwei Yang等.Dynamic vehicle routi ng with time w indows in the theory and practice. 《Spri ngerlink》 .2016,第1-15页. 审查员 卢洁 (54)发明名称 一种运输调度线路 设定方法和装置 (57)摘要 本发明涉及一种运输调度线路设定方法和 装置， 步骤S1： 建立运输调度线路模型： 步骤S2： 利用配置后的蚁群算法求解运输调度线路模型， 获得第一配送线路； 步骤S3： 根据各个车辆到达 沿途各节点的时间和节点对应的订单到达时间 的时间差给规划后的第一配送线路中各配送子 线路打分； 步骤S4： 筛选分数值大于线路分数阈 值的配送子线路， 构成第二配送线路集； 步骤S4： 对第二配送线路集中各配送子线路执行线路自 搜索， 构成第三配送线路集； 步骤S4： 对第三配送 线路集执行车辆间线路搜索， 获得最优配送线 路。 本发明能够在保证获得最优线路的同时降低 运算量， 考虑订单到达时间对需求拆分的影响， 提高了方法的适用性。 权利要求书3页 说明书11页 附图1页 CN 115018211 B 2022.11.01 CN 115018211 B 1.一种运输调度线路设定方法， 其特 征在于， 所述 运输调度线路设定方法具体包括： 步骤S1： 建立 运输调度线路模型； 步骤S2： 根据订单信息配置蚁群算法， 利用配置后的蚁群算法求解运输调度线路模型， 获得第一配送线路； 其中， 所述配置后的蚁群算法包括配置后的线路信息素 更新方式， 所述配置后的线路信息素更新方式根据订单到达时间计算增量调整因子 ， ， Ti是节点i的订单到达 时间， Tj是节点j的订单到达时间， 为时间差阈值， 利用 增量调整因子与信息素的变化 量的乘积调整信息素的变化 量； 步骤S3： 预估第一配送线路各个车辆到达沿途各节点的时间， 根据各个车辆到达沿途 各节点的时间和节点对应的订单到达时间的时间差给规划后的第一配送线路中各配送子 线路打分； 将分数值大于线路分数阈值的配送子线路作为第二配送线路集； 步骤S4： 对第 二配送线路集中各配送子线路执行线路自搜索， 构成第三配送线路集， 线 路自搜索为两 两交换一条配送子线路上的客户以优化线路； 步骤S5： 对第 三配送线路集执行车辆间线路搜索， 获得最优配送线路， 车辆间线路搜索 为两两交换不同车辆的客户以优化线路。 2.根据权利要求1所述的运输调度线路设定方法， 其特 征在于， 所述 步骤S2具体包括： 根据订单信息配置蚁群算法还包括根据订单信息配置初始节点选择方式和状态转移 规则， 订单信息包括各个订单的订单到 达时间。 3.根据权利要求2所述的运输调度线路设定方法， 其特征在于， 利用配置后的蚁群算法 求解运输调度线路模型， 具体包括： 步骤S201： 初始化 参数， 选择待满足需求的第一节点； 步骤S202： 规划第一节点的车辆； 步骤S203： 判断车辆到达第一节点时是否还存在待满足需求的节点， 若存在， 根据配置 后的状态 转移规则选择下一节点作为最新的第一节点， 返回步骤S202， 若不存在， 记录规划 完成的子线路， 修改蚂蚁寻路状态为已寻路， 执 行步骤S204； 步骤S204： 判断已寻路状态的蚂蚁数量是否小于寻路阈值， 若是， 则重置客户需求量为 初始状态， 返回步骤S202， 否则， 执 行步骤S20 5； 步骤S205： 多个蚂蚁寻路获得的多个子线路构成子线路集合， 从子线路集合中选择线 路最短的子线路， 根据配置后的线路信息素 更新方式更新子线路信息素； 步骤S206： 判断是否满足迭代终止条件， 若满足， 完成本次运输调度线路规划， 获得第 一配送线路； 若不满足， 重置客户需求量为初始状态， 重置蚂蚁寻路状态为未寻路， 返回步 骤S202。 4.根据权利要求3所述的运输调度线路设定方法， 其特征在于， 选择待满足需求的第 一 节点， 具体包括： 将所有车辆放置 于车场中， 在t时刻， 车辆k可能选择的初始客户节点 为j， 选择公式为：           (11)权　利　要　求　书 1/3 页 2 CN 115018211 B 2其中，  表示t时刻由车场0到客户节点y构成的边(0,y)上的信息素含量， Kp表示客 户节点集合，  表示t时刻由车场0到可能选择的初始客户节点j构成的边(0,j)上的信 息素含量， 表示车辆k初始客户选择节点j的概率， kj为初始节点选择干预因子， ， 其中t为当前算法运行时刻， 为初始阶段时间阈值， 为节点j对应的订 单到达时间， 根据订单到达时间将各个订单排序， 为订单到达时间位于中间位置订单对 应的订单到 达时间； q是一个在(0,1)区间的随机值， q0是初始选择阈值。 5.根据权利要求3所述的运输调度线路设定方法， 其特征在于， 规划第 一节点的车辆具 体包括： 步骤A1： 若当前的第一节点的客户需求量不大于车辆承载量， 则将第一节点加入线 路中， 更新车辆承载量， 第一节点的车辆规划完毕； 否则， 以当前 的第一节点的客户需求量 和车辆承载量的差值更新第一节点的客户需求量， 将第一节 点加入线路， 派出一辆新车， 返 回步骤A1。 6.根据权利要求3所述的运输调度线路设定方法， 其特征在于， 车辆k在t时正好处于客 户节点i， 下一个可能的客户节点 为j， 配置后的状态转移规则具体为：   (12) 其中， 表示车辆k在i节点之后下一客户选择节点j的概率， 表示节点i和y之间的 信息素含量干预因子， 表示节点i和j之间的信息素含量干预因子， 节点A和B之间的信息 素含量干预因子计 算方式为： ， TA是节点A的订 单到达时间， TB是节点B的订单到 达时间， 为时间差阈值，  表示t时刻 边(i,y)上的信息素含量， 表示节点i和y的 启发式信息，  表示t时刻边(i,j)上的信息素含量， 表示节点i和j的启发式信 息， α 为信 息素浓度因子， 为预期启发式因子， Kp表示客户节点集合， q是一个在(0,1)区间 的随机值， q1是中间选择阈值。 7.根据权利要求3所述的运输调度线路设定方法， 其特征在于， 根据配置后的线路信 息 素更新方式更新子线路信息素， 具体为：            (13)                   (14) 其中， 为更新后的子线路信息素， 为当前子线路信息素， 为子线路信 息素增量， ib表示本轮迭代最优解决方案， Cib表示本轮迭代最短线路的距离， ρ 为信 息素挥 发因子， 取值范围为(0,1)， Z为常数， 代 表蚂蚁携带的信息素总量。 8.根据权利要求1所述的运输调度线路设定方法， 其特 征在于， 所述 步骤S3具体为： 获取第一配送线路各个节点对应的订单到达时间 ， i=1,2,…,I， I为车辆总数， j=1, 2,…,Wi， Wi为车辆i的配送线路上节点总数， 预估第一配送线路各个车辆到达沿途各节点的权　利　要　求　书 2/3 页 3 CN 115018211 B 3