城市生活垃圾管理系统现状研究-大学论文

城市生活垃圾管理系统研究摘要本文对城市垃圾管理系统进行了研究，并对其中城市垃圾年产量的预测及垃圾收运车的路线选择进行了着重分析。首先，对城市垃圾的年产量进行预测。分析搜集数据得出垃圾的年产量与许多因素有相关关系，且它自身并没有随时间变化的明显趋势。对各因素进行灰色关联度分析，得到影响垃圾年产量的主要的因素为：人口、住宅使用面积、消费水平、可支配收入。并用回归分析的方法求出了垃圾的年产量与各主要因素之间的函数关系（以北京市为例）：由于主要因素的变化规律明确，用GM(1,1)模型对各主要因素进行预测，结果见附表1。然后将各因素的预测值代入回归方程，得到2008年垃圾年产量的预测值为680万吨。对比趋势预测（692.7万吨）及2008年的真实值（672万吨）进行检验，得到模型准确性好，实用性强的结论。其次，设计垃圾收运车的运行路线，使整个收运过程路程最短，并在此基础上让每辆车的收运时间均匀。分析问题，将其转化为一辆无限大容量的车遍历所有收集点的最短路径问题（TSP），运用现代优化算法中的遗传算法进行求解，见表11。再让垃圾收运车沿求出的路线收集垃圾，当垃圾量等于或略小于200后前往中转站（为一条线路），卸载完垃圾后再前往下一个收集点，如此往复进行。进而可以计算出每辆车所需时间为：结果经过的线路段路线花费总时间第一辆车线路5、线路6、线路7、线路106.998小时第二辆车线路4、线路8、线路9、线路117.106小时第三辆车线路1、线路2、线路36.103小时由于遗传算法的种群选择比较大（为200）所以结果具有很强的稳定性，并且算法是全局寻优的，具有实用性。路线的安排中，车载重量为都未达到200，留有一定得稳定裕量，使模型有较强的鲁棒性。关键词： 灰色关联度；多元线性回归；GM(1,1)；遗传算法；TSP问题；一、问题重述随着人类生产和生活的不断发展，由此而产生的垃圾对生态环境及人类生存带来极大的威胁，成为重要的社会问题。一般认为，城市生活垃圾的影响因素包括地理位置、人口、经济发展水平（生产总值）、居民收入以及消费水平、居民家庭能源结构等等。城市生活垃圾产量是垃圾管理系统的关键参数，因此对未来某段时间内垃圾产量的准确预测，是相关垃圾管理部门做出管理规划的前提。另外，城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收集与运输，这一过程称为城市垃圾的收运。收运过程可简述如下：每天垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。（以上收运过程均在各点的工作区间之内完成。）请利用数学方法建立以下问题的数学模型，并求解模型，对模型的结果做出合理分析和解释。1. 查阅相关文献，搜集垃圾产量数据，在此基础上建立城市生活垃圾产量中短期预测模型，并且分析模型的准确性和实用性。2. 在收运过程已知下述四个条件下，如何安排垃圾收运车的收运路线，使在垃圾收运车的行车里程尽可能的少，或者垃圾收运时间尽可能短？(1)车库和收集点、收集点与中转站、中转站与车库的距离；(2)各收集点每天的垃圾产量；(3)每辆垃圾收运车的最大载荷；(4)垃圾收集点、车库、中转站的工作区间。请给出规划以上垃圾收运路线的数学模型，并设计出有效的算法，针对附录中给出的数据，求解模型。并且对模型的适用性、算法的稳定性和鲁棒性做出分析。二、模型的假设与符号说明2.1模型的假设1忽略每天交通高低峰的路况区别及其他特殊情况，即垃圾收运车的行驶速度保持不变；2城市两点之间的manhattan距离能很好的表示他们之间的实际距离；3所搜集到得数据真实可靠，且具有代表性；4忽略遗传算法本身所造成的系统误差；2.2符号说明：参考数列，表示时刻；：表示第比较数列；：表示比较数列对参考数列在时刻的关联系数；：数列对参考数列的关联度；：分辨系数；：表示回归系数；：阶单位矩阵；：回归误差平方和；：GM(1,1)模型的初始数据；：级比偏差；：分别表示人口、住宅使用面积、消费水平、可支配收入；：表示垃圾年产量；：表示经过第段线路所花费的时间；：为 变量，当为1时表示第辆车通过第段线路，当为0时表示第 辆车不通过第段线路；：表示第辆车通过路线花费的总时间；：三辆车走过所有路线的总时间；三、问题分析3.1 问题分析问题一，在搜集相关数据的基础上，对影响垃圾管理规划的主要因素垃圾产量进行预测。分析问题我们发现，影响垃圾产量的因素很多，如：人口数量、居民生活水平等，而且垃圾产量并没有随年份变化的明显趋势。因此，必须首先找到影响垃圾年产量的主要的因素，然后对垃圾年产量与主要因素进行多元回归分析，得到回归方程，进而进行垃圾产量的预测。预测过程必须遵循以下两条原则：连贯性原则：是指所研究对象的发生和发展按照一定规律进行，这个规律在其发生和发展过程中贯穿始终，事物未来发展与过去、现在的发展无根本不同。类推的原则：是指事物必须有某种结构，而这种结构及其变化要有一定的模型，可以根据所测定的模型，可以根据所测定的模型，类比过去和现在，预测未来。为预测垃圾的年产量，首先应该进行各主要因素数值的预测。因为影响垃圾年产量的因素，都有明显的规律可以遵循，所以我们使用GM（1，1）模型对个主要指标进行了预测。最终将主要指标的预测值代入回归方程得到所要预测的垃圾年产量。问题二，垃圾收运车从车库出发后，要将所有收集点的垃圾收集完并运往中转站，但是垃圾收运车的载重量不能超过200，所以，在垃圾收运车负载达到最大载重量时要前往中转站，卸下所有垃圾后再返回继续收集。可以先假设垃圾车的载重量无限大，可一次将垃圾全部收集完毕，因此暂不考虑中转站问题，而直接从车库出发，找到一条遍历所有收集点的最短路径，从而将问题转化为TSP问题，这样就可求得最短收集路线。但是由于垃圾收集点高达275个，使用常规方法根本无法在有效时间内完成计算，因此这里考虑使用现代优化算法中的遗传算法进行求解。然后，再让垃圾收运车沿求出的路线收集垃圾，当垃圾量等于或略小于200后前往中转站，卸载完垃圾后再前往下一个收集点，如此往复进行。进而可以计算出所需时间，以此可以决定至少需要使用的垃圾收运车数目。将经历每次到中转站之间的收集路线作为一条子路线，将这些子路线均衡地分配给每辆车执行即可。四、模型的建立与求解4.1 基于多元线性回归的生活垃圾预测模型 城市生活垃圾产量的准确预测是进行城市固体废物处理处置系统科学决策的基础。只有对未来进行准确的预测，才能够对未来处理规模、处理能力以及处理要求进行确定，进而才能根据需要，对处理处置系统进行科学筛选和决策。然而，影响垃圾质和量变化的因素很多，主要有三类：一、影响垃圾质和量变化的内在因素，主要是指直接导致生活垃圾质和量变化的因素，如人口数量、居民生活水平、城市建设水平等。人口增加，在其他因素不变的情况下垃圾产量必然增加；同样，由于经济的发展，居民生活水平的提高，居民消费品的数量与类别增加，相应垃圾产量也会增加；城区范围增大，保洁区面积增大，垃圾产生量也增大。影响垃圾质变化的因素有居民生活水平、能源结构、生活的地域差异以及消费方式等。如在以燃煤为主的地区以及北方采暖期，生活垃圾中无机灰渣的含量较高。二、影响垃圾质和量变化的社会因素，主要指社会行为准则、社会道德规范、法律规则制度等，是一种外部的、间接的因素。如国家推行垃圾减量、回收和再利用措施，可以大幅度减少垃圾最终处理量；垃圾分类收集则是从源头改善垃圾的质，减少后续垃圾的处理难度，利于垃圾回收而减少垃圾最终处理量。三、影响垃圾质和量变化的个体因素，主要是指垃圾产生的主体人类本身个体的行为习惯和受教育程度等。对生活垃圾质和量进行预测，需综合以上三种因素，通过这些因素的变化情况，分析垃圾质和量的变化趋势，从而得出预测值。因而我们选取人口、生产总值、居民可支配收入、居民消费性支出、社会消费品零售总额、平均每人生活消费能源、人均住宅使用面积等作为生活垃圾预测的因子集，进一步的对生活垃圾产量的变化进行研究。4.1.1 基于灰色关联的主要因素提取对于主要影响因素的提取，数理统计中通常运用回归分析、方差分析、主成份分析等系统分析的方法进行分析。但这些方法都不可避免的存在以下的几点不足之处：1)要求有大量数据；2)要求样本服从某个典型的概率分布；3)计算量大；4)可能出现量化结果与定性分析结果不符的现象。然而，灰色关联分析的基本思想是根据序列曲线几何形状的相似程度来判断其联系是否紧密。曲线越接近，相应序列之间的关联度就越大，反之就越小。由灰色关联度导出灰色关联序，以进行优势分析，从而知道在众多的影响因素中，哪些是主要因素，哪些是次要因素。这使得灰色关联分析对样本量的多少和样本有无规律都同样适用，而且计算量小，十分方便，更不会出现量化结果与定性分析结果不符的情况。因此，我们选用灰色关联分析从给定的因素集中提取影响城市生活垃圾的主要因素。选取参考数列，本文为生活垃圾的年产量，表示时刻（年代）。假设有个比较数列则称 （1）为比较数列对参考数列在时刻的关联系数，其中为分辨系数。称（1）式中、分别为两级最小差及两级最大差。一般来说，分辨系数越大，分辨率越大；越小，分辨率越小。（1）式定义的关联系数是描述比较数列与参考数列在某时刻的关联度的一种指标，由于各个时刻都有一个关联数，因此信息显得过于分散，不便于比较，为此我们给出 （2）为数列对参考数列的关联度。并做如下分析：若存在，满足，则称因素优于，记为。若恒有，则称为最优因素。其算法流程图如下：计算灰色关联矩阵计算因素关联序计算因素关联序是否有最优因素？确定准优因素确定最优因素结束是否通过灰色相关度分析，就能较为准确的提取出影响城市垃圾产量的主要因素。4.1.2 因素之间的多重共线性的分析通过灰色相关度分析，我们能找出影响城市垃圾产量的主要因素。但各个因素之间还存在很强的多重共线性关系，即不同的因素之间的相关性非常的好。可能正是由于这种多重共线性关系造成了一些不是主要的因素通过了关联度分析。为使选择的因素之间的多重共线性关系尽可能的少可做如下的处理：（一）删除不重要的解释变量 解释变量之间存在共线性，说明解释变量所提供的信息是重叠的，可以删除不重要的解释变量减少重复信息。但从模型中删去解释变量时应该注意：从实际经济分析确定为相对不重要并从偏相关系数检验证实为共线性原因的那些变量中删除。如果删除不当，会产生模型设定误差，造成参数估计严重有偏的后果。（二）追加样本信息 多重共线性问题的实质是样本信息的不充分而导致模型参数的不能精确估计，因此追加样本信息是解决该问题的一条有效途径。但是，由于资料收集及调查的困难，要追加样本信息在实践中有时并不容易。（三）利用非样本先验信息 非样本先验信息主要来自经济理论分析和经验认识。充分利用这些先验的信息，往往有助于解决多重共线性问题。（四）改变解释变量的形式 改变解释变量的形式是解决多重共线性的一种简易方法，例如对于横截面数据采用相对数变量，对于时间序列数据采用增量型变量。（五）逐步回归法 逐步回归（Stepwise Regression）是一种常用的消除多重共线性、选取“最优”回归方程的方法。其做法是将逐个引入自变量，引入的条件是该自变量经F 检验是显著的，每引入一个自变量后，对已选入的变量进行逐个检验，如果原来引入的变量由于后面变量的引入而变得不再显著，那么就将其剔除。引入一个变量或从回归方程中剔除一个变量，为逐步回归的一步，每一步都要进行 F 检验，以确保每次引入新变量之前回归方程中只包含显著的变量。这个过程反复进行，直到既没有不显著的自变量选入回归方程，也没有显著自变量从回归方程中剔除为止。本文采用（五）逐步回归的方法，将灰色关联度分析得到的各变量（主要因素）的排列次序依次加入变量，逐次记录计算结果，观察每一个因素对系统的影响，包括方面：对拟合优度的影响；对调整后的拟合优度的影响；参照检验值考察自身的零系数概率。在变量筛选过程中，我们通过细致地观察各变量在不断变换的方程模式中的具体表现，以数据为基础，将定量分析和定性分析有机地结合起来，最终确定模型的最适变量。4.1.3 多元线性回归分析多元回归分析的模型为：（3）式中都是与无关的未知参量，其中成为回归系数。现得到个独立观察数据由（3）得（4）记（4）式表示为其中，阶单位矩阵。模型（3）中的参数用最小二乘法估计，即选取估计值，使当时，时，误差平方和达到最小。将影响垃圾产量的各因素数据代入模型求得各个系数。4.1.4 基于GM（1,1）模型的指标预测 （1）灰色预测的方法设已知参考数据列为，做一次累加（）生成数列其中。求均值数列：则。于是建立灰微分方程为相应的白化微分方程为记，则由最小二乘法，求得使达到最小值的。于是求解白化微分方程得。 (2) 灰色预测的步骤:数据的检验与处理首先，为了保证模型方法的可行性，需要对已知数据列做必要的检验处理。设参考数据为，计算数列的级比如果所有的级比都落在可容覆盖内，则数列可以作为模型的数据进行灰色预测。否则，需要对数列做必要的变换处理，使其落入可容覆盖内。即取适当的常数，作平移变换则使数列的级比:建立模型建立模型，则可以得到预测值，而且。:检验预测值（a）残差检验：令残差为，计算如果，则可认为达到一般要求；如果，则认为达到较高的要求。（b）级比偏差检验：首先由参考数据计算出级比，在用发展系数求出相应的级比偏差如果，则可以认为达到一般要求；如果，则认为达到较高的要求。:预测预报由模型所得到的指定时区内预测值，根据实际问题的需要，给出相应的预测预报。根据上述模型，我们能对未来的各因素的值进行预测。然后将预测值代入多元线性回归模型得到未来时间的城市垃圾产量。4.1.5 预测模型的实现以北京市1999年到2007年的各个指标的情况为例，对2008年北京市的垃圾产量进行预测，并用2008年的实际值对其准确性进行对比检验。表1是1999年到2007 年的各个指标数据。预测步骤：利用灰色关联度求取垃圾产量与各因素之间的相关性关系，得到垃圾产量与各个因素的关联度见表2。可以看出人口、住宅使用面积、消费水平、可支配收入与垃圾产量相关度较大。结合逐步回归的思想，将灰色关联度分析得到的各主要因素依次加入变量，逐次记录计算结果，观察每一个因素对系统的影响，以数据为基础，将定量分析和定性分析有机地结合起来，最终确定模型的最适变量为：人口、住宅使用面积、消费水平、可支配收入。表1 垃圾产量及其相关因素的数据值时间垃圾量人口生产总值居民收入居民消费水平社会消费品零售总额消费能源住宅使用面积1999449.512572689.69182.77498.41313.3121.415.72000244.413823333.610349.78493.41443.3126.416.8200130313833710.511577.88922.71593.5130.317.62002321.414234330.412463.910284.61673.3136.918.22003454.514565023.813882.611123.81916.7153.918.7200449114936060.315637.812200.42626.6164.219.12005454.615386886.31765313244.22902.8179.919.52006538.215817870.319977.514825.43275.2194.720.12007600.916339006.221988.715330.43800.2203.320.75表2 垃圾产量与各因素之间的关联度关联度人口生产总值可支配收入消费水平消费品零售额平均能耗住宅使用面积垃圾产量0.84130.53410.63150.66130.60450.75860.8339：令人口、住宅使用面积、消费水平、可支配收入分别用表示，对其进行多元线性回归，利用最小二乘法求得各系数值为：， 。这样得到回归方程为： （5）相应的检验值为：表3 多元回归检验值检验FP结果0.92712.70.015可以看出，检验结果比较理想，回归方程是可信的。：用GM(1,1)模型对各因素2008年的数据进行预测。由人口发展理论及经济学理论，易知人口、住宅使用面积、消费水平、可支配收入是具有明显的按时间发展的规律的，所以这些因素能用GM(1,1)模型进行预测。将表1的数据代入4.1.4的模型得到各因素2008年的预测结果。以人口预测为例，见表4从表4中可以看出，北京各年人口的预测值与实际值之间的相对误差、级比偏差都很小，预测结果比较理想。同理，我们预测得到北京2008年的人均消费水平、人均消费能源、人均住宅使用面积的数据，见表5。表4 人口预测结果人口实际值预测值残差相对误差级比偏差19991257125700200013821358.15923.84130.01730.0672200113831392.856-9.85590.0071-0.0248200214231428.44-5.43960.00380.0033200314561464.932-8.93240.0061-0.0023200414931502.357-9.35740.0063-0.0001200515381540.739-2.73860.00180.0045200615811580.10.89970.00060.0023200716331620.46812.53240.00770.007120081660.917表5 相关指标的预测结果因素人均消费水平人均消费能源人均住宅使用面积预测结果17142.82220.997321.3044具体的预测结果见附表1。可以看出他们的预测结果都是比较理想的，所以能够作为对2008年垃圾产量的预测的数据。：利用中的回归方程（5），及中对各个指标的预测值，求出北京2008年的垃圾产量。将数据代入回归方程得到北京2008年的垃圾产量为：1275.245-2.67571660.917-0.021817142.82+10.1925220.9973+92.48921.3044=680.3535（万吨）。4.1.6 结果分析（一）回归方程负系数分析由回归方程式（5），我们看到代表人口数量和人均消费水平的系数是负数，这显然与我们的生活常识及相关性分析不符，见表6。表6 1999年2007年四元线性回归系数符号情况常数为正数影响趋势人口数系数为负数人口垃圾产量居民消费性支出系数为负数居民消费性支出垃圾产量平均每人生活消费能源系数为正数平均每人生活消费能源垃圾产量人均住宅使用面积系数为正数人均住宅使用面积垃圾产量为了方便观察与分析各系数对全国垃圾产量的影响，这里将上述分析分两阶段总结为表7。表7 自变量的系数与北京垃圾产量关系一览表年份参量常数人口居民消费性支出人均生活消费能源人均住宅使用面积199920032003200719992007从表7中看出：不同年份段，自变量的系数影响北京市垃圾产量的趋势不同。从1999年2007年段来看，当平均每人生活消费能源、人均住宅使用面积为正影响时，符合人们的一般看法，但人口数和居民消费性支出为负影响却不好理解，但揭露出一个事实，不同时期各自变量对垃圾产量的贡献是不同的。对北京市生活垃圾产量进行多元线性回归，将北京市垃圾产量与诸多因素的关系已反映出来，可以看出每个时间段各因素的影响趋势不大相同，随机性强。（二）模型的准确性和实用性分析1、准确性为检验模型的准确性，我们用简单趋势预测法GM(1,1)模型，对2008年北京市的垃圾年产量进行预测，结果如下表。表8 2008年北京市的垃圾年产量预测结果垃圾量实际值预测值残差相对误差级比偏差1999449.5449.5002000244.39279.9103-35.52030.1453-1.05652001303312.9347-9.93470.03280.09822002321.4349.8554-28.45540.0885-0.05412003454.5391.132163.36790.13940.20932004491437.278853.72120.1094-0.0352005454.6488.8699-34.26990.0754-0.20762006538.2546.5479-8.34790.01550.05562007600.9611.0308-10.13080.0169-0.00142008672692.691520.69150.030791从表中的数据可以看出用简单的趋势预测的结果并不理想。两种预测的结果与实际值的对比如下：表9 预测结果对比2008年实际值GM(1,1)回归预测数值672692.6915680.3535误差020.69158.3535由上面的分析可以看出，回归预测的精度要高于简单的趋势预测，准确性较好。2、实用性分析由于垃圾产量的变化并没有，明显的数值规律可以遵循，所以一些简单的趋势预测方法并不能很好的描述它发展变化。而且这些完全基于观察值的预测，并没有分析其内在成因，这样会有产生误差的累积过程，不能用于短中期预测。然而，运用灰色关联的方法找到与垃圾产量有明显关系的主要因素，这样就找到了垃圾产量变化的内因；用多因素线性回归的方法将这些主要的因素有机的结合在一起，有利于研究垃圾产量变化的规律，可以避免误差的累积。由于影响垃圾产量的主要的经济、社会因素的发展规律已经非常明确和完善，站在对其中的各个主要的经济、社会因素进行预测，然后代入回归方程间接地预测垃圾的产量的方法是可行的也是实用的。4.2 问题二模型的建立与求解4.2.1 基于遗传算法的模型由于在垃圾收运的过程中，垃圾收集车的数目不确定，因此首先需要估算出在车库工作区间内所需的最少垃圾收集车数。由于所有收集点的垃圾总量为2132.5，小于每辆垃圾车每天的负载总量2200.0，且总计275个垃圾收集点，也小于每辆垃圾车每天最多经过的垃圾收集点个数500。因此在不考虑车库工作区间的情况下，用一辆车从车库出发，遍历所有收集点的最短路径，最后回到车库，从而将问题转换为模型。由于含有276个点的模型数据量十分庞大，通过查阅相关资料知道，普通算法的模型最适合的规模是25个点左右，求解起来比较容易。因此这里考虑采用现代优化算法中的遗传算法进行求解，用于解答类似问题的组合优化问题的全局最优解。遗传算法（，简称）是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。其实现方法如下：(1)根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示可行解域的每一解。(2)对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。(3)确定进化参数群体规模、交叉概率、变异概率、进化终止条件。表10 生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存算法停止时，最优目标值的解有最大的可能被留住个体解染色体解的编码基因解中每一分量的特征适应性适应度函数值种群根据适应度函数值选取的一组解交配通过交配原则产生一组新解的过程变异编码的某一分量发生变化的过程为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到最优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进化结束，也可能根据找出近似最优是否满足精度要求来确定。表10列出了生物遗传概念在遗传算法中的对应关系。针对问题二，求解的遗传算法的参数设定如下：种群大小：最大代数：交叉率：，交叉概率为1 能保证种群的充分进化。变异率：，一般而言，变异发生的可能性较小。(1)编码策略采用十进制编码， 用随机数列作为染色体， 其中(），, ；每一个随机序列都和种群中的一个个体相对应，例如一个9城市问题的一个染色体为0.23，0.82，0.45，0.74，0.87，0.11，0.56，0.69，0.78其中编码位置代表城市，位置的随机数表示城市在巡回中的顺序，我们将这些随机数按升序排列得到如下巡回：613784925(2)初始种群本文中我们先利用经典的近似算法改良圈算法求得一个较好的初始种群。即对于初始圈，交换与之间的顺序，此时的新路径为：记 ，若 ，则以新的路经修改旧的路经，直到不能修改为止。(3)目标函数目标函数为行遍所有收集点的路径长度，适应度函数就取为目标函数。我们要求根据题目要求，这里两点之间的距离为距离：(4)交叉操作我们的交叉操作采用单点交叉。设计如下,对于选定的两个父代个体，我们随机地选取第个基因处为交叉点，则经过交叉运算后得到的子代编码为 和,的基因由的前个基因和的后个基因构成,的基因由的前个基因和的后个基因构成，例如：设交叉点为第四个基因处，则交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。(5)变异操作变异也是实现群体多样性的一种手段，同时也是全局寻优的保证。具体设计如下，按照给定的变异率，对选定变异的个体，随机地取三个整数，满足，把之间（包括和）的基因段插到后面。(6)选择采用确定性的选择策略，也就是说选择目标函数值最小的个个体进化到下一代，这样可以保证父代的优良特性被保存下来。 基于上述遗传算法原理，通过编程，可以得到最短路径的分布情况，见图1。图1 最短路径的分布图4.2.2 考虑垃圾车最大载重量及车库工作区间的最短路径分布 在不考虑垃圾车最大载重量和车库工作区间的情况下，求得最短路径后，这里将垃圾车的最大载重量的因素考虑进去，暂时仍然不考虑车库的工作区间，用一辆垃圾车按照上述的最短路径，从车库出发开始收运垃圾，当垃圾车内收集的垃圾接近或达到200，但剩余载重量又小于下一站点垃圾量的时候，垃圾车开往垃圾中转站，在中转站卸下所有收运的垃圾后，再到下一站点继续收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。 基于上述思路可以得到考虑垃圾车最大载重量的最短路径分布，见表11。表11 最短路径路线分布表0155196207198200209204203183134169133165881431921319510111198246270247218250276/1/217252210243245223232233235275269226262257254237271272251253230/1/249259231274248224227214229261220238234215260239225228265222213256267221/1/241219242236273216258263268266240264255822441391571022141216/1/61827175127202123234208189205202190187201185/1/1942061842111951991911938548386142306460376571848056584476532962/1/59915533635750242868904725815135416731755439/1/4977527932702646746673348336457872406943188182212197186108105135124/1/166161921201251731421581541521171711531681309897991211598917810914810017218187146132175/1/8612913816017611393126177163106119103136112180149147115139140/1/1041231451411101111371741571511701221071649611616710211814412815016217915611494/1/0 根据最短路径分布表，可以得到图2图2 考虑垃圾车最大载重量的最短路径分布从上图可以看出，由于整个垃圾收运途中，垃圾车共计需要到中转站11次卸垃圾，因此，最短路径的路线被分成相对独立的11个子路线，根据各点的坐标，可以求出最短路径的总路程为479.6992，垃圾车在各收集点收集垃圾和11次到达中转站卸载垃圾的工作时间共计为8.2153小时，垃圾车的行车速度为40，可以得到总时间为：479.6992/40+8.2153=20.2078(小时) 由于车库的工作区间为9小时，同时出于实际情况的考虑，在满足目标和条件的前提下，所用车辆越少越好，而且，车辆的增多使最后从中转站到车库段增多，导致总路程变长，因此需要至少三辆垃圾收运车才能在车库的工作区间内将垃圾全部运往中转站。根据垃圾收集点的分布图不难看出，所有收集点大致分为比较独立的三块区域，这里从左至右依次称为西区、中区和东区。中区和东区距离中转站距离大致相近，而西区距离中转站则相对较远。由于垃圾车需要11次到中转站卸载垃圾，三辆车无法平均分配，由于西区路程较远，因此将经过西区的到中转站的3个子路线分配给一辆车清运，其余8个子路线平均分配给另外两辆车。基于上述思想，这里先以三辆车进行垃圾清运，若能满足车库工作区间，则为可行解，若仍然超出车库的工作区间，则以四辆车进行垃圾清运来计算。三辆车从车库出发后，分别从155号收集点、241号收集点、49号收集点开始收集垃圾，收集路线见图3。图3 三辆车的垃圾收运路线通过计算可以得到，三辆车进行垃圾清运的路程分别为：154.9591、173.8447、159.6432；在各收集点和中转站收集和卸载垃圾花费的时间分别为：2.2292小时、2.9514小时、3.0347小时；进而可以求出三辆车清运垃圾的总时间分别为6.1031小时、7.2975小时、7.0258小时。则运行的总路程为488.4470，工作时间为三辆车工作时间的最大值7.2975小时。 4.2.3 模型改进通过上图可以很明显地看出，尽管模型开始建立时使用一辆车行遍各个点，采用的是全局最优解，但是将路线分配给三辆车行走时，不应定能够满足局部最优。从结果也可以看出每辆车工作的时间差距达到1个小时左右，没有将工作量平均的分配给三辆车执行，导致整个系统工作时间变大。因此，需要对模型进行改进。在模型改进之前，这里需要对距离的应用做出进一步的解释：距离的定义是为：如上图所示，若按欧式距离计算，,很显然得到，但是若按距离计算，可以得到如下关系，,，则有：根据问题二的实际情况，以及距离的性质，如果点为任一收集点，点为车库，点为中转站，则可得到如下结论：由车库出发到达任一收集点，最后再从中转站返回车库，该距离即等于从中转站直接到达收集点的距离。而模型改进的关键就在于能够将11条子路线均衡的分配给三辆车去走，分配的前提条件就是这11个子路线必须是相同情况下的，也即是起点和终点相同。根据上述距离的性质，这里假设所有11个子路线的起点和终点均为中转站，这样11个子路线的相关量就可以在同等条件下进行计算了。为了能够将11个子路线进行量化，这里综合考虑各个路线的长度和每个节点花费的时间，由于车辆进行匀速行驶，因此可以将路程化为等效时间，即将路程除以速度。这里给出11个子路线所经历收集点的起始点和结束点，见表12表12 11个子路线所经历收集点的起始点和结束点子线路收集点坐标坐标线路1起始点155-48472384183012结束点276-48764844197661线路2起始点217-48781984198208结束点230-48747624200997线路3起始点249-48749394199870结束点221-48698634199883线路4起始点241-48698064199873结束点16-48622054203990线路5起始点6-48615214203864结束点185-48410614200332线路6起始点194-48404234199203结束点62-48220124213081线路7起始点59-48201584213154结束点39-48194704210260线路8起始点49-48176884209915结束点124-48384404197237线路9起始点166-48394564195192结束点175-48459574194648线路10起始点86-48461114194774结束点140-48430104193167线路11起始点104-48430074193186结束点94-48399284188044通过计算可以得出每条线路的等效时间，见表13。表13 11个子线路的等效时间（单位：小时）子路线线路1线路2线路3线路4线路5线路6等效时间2.04582.05761.99981.99801.83691.8007子路线线路7线路8线路9线路10线路11等效时间1.66171.76351.69421.69901.6504设表示经过第段线路所花费的时间；为变量，当为1时表示第辆车通过第段线路，当为0时表示第辆车不通过第段线路；表示第辆车通过路线花费的总时间，为三辆车经过所有路线的总时间。建立如下的规划模型：求解结果为：表14 三辆车的线路安排结果结果经过的线路段路线花费总时间第一辆车线路5、线路6、线路7、线路106.998小时第二辆车线路4、线路8、线路9、线路117.106小时第三辆车线路1、线路2、线路36.103小时通过结果可以看出模型经过改进后，结果明显得到了优化。这样，当每辆汽车从车库出发后，由于除起始点外，其他所有子线路均为从中转站出发再回到中转站，顺序对结果没有影响，因此只要找到离车库最近的线路起点作为第一个要走的子线路即可，通过计算可以得出三辆车的子路线起始点，如下：表15 三辆车垃圾收集点的起始坐标第一子路线起点坐标坐标第一辆车86-48461114194774第二辆车104-48430074193186第三辆车155-48472384183012三辆车在收运垃圾的过程中所花费的时间最大值为7.106小时，因此工作时间也是7.106小时，小于车库的工作区间，至此为止，就是垃圾收运路线的数学模型。4.2.4 模型的实用性以及算法的稳定性和鲁棒性由于问题二模型的建立中首先是将模型转换为典型的模型，并且利用遗传算法得到了全局最优的最短路径，同时又根据距离的性质对线路的分类做出合理的假设，模型建立的过程中除系统算法固有误差外，不存在任何假设或简化的认为误差存在，基于上述分析可以看出，模型具有可操作性和实用性，对数据没有特别的要求，最突出的优点是利用遗传算法求得了大规模数据的全局最优解，并且每一步的实现均有相应的程序，可以为以后设计相关的专业软件提供模型和程序支持。问题二在利用遗传算法进行模型全局求解的时候，将种群数设为200，在大规模种群的情况下，可以使算法结果更加趋于稳定。比如，通过五次计算最短路径的路程即可看出，分别是：395068、394860、395880、394076、395450，并且每次计算的耗时仅为40秒左右，因此，算法具有一定的稳定性。算法的鲁棒性，即算法的健壮性，是指控制系统在一定的参数（结构、大小）摄动下，维持某些性能的特性，现代鲁棒控制则着重研究控制系统中非微有界摄动下的分析与设计的理论和方法。本文中要求垃圾的最大载重量为200，但是在求解的过程中，垃圾收运车在去往中转站卸载垃圾之前收运的垃圾量均不超过200，同时剩余量又小于下一收集点的垃圾，11次前往中转站的载重量（单位：）分别为：表16 11次前往中转站的载重量车次第1次第2次第3次第4次第5次第6次载重量194.5186198198195198车次第7次第8次第9次第10次第11次载重量196197198196176在保证尽可能地减少前往中转站次数的前提下，又给每次的运送量保留了一定的稳定裕量，如果某些垃圾收集点的垃圾某天由于特殊原因有一定的增长，也不会改变垃圾运送的线路设计，从这一点可以看出，算法具有较好的鲁棒性。五、模型评价5.1模型的主要优点：1从内在因素、社会因素、个体因素三方面出发，找到了影响城市垃圾年产量的内因；2将多元回归的计算结果、趋势预测结果、实际值进行了对比，凸显了模型的准确性及实用性；3问题二中，采用遗传算法对大数据量的TSP模型进行全局寻优，得出较好的最短路径；4在路程最优的基础上，将每天的工作量平均分配给每一辆车，使垃圾收运时间也尽可能的缩短。5.2模型的不足： 1城市生活垃圾产量的预测和垃圾清运模型的建立，只是针对题目的要求建立模型，并未参考相关专业知识； 2遗传算法中使用的随机数和规划中使用Lingo进行的迭代求解，导致结果有一定的波动性。参考文献1孟繁柱，金志英等，我国城市垃圾产量预测J，环境保护科学，总第120期第29卷：24，2003.12；2王福建，俞传正等，灰色关联分析在道路交通事故中的应用J，中国安全科学学报，第2期第16卷：18，2006.2；3 宋薇，刘建国，聂永丰，城市生活垃圾收运路线优化研究J，环境卫生工程，01期16卷：11-15，2008.220