(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111623564.7 (22)申请日 2021.12.28 (71)申请人 扬州大学 地址 225009 江苏省扬州市大 学南路88号 (72)发明人 邓社军　于世军　丁永峰　嵇涛　 张俊　陆曹烨　施议　彭浪　 朱俊豪　管恩丞　宇泓儒　周鹏　 王晓莹　李婷婷　窦玥　刘根基　 姚炎宏　张海旻　徐成　郦红艺　 (74)专利代理 机构 南京苏高专利商标事务所 (普通合伙) 32204 代理人 柏尚春 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01)G06K 9/62(2022.01) G06Q 50/30(2012.01) (54)发明名称 一种基于城市生活垃圾分类的收运车辆调 度方法及系统 (57)摘要 本发明公开了一种基于城市生活垃圾分类 的收运车辆调度方法及系统， 对服务区域内历史 垃圾量进行统计， 对每日不同类型的垃圾量进行 预测； 利用K ‑means聚类算法对整个区域内的垃 圾收集点进行聚类并分为多个区域； 对工作区域 内不同类型车辆的工作耗时和运行耗时进行统 计； 对车辆的配置数量和路径进行规划分析， 计 算收运车辆的最少配置数量和车辆路径； 将车辆 配置及路径规划后车辆需要行驶的时间与历史 收运时间进行对比， 分析收运车辆配置及路径规 划分析子模块分析不同规划路径的有效率， 根据 路径有效率判定区域内车辆收运最优路径。 本发 明以精细化测算区域内垃圾收运车辆运输成本， 智能化分析范围内大量垃圾收集点的收运车辆 最优配置及线路。 权利要求书4页 说明书8页 附图1页 CN 114330874 A 2022.04.12 CN 114330874 A 1.一种基于城市生活垃圾分类的收运车辆调度方法， 其特 征在于， 包括以下步骤： (1)对服务区域内历史垃圾量进行统计， 对每日易腐垃圾、 可回收垃圾、 有害垃圾和其 他垃圾四种不同类型的垃圾 量进行预测； (2)利用K ‑means聚类算法对整个区域内的垃圾收集 点进行聚类并分为多个区域； (3)对工作区域内不同类型 车辆的工作耗时和运行耗时进行统计； (4)对车辆的配置数量和路径进行规划分析， 计算收运车辆的最少配置数量和车辆路 径； (5)将车辆配置及路径规划后车辆需要行驶的时间与历史收运时间进行对比， 分析收 运车辆配置及路径规划分析子模块分析不同规划路径的有效率， 根据路径有效率判定区域 内车辆收运 最优路径， 形成调度方案 。 2.根据权利要求1所述的基于城市生活垃圾分类的收运车辆调度方法， 其特征在于， 所 述步骤(2)实现过程如下： 假设有N个分散不均的垃圾收集点， 在其中随机选择k个点作为初始聚类中心点， 计算 并记录剩余点到k个初始中心点的距离， 选择最小的距离将归类到相应的初始中心点的类 中， 再计算每个类中的平均值并更新初始中心 点， 直到聚类准则函数收敛停止更新， 最 终将 区域内所有垃圾收集 点分为k个区域。 3.根据权利要求1所述的基于城市生活垃圾分类的收运车辆调度方法， 其特征在于， 所 述步骤(3)实现过程如下： 对首次测算的工作耗时时间进行标记， 测算收运车辆在路段行驶的耗时时间， 对二次 测算的运行耗时时间进行标记， 将标记的每一次收运车辆工作耗时和运行耗时时间进 行对 比， 设置运行耗时时间对比值为(0,tn]， 当每一收运车辆工作耗时和运行耗时时间之差大 于等于tn， 则进行重新测算， 将重新测算的数据进行分析满足对比值阈值后 进行标记， 将标 记数据发送垃圾收运车辆配置及最优路径分析模块。 4.根据权利要求1所述的基于城市生活垃圾分类的收运车辆调度方法， 其特征在于， 所 述步骤(4)包括以下步骤： (41)设定当前分析的收运车辆最少配置数量和车辆路径采用算法进行条件约束， N为 垃圾收集点集合， 其中N＝0表示起点， K为 收运车辆集合， S为某一车辆访问收集点集合， 根 据该数学表征设定模型参数， 设定车辆最大载重量为Q， 设定收集点i和j之间的距离为dij， 设定车辆k单位距离运输成本为ck， 设定车辆k固定成本为 fk， 设定到达收集点i的左时间窗 为ai， 设定到达收集点i的右时间窗为bi， 设定收集 点i的时间窗宽度为 wik； (42)设定垃圾收运 服务区域内部最少收运车辆配置数为mi n n； (4 3) 设 定 每 个收 集 点 只能 被 一 辆 车 服 务 且 只能 访问 一次 ， 根 据公 式 ： 和 进行约束； (44)设定除起点和 终点的每个收集点， 进入和驶出每一收集点的车辆数相等， 收运车 辆进入某一收集点也必须从该点离开， 根据公式： 进 行流量守恒约束； (45)设定每辆车都从垃圾车辆集中点出发并且服务完后必须返回垃圾车辆集中点， 根 据公式 和 进行约束；权　利　要　求　书 1/4 页 2 CN 114330874 A 2(46)对所有收运车辆到达每个收集点起始时刻和离开每个收集点终止时刻进行定义， 其中， 根据公式： 对所有收运车辆在每 个收集点最早达到时间和最晚离开时间进行约束； (47)设定收运车辆容量限制， 确保每辆车的载重量不能超过车辆限制， 根据公式 进行约束； (48)对xijk和yijk为0‑1整数决策变量进行定义： 5.根据权利要求1所述的基于城市生活垃圾分类的收运车辆调度方法， 其特征在于， 所 述步骤(5)包括以下步骤： (51)状态转移规则： 在蚁群算法中， 每只蚂 蚁在寻找最优路径的过程时， 根据路径上残 留的信息素量， 以及从点i转移到点j的启发式信息η， 独立选择下一个访问点； 在状态转移 概率中综合考虑车辆访问收集点的时间窗吻合度、 车辆容量约束以及车辆容量利用率； 状 态转移规则公式为： 其中， l表示所有可能的取值； τij表示边(i， j)上的信息素浓度， 也就是边(i， j)的轨迹 强度； α( α ≥0)为信息启发式因子， 表示信息素的相 对重要性， 其值越大蚂蚁则越倾向于选 择较多蚂蚁走 过的路径； ηij表示边(i， j)上的启发信息素： ηij＝1/dij 其中， dij为点i到j的距离； β( β ≥0)为期望的启发式因子， 表示能见度的相对重要性， 其 值越大则越倾向于 选择距离较短的路径； kij表示车辆的容 量利用率： kij＝(qi+qj)/Q 其中， λ( λ ≥0)为车辆容 量利用率的相对重要性； εij为时间窗吻合 值： εij＝1/(|si‑ei|+|si+li|) 其中， si表示车辆到达收集点i的时间； θ( θ ≥0)为时间吻合的相对重要 性； p为一个在区 间[0， 1]内的随机数； p0为一个算法参数固定值， 其取值范围为(0， 1)； 当收集点i与j之间的信息素浓度越大、 距离越短、 车辆的容量利用率越大、 时间窗吻合 度越高， 它 们的乘积所占比重就越大， 因此选择收集 点j的概率也越大； (52)信息素更新规则： 蚂 蚁每走完一次周游后， 会对路径上的信息素进行更新； 信息素 浓度更新采用全局更新策略， 在所有蚂蚁构造出路径之后， 对所有生成的可行路径以及在 成本费用最小的路径上注入额外的信息素， 更新公式如下： 权　利　要　求　书 2/4 页 3 CN 114330874 A 3