|
中南大学第四届数学建模竞赛 题目： 城市生活垃圾管理问题研究 【摘 要】 本文主要建立了灰色预测模型、多元线性回归预测模型和TSP最短路线模型、动态规划模型分别解决了城市生活垃圾产量的预测问题和垃圾收运路线优化问题。 问题一 1、搜集统计上海市1998-2007年的垃圾产量及相关数据，初步建立灰色预测模型GM(1,1)对上海市各年的垃圾产量进行预测。 2、在对灰色预测模型的分析和评价后，运用灰色关联分析筛选影响垃圾产量的各主要因素，建立精度更高的多元线性回归预测模型，对垃圾产量进行预测，并分析模型的准确性和实用性。 主要结论： 1、多元线性回归预测模型的最大相对误差为8.08% ，平均相对误差为3.28%，相比灰色预测模型精度有了较大的提高，具有较高的准确性和实用性。 2、多元线性回归预测模型如下： Y=3053.5-2.6xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21674.png-0.6xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17461.png-10.7xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10028.png+10.5xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26161.png 问题二 1、对垃圾收运的相关数据进行统计分析，并将所有收集点划分成三个区域，将问题简化成多个最短路线问题和动态规划问题。 2、通过遗传算法和MATLAB编程实现对模型的求解，初步选出11条收运路线。 3、运用2-OPT方法对所选路线进行优化。 4、根据题目所给约束条件对最小车辆数进行讨论。 5、对模型的适用性和算法的稳定性、鲁棒性进行分析。 主要结论： 1、优化后的垃圾收运路线总路程为S=4247998 (feet) 2、最小车辆数为 k=3 3、经过分析，模型对大区域、复杂的垃圾收运系统的计算求解具有较好的适用性，遗传算法在交配代数为100时，具有较好的稳定性和鲁棒性。 关键词：GM（1,1） 多元线性回归 遗传算法 动态规划 2-OPT 一、问题重述 随着人类生产和生活的不断发展，由此而产生的垃圾对生态环境及人类生存带来极大的威胁，成为重要的社会问题。城市生活垃圾的年增长速度达8-10%，严重污染环境。城市垃圾管理包括计划、组织、行政、金融、法律和工程等多方面，并涉及到城市生活垃圾收集、运输和处置。 一般认为，城市生活垃圾的影响因素包括地理位置、人口、经济发展水平（生产总值）、居民收入以及消费水平、居民家庭能源结构等等。城市生活垃圾产量是垃圾管理系统的关键参数，因此对未来某段时间内垃圾产量的准确预测是相关垃圾管理的部门做出管理规划的前提。 另外，城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收集与运输，这一过程称为城市垃圾的收运。收运过程可简述如下： 某城市有多个行政区，每个区内均有一个车库，假设某一车库拥有最大装载量为 w 的垃圾收集车 k 辆，并且该区的垃圾收集点（待收集垃圾的点）有 n个，该城市共有垃圾中转站 p 座。每天 k 辆垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。以上收运过程均在各点的工作区间之内完成。（注：必须在收集点的工作区间之内，垃圾车才能在该点收集垃圾。） 问题1. 查阅相关文献，搜集垃圾产量数据，在此基础上建立城市生活垃圾产量中短期预测模型，并且分析模型的准确性和实用性。 问题2. 在收运过程已知下述（1）（2）（3）（4）等条件下，设计模型与算法安排垃圾收运车的收运路线，使在垃圾收运车的行车里程尽可能的少。并且对模型的适用性、算法的稳定性和鲁棒性做出分析。 （1）车库和收集点、收集点与中转站、中转站与车库的距离； （2）各收集点每天的垃圾产量； （3）每辆垃圾收运车的最大载荷； （4）垃圾收集点、车库、中转站的工作区间[a,b]。 二、模型假设 1、假设不考虑预测城市未来发生重大灾害事故等对产生垃圾量的影响 2、假设垃圾收运车辆的数量k不限 3、假设每个收集点只有唯一的垃圾车进行收运，即不经过重复的收集点 4、假设每条收运路线均达到车辆最大荷载 5、假设城市交通状况良好，不存在堵车、交通事故的情况 6、假设不考虑垃圾车同时进入车库或中转站时的排队问题 三、符号约定 问题一主要变量： Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-15190.png={ Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26493.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31152.png，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29388.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23884.png，…，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11651.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-6693.png}：原始非负时间序列 Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22298.png={ Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1946.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-12335.png，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30624.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20332.png，…，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10398.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31351.png}：生成序列 xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-12049.png={xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2945.png, xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23915.png，… ，xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28720.png} : 影响垃圾产量因子集 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9159.png：关联系数 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29945.png：第j个变量对第i个变量的关联度 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28269.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26660.png，…，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-311.png：回归系数 R：复相关系数 问题二主要变量： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14860.png：收集点集 dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-32593.png：从节点i到节点j的距离 Ｖ ：某区内所有垃圾收集点集 ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11364.png：第k个断点的序号 sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2553.png：k阶段的状态，等于断点的序号 Qfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28796.png：垃圾收运车容量 ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30239.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21728.png,dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22547.png) ：路线k在收集点sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25800.png断开后经过dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23977.png个收集点的路程函数 dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-12340.png ：路线k中集中点的数量 四、模型一的建立 4.1问题一分析 城市垃圾系统是一个部分信息已知，部分信息未知的灰系统，垃圾本身的不确定性、分散性、使城市垃圾的数据符合灰色数据特征，因此可采用灰色系统理论中的数列灰预测，建立灰色系统预测模型利用上海市近十年的垃圾产量对模型进行预测检验。针对灰色系统存在的缺陷进行改进，综合考虑影响垃圾产量的内在因素，运用灰色关联分析把主要因子从众多因素中找出来，通过主要因子对城市生活垃圾产生量的影响多元线性回归分析，最终建立精度较高的多元线性回归预测模型。 4.2.1灰色系统预测模型 灰色系统GM(1，1)预测模型是一种常用的灰色模型，用于单个时间序列的预测，它通过对原始数据作累加处理后，由于有了较强规律的生成数据列，建立微分方程模型，具体过程如下：设有原始非负时间序列Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29306.png={ Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27043.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-18217.png，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11973.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23510.png，…，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-15268.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28454.png}，对Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1037.png进行一次累加生成，得到生成序列Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-32390.png={ Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19775.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10647.png，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29235.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-6628.png，…，Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-3828.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22859.png} 其中：Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29663.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-5322.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1990.png，i=1,2,…，n 利用数列Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30344.png建立白化微分方程: file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14412.png 利用最小二乘法求参数a，u file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22869.png 其中：b=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20975.png Yfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26867.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9631.png Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7656.png的灰色预测模型为: file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20434.png,k=0,1,2,… 对file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14511.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21879.png作一次累减生成，即得Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16244.png的灰色预测模型为 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11569.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23241.png(1) file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16325.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4343.png,k=1,2,… 为了判断模型的优劣，还应进行模型精度检验，精度检验一般有残差检验、关联度检验和后验差检验等三种方式，若通过检验，则可利用所建立的模型进行预测，否则应进行残差修正。 4.2.2模型求解 运用MATLAB编程实现（程序见附录1.1），对上海98~ 07年的垃圾产量进行预测，结果如下： 表 1 GM（1，1）预测结果 由上表可知，灰色系统预测模型的相对误差波动较大，其中02年的相对误差达到了22.62% 这主要是由于影响垃圾产量的不确定因素变化所致。 4.2.3残差检验 Step 1：生成数列误差（残差）检验： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-160.png， Step 2：还原数列检验： 根据file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7380.png，得到第file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2014.png年垃圾产量。与实际值file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17475.png的相对误差即为残差，从表1看出GM（1，1）模型对少数年份的残差偏大。 4.3.1 模型改进 灰色系统预测模型仅从城市垃圾年产量时间序列这个综合灰色量本身挖掘有用信息，利用它的动态记忆特征，建立灰色模型来寻找系统产垃圾量的内在规律，而忽略了其他因素对垃圾产量的影响，因此有一定的缺陷。模型用于短期预测精度可达较高，但用于中长期的预测精度则会有所下降，难以令人满意。因此为了使模型预测的精度能够在中短期内均保持较高精度，下面我们通过灰色关联分析把影响垃圾年产量的主要因子从众多因素中找出来，再利用多元线性回归分析方法建立模型，预测城市生活垃圾年产量，以期能够达到较高精度。 4.3.2灰关联分析 灰色关联分析的基本思想是根据序列曲线的几何形状的相似程度来判断其联系是否紧密．曲线越接近。相应序列之间关联度就越大，反之就越小。灰色关联的表示方法很多，一般灰色斜率关联度的分辨率较高而经常被使用。斜关联度分析首先要确定变量斜率： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-8506.png （i=1，2，…，n，k=1，2，…，m） （1） 式中：n为变量个数；m为样本容量；file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29648.png为xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-8142.png标准差， file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20481.png， file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1170.png为xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-12881.png的均值，关联系数用式（2）计算 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-13807.png i，j=1，2，…，n； k=1，2，…，m （2） 采用等权平均值法计算关联度： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30453.png file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14573.png （3） 式中：file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27101.png为第j个变量对第i个变量的关联度，反映了2条曲线变化率的平均相似程度．根据对file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-8379.png的大小排序，挑选影响系统的主要因子。 4.3.3 关联度计算及影响因素选取 垃圾产生量的影响因素主要有人口、社会经济发展水平和居民生活水平3个方面，结合上海市的实际情况，选取非农业人口、国内生产总值、消费品零售总额、居民平均消费支出、能源消耗、绿化覆盖率、环境保护投资等7个因素。用表2汇总上海市1998-2007年度各年的生活垃圾产生量及各主要影响因子数据，同时，求得各项指标与垃圾产生量的线性相关系数。 表2 上海市1998-2007年度各年生活垃圾产量及各主要影响因子 | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21636.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20398.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31637.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-15583.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4723.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19473.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7191.png | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
运用MATLAB编程（程序见附录1.2），以上海市城市生活垃圾产生量为母序列，各影响因子为子序列，并作初始化处理。用公式(2)得关联系数file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29072.png，用公式(3)得关联度file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11249.png。关联度见表3。 表 3 各相关因素关联度数据 | | | | | | | | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27164.png | | | | | | | |
比较得到：rfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20132.png> rfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20258.png> rfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25048.png> rfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20947.png；所以采用与垃圾产量具有较好的线性关系的4个因子，即绿化覆盖率、非农业人口、环境保护投资、社会消费品零售总额作为上海市城市生活垃圾产量预测指标。 2.3.1 多元线性回归分析及模型建立 多元线性回归模型可表示为: y=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7038.png file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31703.png~ N（0，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17456.png） （4） 式中：y为可观测的随机变量；file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2732.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1428.png，…，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25333.png为未知参数(回归系数)；file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29941.png为不可观测的随机误差． 设有n组独立观测值（yfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17218.png：xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-865.png，xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23067.png，…，xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2073.png），i=1，2，…，n，则式四可表示为： yfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16717.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-32530.png （5） 用矩阵表示： Y=Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-12500.png+file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9421.png （6） 利用最小二乘法求回归系数file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-3538.png的估计值file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-8679.png： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24173.png=（Xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19453.png）file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-12695.pngXfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28379.png Y=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16900.png，X=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26649.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-5594.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28807.png （7） 回归系数file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10466.png确定后，即求得回归方程： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2587.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23874.png （8） 4.3.4 模型求解 通过MATLAB编程实现模型的求解（程序见附录1.3），取表1中98~04年xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-32324.png,xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-3851.png,xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30662.png,xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-18710.png数据作为求解数据带入式7，求解回归系数file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23696.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19986.png=3053.5，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28459.png=-2.6，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-32429.png=-0.6，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-15539.png=-10.7，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11826.png=10.5；得到多元线性回归预测模型如下： Y=3053.5-2.6xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17266.png-0.6xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16678.png-10.7xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24482.png+10.5xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-3483.png 式中：Y为城市生活垃圾产生量(10file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14039.pngt)；xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29529.png为非农业人口(万人)；xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24611.png为社会消费品零售总额(亿元)；xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4618.png为绿化覆盖率(％)；xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-13811.png为环境保护投资(亿元)。 取表1中05~07年xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30220.png, xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26674.png，xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-6300.png,xfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22589.png数据作为检验数据带入模型，预测城市生活垃圾年产量,对上海市98~08年城市垃圾年产量的理论值与预测值作比较，其拟合结果见图1： 图1 模型拟合效果图 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-13931.png file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21923.png 对灰色系统预测模型和多元线性回归预测模型的预测结果进行比较，见表4： 表4 模型预测结果数据比较 从图1和表4，我们可以看出：多元线性回归预测模型的最大相对误差为8.08%，通过比较多元线性回归预测模型具备了灰色系统预测模型所不具备的优越性，它综合考虑了影响城市生活垃圾产量的内因和外因，利用原始数据建立预测模型，预测结果具有较高的精度，平均相对误差为3.28%，一般来说，只要模型的C<0.35,p>0.95,则模型精度达到一级，因此该模型适用于垃圾产量预测，且能够达到令人满意的效果。 4.3.5 模型检验 1、F检验，构造检验回归方程的统计量 F=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22500.png~ F（p，n-p-1） （9） U=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-18896.png, Qfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-178.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26683.png，式中file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-623.png为样本y的平均值。 在给定显著性水平file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27437.png的情况下，若F> Ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-8664.png（p，n-p-1）,则回归方程显著性成立，否者认为回归方程不显著，模型不能用于预测。通过MATLAB编程求解，程序见附录1.4。 2、复相关系数R检验，检验式为： R=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9815.png , file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28102.png R越接近于1，表示回归方程的拟合程度越好。 取显著性水平file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28002.png=0.05，通过查表得F（4，5）=6.26<F=23.18，回归方程通过显著性检验；将数据带入进行复相关系数检验，R=0.9741接近于1，回归方程拟合程度好。检验结果如下表： 表5 多元线性回归模型检验结果 | | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11974.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9248.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26866.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30605.png | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4471.png | | file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7102.png | | | | | | | | | |
五、模型二:垃圾收运路线规划模型 5.1问题二分析 垃圾收运车辆路线问题（RCVRP）是车辆路线问题（VRP）中的一种，因此可采用遗传算法、启发算法等对它求解，但由于题中给出数据量较大，且约束条件较多，使模型的实现更加困难，所以应首先对问题进行简化，建立简单的TSP模型，运用动态分析法对路线进行初选然后再通过2-opt法对路线进行优化，使路线的路程达到最小值。 5.2 问题简化 （1） 在一个收集区，垃圾收运的过程大致是:车辆从车库出发，沿着街道或垃圾收集点收集，直到车辆满载，无法继续装载垃圾，这时车辆需赶往中转站卸空垃圾，这为车辆的第一次收集行程(最初行程);车辆清空后再返回未收集的区域，进行第二次收集，收满垃圾后开往中转站卸空，这为中间行程;若还存在未收集的区域，车辆返回未收集区域，这时车辆需完成中间行程若干次，直至所有垃圾清运完毕，车辆便从中转站直接返回车库，这为最后行程。 因此可将行程分为三类:起点是车库，终点是中转站的最初行程;起点是中转站，终点是中转站的中间行程，即往返中转站的一次环游;起点是中转站，终点是车库的最后行程。 图2 表示一车辆收运垃圾的路线 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14660.png 9 A! g, X. I+ B
由于车辆数不受限制，且中转站与各收集点和车库的距离较远，因此为了达到垃圾车收运路程的最小化，对于所有车辆可认为只进行从车库到中转站再从中转站到车库的行程。 （2） 对问题二中给出的庞大的数据量进行分析，利用Matlab的绘图功能将所有垃圾收集点的坐标表示在坐标域内， 针对所有收集点呈现相对集中的状态，对其进行人为的区域划分，可分为L1区域，L2区域和L3区域，如图3所示，垃圾收运车辆的两段行程即从车库到中转站再从中转站到车库可看作是车库，中转站与收集区域间的最短环游路线。（程序见附录2.2） 图3 垃圾收集点区域划分图 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7756.png 表6 各区域垃圾收集点集 | | | 43、38、59、42、25、49、56、33、67、46、50、80、40、75、76、52、55、64、51、26、54、78、74、47、83、69、41、44、61、73、35、58、32、60、29、91、71、63、79、90、53、28、36、65、68、77、81、72、39、57、31、37、48、34、70、66、62、85、84、30、45 | | 155、21、114、134、156、162、209、180、170、167、107、183、193、188、96、128、159、171、191、97、19、99、121、5、138、20、117、102、141、164、173、132、6、163、27、192、203、147、184、197、127、148、179、123、137、146、86、178、130、208、194、169、111、181、108、3、24、207、88、119、211、190、185、166、103、110、142、182、105、195、95、161、174、187、133、175、118、196、157、199、144、112、168、143、115、145、98、139、100、205、158、172、201、212、129、177、202、126、151、149、160、206、186、124、120、93、125、140、176、153、87、189、104、150、106、152、18、12、135、198、94、136、92、165、200、89、131、101、122、113、116、204、109、22、154、4 | | 7、257、231、243、240、238、13、213、252、271、253、227、251、11、239、249、254、258、246、220、244、228、23、274、17、224、210、216、266、15、248、241、273、9、225、214、237、226、217、230、10、269、229、245、265、255、236、272、218、221、267、260、259、247、215、234、8、264、223、16、262、250、222、275、82、235、270、261、219、268、256、233、232、276、14、242 |
（3） 垃圾收运问题一般可以这样描述：从车库到中转站的行程中经过多个收集点进行垃圾收运，实际上垃圾收运车辆路径优化问题是一个分组的TSP，也就是说是一个车辆路径问题(VRP)。本文按假设实际问题的条件，将问题简化后可分为两个问题： ①垃圾收运车在车库，中转站与各区域间简单的最短环游（TSP）问题，即确定垃圾收运车的大致收运行程。 ②垃圾收运车在收运行程中所经过收集点最短路线的实现与优化。 下文将建立TSP模型，通过遗传算法求解各区域内收集点的最短环游路线，在TSP路线确定的前提下，建立动态规划模型将路线分割成若干满足条件的路线，并运用2-opt法对路线进行优化。 5.3.1 TSP最短路线模型的建立 旅行商问题(TSP)是组合优化的一个典型问题：旅行商必须在其活动区内对每个城市访问一次仅且一次，并且最终返回到起始点。该模型求解的任务，即是垃圾车在划分的每个区域内收垃圾时，应根据何种路线收集，能使所有垃圾车在该区走过的路程最短，从而总路程最短。 令Ｇ＝（Ｖ，Ｅ），其中Ｖ为某区内所有垃圾收集点集，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7768.png＝ｎ，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-6391.png为边集，则G中一个TSP环路就是一条不重复访问file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24642.png中所有顶点的环路，记为： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11932.png 其中file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14796.png 且file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19640.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28911.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-15876.png是file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30598.png以n取模运算的结果。记file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16113.png为file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19021.png中所有TSP环路的集合，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2832.png为file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-18741.png的边权函数即两点间的Manhattan距离，定义： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21158.png 其中file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-23327.png 则旅行商模型即求所有环路中的最小权值环路file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16897.png,使得： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-103.png 且file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20548.png 5.3.2 基于遗传算法的TSP模型求解 遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体，称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体，作为下一代群体，再继续进化，这样经过若干代之后，算法收敛于最好的染色体，即作为问题的最优解。于TSP的遗传算法求解，主要有如下几个步骤： (1)编码与编码规则 采用整数排列编码方法。若对于收集点file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21235.png的一个访问顺序为file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31171.png，其中t为file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10151.png的一个排列，且记file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27185.png，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25696.png为收集点file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21678.png之间的距离，则数学模型为 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28209.png (2)适应度函数 直接用以上数据模型作为适应度函数，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27892.png (3)遗传算子 遗传算子的选择必须与编码方式匹配，一方面是为了产生合法的个体，使算法得以继续下去；另一方面是为了使算法能较快收敛。采用比例选择方法。根据个体的适应度，采用概率选择即轮盘赌策略，并保留当前最优解，使适应度较大的个体能以较大的概率生存下来。 程序采用部分匹配交叉，基于交叉已经含有变异，未设计单独的变异算子。经过选择保留的染色体放到杂交池中。根据选定的杂交算子进行杂交，以期通过杂交得到适应值更好的染色体。采用贪婪交叉算子，这种算子的优点在于在算法前期能够使值迅速向最优值靠拢。 (4)进行迭代运算 根据得出的新的染色体，再次返回选择染色体的步骤进行迭代。当迭代次数到到150时，算法停止。 (5)算法流程如下图所示 图4 算法流程图 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25505.png
# `& v) g' w6 q8 M通过MATLAB编程实现遗传算法对TSP最短路线模型的求解（程序详见附录2.1），输出各区域最短路径示意图： 图5最短路径示意图 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-30420.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1497.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26461.png 5.4.1 动态规划实现垃圾收运路线的初选 在初始解的基础上，如何将一条TSP路线分割成若干条满足条件的路线，是接下来要解决的问题。这个问题可以描述为：假设有n个收集点，相应的顺序为 1，2，3，…，n，定义断点为 TSP路线分割后作为前一条路线的终点，该断点后面的节点则成为另一条路线的起点。目的是要寻找K个断点，使得断开初始TSP路线的成本最小即路程最小，从而形成 K条可行路线。条件是要满足车辆容量的限制。 假设在收集点i处断开路线，相应增加的距离是从收集点 i到车库0的距离加上收集点i+1到车库0的距离再减去从收集点 i到收集点i+1的距离。 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7628.png
* \) z; [: W; ]* J* I* i距离增加 e 可表示为 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-5503.png 式中；dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-6545.png为从节点i到节点j的距离即Manhattan距离： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-22342.png 因此形成K条可行路线增加的总距离为，file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24085.png，目标函数可以表示成整数规划形式 ： Minfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28882.png S.t. file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-20048.png，k=1,2,…,K, 1file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4902.pngifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4448.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17008.pngifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-13880.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26470.png…file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2562.pngifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11433.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24174.pngn 式中：ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4192.png为第k个断点的序号，且ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10104.png= ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4951.png 如果设固定点ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21619.png=n，则意味着收集点i为TSP路线的起点，收集点 n为路线的终点。于是我们只需要寻找 K-1个断点，相应的就有 K-1个最优决策阶段，在阶段 k∈{1，…，K}要确定断点ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31336.png在该点结束，到设施。为了建立动态规划模型，设sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9818.png为 k阶段的状态，它等于断点的序号，即sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31749.png= ifile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-5554.png，第 k条路线在此结束。考虑到车辆容量和客户的需求，设lfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17165.png和代表ufile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-11402.png代表阶段车辆可以完成收运的最小值和最大值，则：lfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14679.png=file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7509.png，ufile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24476.png=kQfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26033.png。如果决策变量dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26022.png代表路线k中集中点的数量，那么sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-1117.png= sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-3302.png-dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17388.png。若ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-28906.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26610.png,dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-27715.png)表示路线k在收集点sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14530.png断开后经过dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17885.png个收集点的路程函数，此最优决策用于其他相应决策阶段，因此在k阶段动态规划数学模型为： ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2551.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-29143.png,dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31322.png)=efile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-19037.png+ ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24546.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2068.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10474.png) ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16146.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-971.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-3200.png)=Minfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26739.pngffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-16978.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-15298.png,dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2489.png) S.t. dfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17068.png>0, (1) lfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-31297.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-2918.png, (2) file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-21174.png, (3) 同时sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25915.png=0, ffile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10813.pngfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-948.png(sfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-25423.png)=0。约束（1）只允许产生有意义的路线；（2）确保在该阶段完成收运在可行约束内；（3）保证车辆容量不超限。 这样，在给定点位置的情况下，应用动态规划的数学模型便可以计算出每阶段最优收集点个数，从而形成最少的车辆路线，实现TSP路线的最优分割，确定了各条路线上的收集点，进而解决了路线最短问题。 5.4.2 动态规划模型的求解 运用MATLAB编程和Excel实现对动态规划模型的求解（程序见附录2.3），得到垃圾收运的初始路线如下表： 表7 收运路线路径表 | 最短收运路线 （所有点数为点的序号，1为车库，2为收集点） | | | | 1（车库）→43→38→59→42→25→49→56→33→67→46→50→80→40→75→76→52→55→64→51→26→54→2(中转站) | | | | 1→78→74→47→83→69→41→44→61→73→35→58→32→60→29→91→71→63→79→90→53→28→36→65→68→77→81→72→2 | | | | 1→7→257→13→243→239→254→246→238→253→220→249→252→227→258→251→213→231→11→240→271→2 | | | | 1→228→230→210→241→10→216→226→248→237→9→229→15→225→273→269→214→255→17→274→266→224→245→23→217→265→236→2 | | | | 1→272→219→261→247→218→222→234→250→268→264→267→8→259→260→275→256→16→221→233→215→270→223→262→82→272→5→2 | | | | 2（中转站）→155→21→114→134→156→162→209→180→170→167→107→183→193→188→96→128→159→171→191→97→19→99→121→5→138→20→117→102→141→164→173→1（车库） | | | | 2→132→6→163→27→192→203→147→184→197→127→148→179→123→137→146→86→178→130→208→194→169→111→181→108→3→24→1 | | | | 2→207→88→119→211→190→185→166→103→110→142→182→105→195→95→161→174→187→133→175→118→196→157→1 | | | | 2→199→144→112→168→143→115→145→98→139→100→205→158→172→201→212→129→177→202→126→151→149→160→206→186→1 | | | | 2→124→120→93→125→140→176→153→87→189→104→150→106→152→18→12→135→198→94→136→92→165→200→89→131→101→122→1 | | | | 1（车库）→14→242→37→109→4→232→45→204→30→39→22→276→66→84→263→34→154→48→57→116→2（中转站）→62→70→31→85→113→1（车库） | | |
5.4.3 路线的优化 动态规划方法实现路线的最优分割之后，本文对所形成的k条最优可行路线通过2-opt侧交换的方法进行改进，即通过交换路线内的点顺序，减少路线上的运输距离，使得SDL即的当前解得到进一步的优化。2-opt交换的思想如下: 在进行无时间窗限制的路线改进，搜寻更优路径时，通常采用2-opt法。2-opt法是应用局部搜索的概念，通过对边(或者弧)进行交换，在初始可行解或者某些近似算法产生的较好解的基础上对当前解进行调整，每次的调整可以使得当前解得到改进，更趋于问题的最优解，直至解在邻域内不能再改进为止。 2-opt法交换如图6所示。它是将一条路径不相邻的两条边(或者弧)断开，即图中的边（1，2）和（3，4），相应的由边（1，3）和（2，4）取代，同时原来路径中2与3之间的路线反向。 file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-4139.png 经过2-opt优化后的路线为： 表8 优化后的收运路线路径表 | 经过优化的最短收运路线 （所有点数为点的序号，1为车库，2为收集点） | | | | 1→7→257→231→243→240→238→13→213→252→271→253→227→251→11→239→249→254→258→246→220→244→2 | | | | 1→228→23→274→17→224→210→216→266→15→248→241→273→9→225→214→237→226→217→230→10→269→229→245→265→255→236→2 | | | | 2（中转站）→155→20→21→19→5→114→134→156→162→209→180→170→167→107→183→193→188→96→128→159→171→191→97→99→121→138→117→102→141→164→173→1（车库） | | | | 1（车库）→62→276→66→57→39→204→34→4→70→14→48→30→85→45→84→37→116→232→22→242→263→31→2（中转站）→109→154→113→1（车库） | | |
路线3、4、6、11经过优化后路程均有明显的缩短，其他路线已达到最优化，故在此不列出。优化后的总路程为S=4247998 (feet) 5.5 最小车辆数的讨论 由于在建立最短路线模型时，我们假设车辆的数量不限，这与实际情况不符，所以我们制定了垃圾收运的最短路线后再对最小车辆数进行讨论。 设车辆数为file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-14201.png，需要运输完11趟路上的垃圾，且每辆车至少走了一个最初行程和一个最后行程，则在调度中共需要走的中间行程数目file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-17692.png，并假设每趟行程垃圾车都达最大装载量200(yards)，且每辆车平均分配中间行程，已达资源最优分配。 从题目所给约束条件： 1、垃圾车每天的负载总量：2200.0 （yards） 2、垃圾车的行车速度：40（MPH, Miles Per Hour） 3、每辆垃圾车每天最多经过的垃圾收集点个数：500 4、车库的工作区间为早上8点至下午5点，tfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-10752.png=9 得到以下方程： k>file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-18587.png （1） tfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-24807.png为垃圾车收运工作最大时间量，tfile:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-26586.png为第i条路线收运总时间， 每辆车在总运输过程中的垃圾装载量为： file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-7914.png （2） 用Excel求出各路线的总收运时间：file:///C:/Users/lenovo/AppData/Local/Temp/ksohtml/wps_clip_image-9139.png =25.7 h 对（1），（2）方程求解得到：k>2.8 ，即取最小车辆数为3。 5.6.1 模型的适用性分析 本题是垃圾收运线路优化问题，由于题目所给数据量大，且约束条件较多，故将问题简化为TSP最短路线模型和动态规划模型。 TSP模型采用遗传算法求解，遗传算法这种算法的主要特点不仅是采用群体搜索策略和可实现群体中个体之间的信息交换，且搜索过程不依赖于梯度信息。它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。这一改进优化模型实现了时间、路线长及综合效益最优化，将庞大的数据资料进行简化为简单的旅行商非线性规划问题，意义明确，便于求解，特别适用于大区域、复杂的垃圾收运系统的计算求解。 动态规划模型是在TSP路线建立后，将路线分割成k条满足条件的路线。动态规划的求解方法是先把问题分成多个子问题（一般地每个子问题是相互关联和影响的），再依次研究逐个子问题的决策。当全体子问题都解决时，整体问题也随之解决。建立的动态规划模型在题目约束条件下具有较强的针对性和适用性，通过对模型的求解可实现TSP路线的最优分割。 5.6.2 算法的鲁棒性分析 鲁棒性量化指标的定义：算法的鲁棒性是指当被控对象的特性发生变化时，如系统成分的忽略，大的参数变化，阶次的时延发生迁移等情况下，控制算法对系统稳定性的保持能力和对期望输出的跟踪能力。 本文针对问题二建立的模型是解决基于遗传算法的旅行商TSP问题，因此影响模型稳定性及鲁棒性的因素主要有以下几点：第一，系统本身的稳定性，即遗传算法本身是一个随机搜索的方法，不同次运算结果不同纯属正常，往往评价一个算法的好坏并不是以某一次的运算结果为标准的；第二，系统的静差，即被控对象模型参数剧变时系统的稳定性；第三：算法系统的变异率影响。 针对系统的稳定性控制，我们通过多次试验，对于运算代数进行了比较系统的统计，发现90%的实验都在100代或100代之前达到最优化，因此我们人为的将程序设定为100代，使程序运行达100代后自动停止，这样，系统本身不会受到遗传算法的随机性影响； 针对于系统的静差影响，由于我们运用的遗传算法主要通过交叉、变异、选择运算实现，故而被控模型的参数变化对于模型的影响极小，再次可以忽略不计。 对于系统的变异率的设定，可以采用自适用变异率，即变异率初始值比较大，但随着运算代数的增加，变异率会逐渐减小，最后得到最优化结果，这样不仅节省了程序的运算时间，又使得系统运算的结果更加趋于优化。 综上所述模型具有良好的稳定性及鲁棒性。 六、模型的评价及推广 6.1问题一模型评价： 模型的优点：模型综合考虑了影响垃圾产量的主要因子，通过建立多元线性方程分析确定各因子的相关系数，使得多元线形回归预测模型在城市生活垃圾预测中具有其他模型不具备的优越性，其预测精度与其他模型相比有很大的提高，得到令人较为满意的数据结果，证明了它在城市生活垃圾产量预测方面的可行性。另外，模型实现过程，运算过程可采用MATLAB软件编程，方便灵活简单，便于操作。 模型的缺点：该模型不具备自组织自适应和自学习能力，受突发事件影响比较大，该模型只能适用于正常情况下城市发展的垃圾产量预测。 模型的推广：该模型适用多个城市的预测，只需改变输入变量数，将数据更改为适合其他城市发展的数据，便可对其他城市进行预测，适用范围广；其次，该模型适用多个参数的预测，不止对垃圾产量的预测有效果，只需改变其内部影响因子，便可实现对其他预测问题的解决。 6.2问题二模型评价： 模型的优点：我们首先对问题进行了简化，建立了TSP模型和动态规划模型，结合题目所给约束条件，具有较强针对性和适用性。简化后的模型及算法能比较容易地在MATLAB等编程软件中实现，可行性较强，且具有一定的推广价值。最后运用2-opt方法对模型选择的路线进行了有效的优化。 模型的缺点：模型忽略了车辆的数量限制，把所有车辆看作完成收运路线后即回车库。对所有收集点进行人为的区域划分，少数离散的收集点会给最短路线的确定带来一定误差，但经过计算修正后，误差较小。 模型的推广：对垃圾收运路线的选定建立的简化模型，简便易懂，具有较强的普遍性和适用性，通过改进后能够广泛用于其他城市垃圾收运路线的制定与优化。 七、 参考文献 【1】 傅立，灰色系统理论及其应用[M]，北京：科学技术文献出版社，1992 【2】 上海市统计局，上海统计年鉴（1999-2008）[M]，上海：中国统计出版社 【3】 郑人权，预测学原理[M]，北京：中国统计出版社，1998 【4】 赵静，但瑜等，数学建模与数学实验[M]，北京：高等教育出版社，2000， 【5】 孙家广，计算机辅助设计技术基础[M],清华大学出版社，2000 【6】 宁宣熙，运筹学实用教程[M],科学出版社，2002 【7】 涛渊、黄兴华等，生化垃圾收运模式研究[J]，环境卫生工程2003，11（4）：211-212 % C4 \1 C5 o0 B V8 j |
八 相关附录 附录1.1 function xk1=greyforecast(A,k) %灰色预测模型 Yn=A(2:k); %做累加处理 A1(1)=A(1); for i=2:k A1(i)=A1(i-1)+A(i); end for i=1:k-1 A2(i)=-1/2*(A1(i)+A1(i+1)); end B=[A2;ones(1,k-1)]; B=B'; au=inv((B'*B))*B'*Yn'; xk1=(A(1)-au(2)/au(1))*exp(-au(1)*k)+au(2)/au(1); p=[470 500 641 644 467 585 610]; %调用程序对第8，9和10年经行预测 for i=8:10 p(i)=greyforecast(p(1:i-1),i-1)-greyforecast(p(1:i-2),i-2); end >> ans = Columns 1 through 7 470.0000 500.0000 641.0000 644.0000 467.0000 585.0000 610.0000 Columns 8 through 10 638.8257 670.9732 705.9709 附录1.2 %6个因素各年的值 fangzhen=[921.7 yangben=[372 419 454 470 500 641 644 467 585 610]; %10年垃圾量真实值 | 
IP卡
狗仔卡
发表于 2013-9-13 16:01
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
不明觉厉啊啊啊啊啊
