《数学建模论文城市生活垃圾管理问题研究.doc》由会员分享，可在线阅读，更多相关《数学建模论文城市生活垃圾管理问题研究.doc（35页珍藏版）》请在三一办公上搜索。
1、城市生活垃圾管理问题研究摘要：对问题一，本文通过对城市生活垃圾产量自身特征及各种影响因素的系统分析，分别采用多元线性回归分析和灰色预测方法建立了预测模型，并采用该模型对中短期城市生活垃圾产量进行了较为准确的预测。对问题二，将极其复杂的行车问题进行简化，使其变为图论中经典的多人推销员问题，然后对其进行分组，进一步简化为更为经典的哈密尔顿圈求解问题，即货郎担问题。在分组时以车载量为划分依据，采用边界和密集区优先分组的原则，根据坐标的范围先粗略划分为4个区域，并将每一区域用尽可能小的矩形圈定，再精确划分，采用动态线性规划方法，使划分的每一个小区域中的垃圾总量尽量接近最大车载量，最终实现分组，进而运用
2、遗传算法得到最短行程路线。关键词：多元线性回归 灰色预测 哈密尔顿圈 动态线性规划 问题重述随着人类生产和生活的不断发展，由此而产生的垃圾对生态环境及人类生存带来极大的威胁，成为重要的社会问题。而中国目前处置水平低，管理办法不多，更是急待解决的问题。一般认为，城市生活垃圾的影响因素包括地理位置、人口、经济发展水平（生产总值）、居民收入以及消费水平、居民家庭能源结构等等。城市生活垃圾产量是垃圾管理系统的关键参数，因此对未来某段时间内垃圾产量的准确预测是相关垃圾管理的部门做出管理规划的前提。另外，城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收集与运输，这一过程称为城市垃圾的收运。收
3、运过程可简述如下：某城市有多个行政区，每个区内均有一个车库，假设某一车库拥有最大装载量为 w 的垃圾收集车 k 辆，并且该区的垃圾收集点（待收集垃圾的点）有 n个，该城市共有垃圾中转站 p 座。每天 k 辆垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。以上收运过程均在各点的工作区间之内完成。（注：必须在收集点的工作区间之内，垃圾车才能在该点收集垃圾。）问题：1. 查阅相关文献，搜集垃圾产量数据，在此基础上建立城市生活垃圾产量中短期预测模型，并且分析模型
4、的准确性和实用性。2. 在收运过程已知下述（1）（2）（3）（4）等条件下，如何安排垃圾收运车的收运路线，使在垃圾收运车的行车里程尽可能的少，或者垃圾收运时间尽可能短？（1）车库和收集点、收集点与中转站、中转站与车库的距离；（2）各收集点每天的垃圾产量；（3）每辆垃圾收运车的最大载荷；（4）垃圾收集点、车库、中转站的工作区间a,b。请给出规划以上垃圾收运路线的数学模型，并设计出有效的算法，针对附录中给出的数据，求解模型。并且对模型的适用性、算法的稳定性和鲁棒性做出分析。参数与说明：垃圾车的最大装载量：200.0 (yards)每辆垃圾车每天的负载总量：2200.0 （yards）每辆垃圾车每天
5、最多经过的垃圾收集点个数：500垃圾车的行车速度：40（MPH, Miles Per Hour）Stop_ID：收集点编号，X,Y分别为该点的坐标，单位：feetEST，LST(Early Service Time, Last Service Time)：该点的工作区间，时间格式为HHMM格式，例如：0800表示早上八点ST（Service Time）：该点收集或者卸载垃圾需要的工作时间，单位:sLoad：该点的垃圾量，单位：yardStop_Type：收集点类型（0:车库，1：垃圾收集点，2：中转站）表中两点之间距离为Manhattan距离:()。模型的假设1、假设每辆车装载时发挥其最大装载
6、能力；2、假设运输车行驶过程中不考虑塞车抛锚或意外事故等现象，忽略运输车行走拐弯的时间，以保证每辆车每天可以达到最大作业时间；3、垃圾点的垃圾必须每天清除完，不允许滞留；4、假定街道方向均平行于坐标轴，只要和坐标轴平行就有路存在；5、垃圾车装载量具有弹性，即最大装载量可在200yards上下波动。符号的说明：线性规划直线：线性规划直线的截距：线性规划直线斜率：第区的横坐标：第区的纵坐标：徐州市生活垃圾产量的预测值：生活垃圾产量的影响因素：生活垃圾产量影响因素的相关系数问题的分析对问题一，系统分析之后可知，垃圾产量既具有与多因素相关联的特征，又有单调递增，非负，变化率不均匀等特征，故可以分别采用
7、白箱和灰箱两种思想进行求解，从而保证了结果不至于过分偏差。对问题二，模型将极其复杂的问题进行简化，忽略车库位置，将模型简化为多人从一点出发经过历遍所有点再回到原点的多人推销问题。接着，再对其进行分组，进一步简化为更为经典的哈密尔顿圈求解，即货郎担问题。在分组时，对于提出的几种方法树枝状法，扇形法和矩形法进行比较，发现矩形法更为稳妥且更容易实现。矩形法首先根据点的密集程度进行粗略分区，并将每一区用尽可能小的矩形圈定，以便划分，采用初级的线性规划方法，以矩阵的方向为斜率，通过位置坐标来划分区域，以车载量为划分依据，采用边界优先和密集区优先的原则，逐步划分出小的区域，进而使用货郎担问题的遗传算法分别
8、求得每组的最佳路线。模型的建立及求解问题1 查找的数据显示，徐州市19992007年城市生活垃圾的产量见表1：表1.1999年2007年徐州城市生活垃圾产量年份199920002001200220032004200520062007垃圾产量（万吨）34.134.635.633.535.436.537.238.339.6城市生活垃圾的产生受到多种因素的影响，包括地理位置、人口、经济发展水平（生产总值）、居民收入以及消费水平、居民家庭能源结构等等，我们从中选取了人口、生产总值、人均可支配收入、社会消费品零售总额、燃气化率五种因素，定量描述如下表所示：表2. 影响生活垃圾产量的因素年份人口（万人）生
9、产总值（亿元）人均可支配收入（元）社会消费品零售总额（亿元）燃气化率（%）199920002001200220032004200520062007107.84113.64115.01116.43118.40119.23120.04121.00122.00603.30658.45730.88794.88905.661095.801212.151360.301501.236498.567147.247616.218036.918954.239839.6510820.0011830.3112961.63161.2185.2202.0223.9235.4342.5396.0432.5486.262.6
10、570.8075.8076.9090.2095.5696.5096.7397.01解决预测问题一般采用灰色预测模型、多元回归模型、逐步回归模型、时间序列分析法等方法，灰色预测模型研究预测对象自身变化过程及发展趋势，多元回归模型与逐步回归模型方法原理类似，都是由多个自变量的最优组合共同来预测或估计因变量，时间序列分析法兼有以上两种思想的模型。考虑到垃圾产生量受多种因素的影响，及其单调性等特性我们采用多元线性回归和灰色理论预测两种方法.方法一. 多元线性回归分析1.1根据上述选取的影响因素，建立多元线性回归数学模型如下： (1)式中，Y为徐州城市生活垃圾产生量的预测值，分别为影响因素的相关系数和变
11、量。1.2将19992005年垃圾产生量与选取的影响因素指标带入式(1)，采用最小二乘法求解模型参数从而获得徐州市垃圾产生量的预测模型： 1.3对预测模型(2) 运用F检验（即方差齐性检验）进行统计检验：查表可得9年5个因变量在F分布表上的临界值 ，而求得的检验统计量，由于，故应否定，即认为变量和、之间的线性相关关系显著。1.4预测结果与分析：表3.垃圾产量预测结果年份199920002001200220032004200520062007预测值34.313034.428034.522534.444835.587436.181137.766938.088739.4676实际值34.134.63
12、5.633.535.436.537.238.339.6相对误差0.00620.00500.03030.02820.00530.0087 0.01520.00550.0033表4.徐州市2008年2016年城市生活垃圾预测值年份200820092010201120122013201420152016垃圾产量（万吨）38.435439.085639.718940.556240.007542.502442.964044.130444.4136图1 20082016年垃圾产生量预测值从图中可以看出，今后9年内，徐州城市生活垃圾产生量仍然逐年上涨。方法二.灰色理论模型2.1对原始数据作一次AGO(acc
13、umulated generating operation)累加生成，目的在于为建模提供中间信息，使原始时间序列的随机性弱化。设时间序列一有n个观察值，通过AGO累加生成新序列其中： 则GM(1，1)模型相应的微分方程为：2.1构造累加数据矩阵和常数向量2.3用最小二乘法求得灰色参数，其中：称为发展灰数；称为内生控制灰数。设为待估参数向量，解得： 2.4将灰色参数带入微分方程，求解微分方程，即可得预测模型：2.5精度检验，利用相对误差均值进行精度检验，若精度达到要求，则可利用所建模型进行预测；若精度达不到要求，则仍需建立修正模型以提高精度，然后利用修改后的模型进行预测。表4.垃圾产量预测结果及
14、误差年份预测值实际值相对误差199934.134.10200033.823234.60.00254032341525200134.512135.60.01081428699312200235.21533.50.07260400073396200335.932235.40.03570803133379200436.664136.50.02495341781306200537.410837.20.02614903011172200638.172738.30.01697667296843200738.950239.60.00362383278027图2年的垃圾产量预测图表5.徐州市2008年2016
15、年城市生活垃圾预测值年份200820092010201120122013201420152016垃圾产量（万吨）39.743540.55341.378942.221743.081643.95944.854345.767946.7 表6、精度检验等级表 相对误差均值0.10.2等级好合格不合格参照精度检验等级表，相对误差均值为0.021486 ABBC，因此可以视为ACAB+BC。所以，若第一个回路在C区域内的话，从车库B出发与从中转站A出发相差无几，故对一辆车来说可以看做从A出发。经计算，C区域内垃圾运完需要4.6775车次（见表n），而估算之后可以看出每天使用四辆车可收送垃圾总量大于每天垃圾
16、产量，且时间充裕，故可以令垃圾车第一个回路全部在C区域内，那么，全部可以看作从A出发最终回到A，进而多辆车所走路线与一辆车所走路线相同，故此问题可以看成从一点出发经过多个回路，遍历所有的点，最终回到原点的问题，即多人推销员问题。B*A*C*我们引入相关定义：定义1 经过图中每个顶点正好一次的圈，称为哈密尔顿圈，建成H圈。定义2 在加权图中，（1） 权最小的哈密尔顿圈称为最佳H圈；（2） 经过每个顶点一次且权最小的闭通路称为最佳推销员回路。简化之后得到的类似于多人推销员问题实际上是货郎担问题的多回路形式，可以通过分组，将多人问题化为单人问题，然后采用经典算法得到最后结果。首先，要对问题进行分组。
17、分组方法一：树枝状分组如图所示，将各垃圾收集点看作图中一个节点，各垃圾收集点之间的路看作图中对应节点间的边，各条路的长度（或行驶时间）看作对应边上的权，于是问题就转化为一个图论问题，即在给定的加权网络图中寻找从给定点A出发，行遍所有顶点一次再回到A点，使得总权（路程或时间）最小。分组方法二：扇形分组图6扇形分组示意图如图所示，以中转站A为圆心画弧得一扇形，将车站及四个垃圾收集点区域皆包含在内，然后将扇形平均分为十一等份，于是将垃圾收集点分为十一组，算出每一个小扇形中所有垃圾收集点的垃圾总量，若之和大于垃圾车的最大装载量，则将此扇形区域中的一部分垃圾收集点归于之和不足垃圾车最大装载量的扇形区域之
18、中，最终使得对于每一个扇形区域，每组垃圾车只需往返一次即可将所有垃圾全部收集完。分组方法三：矩形分组图7矩形分组示意图如图7所示可将垃圾收集点归入4个区域之中，3个收集点密集区和1个分散区，然后通过限定各点的X坐标进行分区（如程序6）。从每个区域中找出中心点，即坐标值为区域内所有点坐标平均值的一点，并与中转站所在的点相连接，画一个两边平行于此连线且能包含区域内所有点的最小矩形，见图7。计算每个矩形内垃圾收集点的垃圾总量，并与垃圾车的最大装载量相比较，可计算出矩形1需要垃圾车往返 2.36次，矩形2需要往返 4.6775次，矩形3需要往返2.745 次，矩形4需要往返 0.88次。表7初步分组各
19、区域垃圾车的往返次数垃圾车最大装载量为200yards，故可以将垃圾总量为200的区域化为一组。于是按照以下原则对四个矩形区域继续分组，使得每组垃圾量尽量接近200.原则1、条件相同的情况下，优先从边界处开始分组，即从整体区域两边的垃圾收集点开始收集垃圾，逐步向中间区域靠拢。原则2、条件相同的情况下，优先考虑收集呈密集分布状态区域的垃圾，再考虑分散区的垃圾收集。原则3、考虑实际情况，实际装载量可以略大于200.遵从以上3个原则，优先收集位于矩形1、3外侧的垃圾收集点的垃圾，此题是先从第一区的外侧开始收集垃圾。第一步：求各区斜率和截距运用线性规划的方法，确定各区的中心和中转站确定的直线的斜率和第
20、一、二区最右端点和第三区的左端点对应的截距 (对应的求解方法在程序7).第二步：对各个区进行精细分组由第一区外侧到内侧，有两次可以装满，剩余74yards量的垃圾和第二区放一块运输。第一区右端点对应的直线为，得到截距，然后给截距增加一个微小的量变为，得到一个新的直线，对进行循环（=0到1000000），取值为1，对于每个都会得到直线方程 ，求落在直线和之间的垃圾总量，使其和最接近200，从而可以得到这些点对应的坐标和收集点编号。 然后用得到的新的截距来计算，用同样的方法计算，使与间的垃圾总量接近200。然后第一区还剩下74yards量的垃圾和第二区放一块运输，只要使第一次运输第二区的垃圾量为2
21、00-70即可。第二区可以有4次满载。剩余的垃圾为10yards和离散区一起运输。第三步：对第三区进行分区从第三区的最左端开始，用第二步同样的方法对第三区分组，由两次是满载的，剩余147yards量的垃圾，和从离散区取出的45yards的垃圾一起运输，离散区的这部分垃圾的取法为：取其左上角离第三区最近的点。最后离散区剩余的131yards和第二区剩余的10yards一起运输。表8分组结果表中精细分组栏的11表示第一区的第一组，离散区为第四区，分为2个组。表中列出各组进行线型规划时的各截距，各组垃圾总量和垃圾站点数。使用遗传算法对分好的组进行排序，最终计算结果如表所示，总共需要运输11次，每列为
22、每次运输要经过的垃圾收集点的编号和对应次序，由假设令起点和终点均为中转站。另，统计计算每组的垃圾量如表所示，可以发现均在上下微小浮动，故此方面误差可以接受。表9每次要运输的垃圾总量表10模型的评价对问题一，本模型对垃圾产量的多因素关联的特征以及自身单调性等特征进行综合分析，采用白箱和灰箱两种思想进行求解，保证了结果不至于过分偏差，使得模型更稳定。计算所得误差足够小，具有准确性，将数据修改之后即可对其他城市进行预测，具备相当的实用性。对问题二将复杂问题简化，对于类似的起点距途径点过远的遍历问题具有适用性，算法采用逐步逼近的方法求得分组界限，对于较小的数据振荡不会产生很大变化，保证了稳定性和鲁棒性
23、。参考文献1、贾玉心. 概率论与数理统计. 北京邮电大学出版社，2005.2、肖位枢. 图论及其算法. 航空工业出版社，1993.3、姜启源、谢金星等. 数学模型. 高等教育出版社，2003.4、周翠红、路迈西等. 北京市城市生活垃圾产量预测. 中国矿业大学报，2003（3）：169171.5、舒莹. 基于灰色预测模型的合肥市城市生活垃圾产量预测. 环境科学与管理，2007（9）：58.6、汪浩、吴克等. 合肥城市生活垃圾产量预测研究. 技术经济，2007（2）：9698.附录程序代码问题一程序代码% 1999-2007年数据% Y垃圾总量（列向量）Y=34.1,34.6,35.6,33.5,
24、35.4,36.5,37.2,38.3,39.6;% 1999年数据X1=107.84,603.30,6498.56,161.2,62.65;% 2000年数据X2=113.64,658.45,7147.24,185.2,70.80;% 2001年数据）X3=115.01,730.88,7616.21,202.0,75.80;% 2002年数据X4=116.43,794.88,8036.91,223.9,76.90;% 2003年数据X5=118.40,905.66,8954.23,235.4,90.20;% 2004年数据X6=119.23,1095.80,9839.65,342.5,95.
25、56;% 2005年数据X7=120.04,1212.15,10820.00,396.0,96.50;% 2006年数据X8=121.00,1360.30,11830.31,432.5,96.73;% 2007年数据X9=122.00,1501.23,12961.63,486.2,97.01; X=X1;X2;X3;X4;X5;X6;X7;X8;X9;% y_1为Y的平均值Y_1=mean(Y);% X_i为Xi列的平均值X_1=mean(X(:,1);X_2=mean(X(:,2);X_3=mean(X(:,3);X_4=mean(X(:,4);X_5=mean(X(:,5);X_i=X_1
26、,X_2,X_3,X_4,X_5;X_i=mean(X_i);% 求正规方程L矩阵L=zeros(5,5);for(i=1:5) for(j=1:5) L(i,j)=sum(X(:,i)-X_i(i).*(X(:,j)-X_i(j); endend% 求L0L0=zeros(5,1);for(i=1:5)L0(i,1)=(Y-Y_1)*(X(:,i)-X_i);end% 求矩阵BB=inv(L)*L0b0=Y_1-X_i*B;% 回归方程Y_1=b0+X*B;% 线性相关的假设检验% S总偏差平方和S=sum(Y-Y_1).2);% U回归平方和U=sum(Y_1-Y_1).2);% Qe剩余
27、平方和Qe=sum(Y-Y_1).2);% F检验假设的检验统计量n=9;m=5;F=(U/m)/(Qe/(n-m-1);Bb0F问题二程序代码程序1 所有数据d=2-48482604201545024002561;3-48463954201227024002541;4-48463284201235024002541;5-485475441986490240075241;6-48615214203864024002581;7-48620474207026024002581;8-48615534192666024002541;9-48625804207287024002561;10-486321
28、34206332024002581;11-485722741901170240050161;12-48621754204004024002541;13-486295542077950240050121;14-486218942040070240050161;15-48620854207033024002581;16-48622054203990024002561;17-48551114199314024002541;18-48550764199511024002561;19-48572354190535024002521;20-48542594198567024002531;21-485473
29、14201494024002581;22-48632594204176024002561;23-485339242015900240050161;24-48191704213811024002531;25-48166184213194024002581;26-48188964207372024002531;27-48550774199507024002541;28-48173744212560024005081;29-48236004213764024002541;30-48219664207961024002561;31-48197644210496024002541;32-48187364
30、207335024002521;33-48196934213065024002581;34-48203094207240024002561;35-48156264212217024002581;36-48207134207719024002561;37-48222044209547024002531;38-48245244208444024002521;39-4819470421026002400175201;40-48236184203685024002541;41-48145044211921024002561;42-4822585420807102400100261;43-4825990
31、4203924024005041;44-48244004213884024002541;45-48207304207127024002541;46-48193144207459024002561;47-48168654211977024002541;48-48252734208561024002541;49-4817688420991502400125241;50-4819493421577602400100241;51-48160564212316024002561;52-48185114207269024002521;53-48236404213752024005081;54-481974
32、64210491024005081;55-48198374213112024002541;56-48242304211143024002531;57-48194904215795024002581;58-48247134213096024002541;59-4820158421315402400200321;60-48225144208588024005081;61-48225824208090024002561;62-482201242130810240075121;63-48192644213397024002561;64-48218964208408024002541;65-482247
33、24210394024002541;66-48195864207514024002561;67-48171964210041024002531;68-48170724212503024002561;69-48251624204443024005061;70-48189014207353024002541;71-48224604210465024002581;72-48235094204299024005081;73-48200024207600024002561;74-4819372420745102400175281;75-48197654210494024002581;76-4823950
34、4213825024002531;77-48176204207807024002541;78-48231984206156024002541;79-48187414207316024002581;80-482380842113910240050161;81-48161564212317024002581;82-48677654210352024002561;83-48203134207219024002561;84-48224794210468024002561;85-48258504205260024002541;86-48461114194774024002581;87-484585341
35、963390240025181;88-48475824188405024002581;89-48456554197482024002561;90-48170724212503024002561;91-48198884213122024002581;92-48408424194908024002581;93-48460124190696024002541;94-483992841880440240050101;95-48472054190510024002561;96-48381054194452024002581;97-48449784199034024002531;98-4844953419
36、8338024002531;99-48449904199071024002541;100-484419541954870240050361;101-48472244190513024002561;102-48372494194484024002531;103-48456884192594024002581;104-48430074193186024002581;105-48366714196264024002541;106-484440841915120240050121;107-48385204193003024002531;108-48353274196696024002561;109-4
37、845195419686302400100161;110-48412344193466024002581;111-48414994192917024002541;112-48454804193780024002531;113-48465604190997024002541;114-48399504189363024002541;115-48438164193906024002581;116-48377544194394024002531;117-48432354198247024002521;118-4837153419315202400100281;119-48444734192168024
38、002561;120-48412854195194024002541;121-48452434198913024002541;122-48387634193064024002531;123-48428324194108024002581;124-48384404197237024002541;125-48413034195202024002541;126-48460184190665024002541;127-48542274197174024002541;128-48365614193068024002531;129-48461464193509024002541;130-484415441
39、98225024002531;131-48472394189268024002561;132-48459514194647024002581;133-48449804188035024002561;134-48468654187848024002581;135-48365334196928024002581;136-48458654192811024002561;137-48412884192729024002541;138-484615941935110240025181;139-48434714193847024002581;140-48430104193167024002561;141-48422734195152024002561;142-48430674196960024002531;143-4847910418887002400754.51;144-48371284193167024002531;145-48424304195198024002531;146-48459674195662024002531;147-48438134193925024002541;148-484437141959300240
