(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111623565.1 (22)申请日 2021.12.28 (71)申请人 扬州青商欣环境科技有限公司 地址 225125 江苏省扬州市邗江区扬州环 保科技产业园创业路8号 申请人 扬州大学 (72)发明人 丁永峰　田芳芳　邓社军　李晟　 于世军　嵇涛　张俊　陆曹烨　 朱俊豪　管恩丞　施议　彭浪　 宇泓儒　周鹏　王晓莹　李婷婷　 窦玥　刘根基　姚炎宏　张海旻　 徐成　郦红艺　 (74)专利代理 机构 南京苏高专利商标事务所 (普通合伙) 32204 代理人 柏尚春(51)Int.Cl. G06Q 10/06(2012.01) G06F 30/20(2020.01) G06F 17/18(2006.01) G06K 9/62(2022.01) G06F 111/06(2020.01) (54)发明名称 一种基于遗传算法的城市生活垃圾收运车 辆调度方法 (57)摘要 本发明公开了一种基于遗传算法的城市生 活垃圾收运车辆调度方法， 通过信息化手段来采 集服务区域内基础数据集； 根据历史垃圾量数 据， 计算每日不同类型垃圾量平均值， 对未来每 日不同类型的垃圾量进行预测； 对区域内不同垃 圾收集点进行定位并根据K ‑means聚类算法的思 想， 实现对垃圾收集点的聚类分区； 对影响城市 生活垃圾分类收运的目标和限制条件进行定性 分析， 以收运环节作为研究对象采用VRP， 以成本 最小化为目标建立垃圾逆向物 流网络规划模型； 利用遗传算法对垃圾逆向物流网络优化模型进 行求解， 计算车辆的最少配置数量和车辆路径， 形成垃圾收运车辆调度方案。 本发 明智能化分析 范围内大量垃圾收集点的收运车辆最优配置及 线路。 权利要求书2页 说明书5页 附图4页 CN 114386792 A 2022.04.22 CN 114386792 A 1.一种基于 遗传算法的城市生活垃圾收运车辆调度方法， 其特 征在于， 包括以下步骤： (1)通过信息化手段来采集 服务区域内基础数据集； (2)根据历史垃圾量数据， 计算每日不同类型垃圾量平均值， 对未来每日不同类型的垃 圾量进行预测； (3)对区域 内不同垃圾收集点进行定位并根据K ‑means聚类算法的思想， 实现对垃圾收 集点的聚类分区； (4)对影响城市生活垃圾分类收运的目标和限制条件进行定性分析， 以收运环节作为 研究对象采用VRP， 以成本最小化 为目标建立垃圾逆向物流网络规划模型； (5)利用遗传算法对垃圾逆向物流网络优化模型进行求解， 计算车辆的最少配置数量 和车辆路径， 形成垃圾收运车辆调度方案 。 2.根据权利要求1所述的基于遗传算法的城市生活垃圾收运车辆调度方法， 其特征在 于， 步骤(1)所述基础数据集包括垃圾分类的类别、 每日不同类型垃圾数量、 每日垃圾总量、 收运车辆类型、 收运车辆油耗、 收运车辆数量、 不同类型收运车辆配备员工数、 收运车辆载 重、 收运车辆 轨迹数据。 3.根据权利要求1所述的基于遗传算法的城市生活垃圾收运车辆调度方法， 其特征在 于， 步骤(4)所述成本为 运输成本和车辆固定成本之和。 4.根据权利要求1所述的基于遗传算法的城市生活垃圾收运车辆调度方法， 其特征在 于， 所述步骤(4)包括以下步骤： (41)设定N为垃圾收集点集合， 其中N＝0表示起点， K为收运车辆集合， S为某一车辆访 问收集点集合， 根据该数学表征设定模型参数， 设定车辆最大载重量为P， 设定收集点i和j 之间的距离为dij， 设定车辆k单位距离运输成本为ck， 设定车辆k固定成本为c0； (42)设定垃圾收运 服务区域内部最少收运车辆配置数为mi n n； (4 3) 设 定 每 个收 集 点 只能 被 一 辆 车 服 务 且 只能 访问 一次 ， 根 据公 式 ： 和 进行约束； (44)设定除起点和 终点的每个收集点， 进入和驶出每一收集点的车辆数相等， 收运车 辆进入某一收集点也必须从该点离开， 根据公式： 进行流量守恒约束； (45)设定每辆车都从垃圾车辆集中点出发并且服务完后必须返回垃圾车辆集中点， 根 据公式 和 进行约束； (46)设定收运车辆容量限制， 确保每辆车的载重量不能超过车辆限制， 根据公式 进行约束； (47)对xijk和yijk为0‑1整数决策变量进行定义： 权　利　要　求　书 1/2 页 2 CN 114386792 A 25.根据权利要求1所述的基于遗传算法的城市生活垃圾收运车辆调度方法， 其特征在 于， 所述步骤(5)包括以下步骤： (51)染色体编码机制与初始化种群： 假设垃圾收集中心从N个垃圾收集点收取垃圾， 那 么依次对垃圾收集点进行编号， 编号从1到N； 所有编号不同的排列顺序均可看成不同的染 色体， 每条染色体表示这个垃圾回收站对垃圾收集点进行收集的先后顺序， 同时每个垃圾 收集点都有自己的一个附带属性， 即垃圾 量； (52)适应度函数： 生成初始化种群后， 对每条染色体进行适应度函数计算； 对垃圾收集 中心而言， 收集完所有垃圾收集点的垃圾所行驶的总距离越小适应度越大； 针对垃圾逆向 物流网络优化模型， 定义x的适应度函数： F(x)＝Cmax‑f(x) 式中， f(x)为个体x对应的目标函数值,F(x)是所得的相对适应度， Cmax为F(x)的最大估 计， F(x)值越大表示个 体越优秀， 即行驶距离越小； 在计算适应度函数的同时， 也对染色体进行解码， 实现了将染色体转换为车辆路径方 案； 模型中对车辆的最大 载重量存在约束， 在满足约束条件下对路径进行划分； (53)交叉算子： 采用顺序交叉算法在两条路径之间交换垃圾收集点， 改变其位置生成 新的服务路线， 增大了该问题解的搜索范围， 提高了种群的多样性； (54)变异算子： 采用双插入法， 在一条染色体中， 依次将两个连续的基因提取出来， 插 入到染色体的其他位置， 每插入一个位置要记录解并与原解作比较， 如果当前解要优于原 来的解， 那么将替换原解； 考虑解是闭合 曲线， 为避免重复， 基因插入的位置避开首基因的 前一个位置和尾 基因的后一个位置； (55)根据得到的最优垃圾收运的有序 序列还原最优垃圾收运 顺序， 结束。 6.根据权利要求5所述的基于遗传算法的城市生活垃圾收运车辆调度方法， 其特征在 于， 所述步骤(53)包括以下步骤： (531)在初始种群中随机选择两条父代染色体P1,P2， 即两种对垃圾收集点进行垃圾收 集的服务顺序； 染色体中单个基因代表单个垃圾收集点， 基因片段代表多个有服务顺序的 垃圾收集 点集合； (532)在P1,P2中随机 选取相同位置的基因片段， 分别记为c hangel和c hange2； (533)先找出change  1在P2中的位置， 再将change  l放入P2中相同的位置， 并删除P2中 与change l相同的基因； (534)先找出change  2在P1中的位置， 再将change  2放入P1中相同的位置， 并删除P1中 与change 2相同的基因， 交叉操作完成生成子代C1、 C2。权　利　要　求　书 2/2 页 3 CN 114386792 A 3