2011三峡大学大学生数学建模竞赛

1、姓名：刘鹏学号：2010142124学院:理学院专业：电子信息科学与技术深圳市南山区垃圾运输问题研究摘要随着城市人口的增加，城市建设规模不断扩大，生活垃圾的数量日益增多，分布更广，垃圾问题逐渐成为人们关心的一个严峻的社会问题，急需得到解决。 城市生活垃圾从收集、运输、中转到处理，构成了城市生活垃圾的处理系统1。据统计，处理系统费用的75%85%2归因于收集和运输（简称收运），即生活垃圾收运系统。而随着垃圾处理设施的向远离城市的远郊转移，市区面积的扩张，整个垃圾收集运输系统的覆盖面积越来越大，对车辆收运垃圾的路线进行科学合理的规划，就显得尤为重要。在生活垃圾收运系统中，收集清运工作的科学性、经济

2、性关键就是选择合理的收运路线。选择合理的垃圾收运车辆的路线，可减少行驶距离，节约时间，可高效地调度收运车辆，减少投入车辆数，车辆的维修费用、燃油费也相应减少。同时，人力资源也可发挥更大的效率。因此，通过对垃圾收运车辆行车路线的优化，可以很大程度地节省收运费用,从而产生巨大的经济和社会效益。就生活中垃圾运输的问题的调度方案予以研究。问题一清运路线中，垃圾清运路线优化垃圾物流具有“产生源高度分散、处置高度集中、产生量和品质随季节变化”的特点通过对问题的分析和合理的假设，（1）对垃圾从中转站运到处理中心的过程运用图论知识建立动态规划模型，并确定大小型设备的分布。然后获得既环保又经济的运送方案。（2）

3、对于转运站的重设，可采用动态规划模型进行分析。关键字：运输车调度 非线性规划 最大利益 图论 分布 （一）问题重述：在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：1）橱余垃圾可以使用脱水干燥处理装置，处理后的干物质运送饲料加工厂做原料。不同处理规模的设备成本和运行成本（分大型和小型）见附录1说明。2） 可回收垃圾将收集后分类再利用。3） 有害垃圾，运送到固废处理中心集中处理。4）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，

4、不产生经济效益。-本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：1） 假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。以期达到最佳经济效益和环保效果。2）假设转运站允许重新设计，请为问题1）的目标重新设计。 仅仅为了查询方便，在题目附录2所指出的网页中，给出了深圳市南山区所有小区的相关资料，同时给出了现有垃圾处理的数据和转运站的位置。（二）问题分析对于问题一的清运路线问题、路线运输车调度方案的设计，不能仅仅考虑使运输车的行

5、走路线最短，因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使得所有运输的花费最少。在建模过程中，我们无需考虑投入的运输车台数，只需对各条路径所花费的时间进行和各运输车载重量约束即可，至于投入的车辆数，在各条路径确定后，最终便可确定投入运输车数量和花费与收益. 对于一中的大小型设备的分布方案，运用图论，从而确定大小型设备的分布，并获得经济与环保的效益。一 模型假设（1）假设南山区人口分为不同部分，每部分人口固定，每天产生垃圾量固定；（2）假设每个小区所有的垃圾都堆在一起；（3）假设各小区的垃圾和中转站的垃圾都必须在当天清理完毕；（4）不考虑运输车在行驶过程中出现的塞车、抛锚

6、等耽误时间的情况；（5）不允许运输车有超载现象；（6）每个小区清运站均位于街道旁，保证运输车和铲车行驶顺畅；（7）所有运输车从中转站出发，最后回到中转站；所有的拖车都从填埋场出发，最后回到填埋场；（8）一天只从收一次垃圾，只从中转站转运一次垃圾；（9）拖车将垃圾一起送往大型设备处和小型设备处再前往坟埋场和焚烧场；（10）所有的橱余垃圾处理设备全部分布在中转站。（11）若中转站的转运垃圾超过60吨（200*3/10）时，建设大型处理设备，其余用小型设备补足或全用小型设备；（12）拖车只负责将不可回收垃圾运往焚烧场和填埋场； 二 模型的建立及求解问题1： 模型一1 符号说明 可将城市生活垃圾收集区

7、域看成一个网络，其中垃圾收集点和街道分别表示网络的顶点和边。如果两个垃圾收集点由一街道相连，则用边把这两点连接起来，表示这两点是相邻的。在连通图G=(V,A)中，有n+1个顶点（|V|=n+1），表示车库、垃圾收集点和中转站。顶点1表示车库，点n+1表示中转站。其余顶点，即U=V1,n+1,表示垃圾收集点。弧(i,j)（(i,j)A）表示在两个收集点之间的街道。单行街道可通过单方向的弧来表示，双行街道则可以用一对方向相反的弧(i,j)和(j.i)来表示。记：G=(V,A):网络图，表示收集区域；V:点集.顶点1为车库；点n+1为中转站；U=V1,n+1,为垃圾收集点（|V|=n+1）；A:弧集

8、.（i,j）表示在两收集点i和j之间的街道（i,j）A）；GR=(V,AR):需求图，由垃圾收集点及需收集的街道构成；AR:需收集垃圾的街道(ARA)；AAR：重复行驶的街道，穿过时无需收集垃圾；r:行程编号；P:车辆数；（=16）W:车辆载限；：弧（i,j）上的垃圾量（i,j）；:网络中的垃圾总量, ；:弧（i,j）上垃圾收集费用（或时间）（i,j）；:网络中的垃圾收集总费用（或时间），；：重复行驶弧（i,j）的费用（或时间）（i,j）A）， （ , ）；:在图中顶点l的出度(lV), ；:在图中顶点l的出度(lV), ；对于所有需要收集的弧，对弧进行编号，按照弧上的垃圾量由多到少的顺序，则

9、有,若满足：则一次行程收集弧1，弧2，弧l上的垃圾后接近车辆载限无法继续收集。在最优解中，最多需要完成行程的数目，应为需要收集的弧数除以l的整数值，即：,这就是收集行程数的上界值。有P辆车，要形成P个最初行程和P个最终行程。最优解中最多有L个行程，则中间行程最多有L-2P个。令r=1,.,：最初的P个行程；r =P +1,.,2P：最终的P个行程；Lr =2 P+1,.,：中间的L-2P个行程。在第r此行程中收集弧（,j）上的垃圾 否则 ：第r次行程中重复穿过弧（i,j）的次数，r =1,.,L 2 模型的建立21线形回归分析法确定各小区日产垃圾量Y=a0+a1x1+a2x2+amxm。式中：

10、Y 小区每日垃圾预测产生量；xi 为影响垃圾产生的多个因素（i=1，2，m）；ai 为回归系数（i=1，2，m）。影响垃圾产生的因素有很多，如人口数量、工资收入、消费水平、燃料结构等。22 运输车调度方案的模型对于运输车的调度方案，我们建立单目标规划的非线性模型使得运输费用最小，模型如下：2.2.1目标函数的建立约束条件包括了两部分：车辆路线问题（VRP）的约束条件；定义形成L次行程及它们次序的约束。L次行程为：从顶点1到顶点n+1的P个最初行程；从顶点n+1到顶点1的P个最后行程；往返于顶点n+1的不会超过L-2P个的中间行程（环游）。s.t.: (1)(1）式表示进出任一垃圾收集点的次数相

11、同，即网络流中间点的平衡条件：流出量流入量 (2), (3) (4)(2）（4）式定义了从车库到中转站的P个最初行程； (5) (6) (7)（5）（7）式定义了从中转站到车库的P个最后行程； , (8) (9) (10)（8）（10）式定义了往返中转站的L-2P个中间行程； (11) （11）式排除了不包含顶点n+1的行程。即规定了所有的行程都包括顶点n+1（因为最初行程、中间行程、最后行程都要经过顶点n+1）。M为非常大的正数； , (12)（12）式规定一次行程收集的垃圾量不得超过车辆的载限； (13)（13）式表示每一街道上的垃圾必须在且仅在一次行程中被收集。 (14) 为非负整数，

12、（15）通过解上述数学模型,可得到P个往返车库的环游路线，按此路线来调度垃圾收运车辆，垃圾收运费用将最小。2.3 数学模型的分解 为了将垃圾收运车辆路线问题及数学模型理解的更为透彻，下面采用图论里的一些概练和方法，对数学模型的目标函数和约束条件做一些变形。将目标函数分解为两部分，这样垃圾收运车辆路线问题就分成了两个子问题。 令 为在所有L次行程中重复穿过弧（I,j）（i,j）A）的次数。 令在所有L次行程中从顶点i(iV)发出的需收集的弧数和为顶点i的出度，进入顶点i的需收集的弧数和为顶点i(iV)的入度，即： 这样处理后，对模型的约束条件变形。由（1）式得： 由（2）、（5）、（8）式得：

13、由（14）式：因此，由式（13）可得：所以，在可行解中，整数是行程数的下界值。因有P个最初行程和P个最终行程，则为中间行程数的下界。对于任一中间行程，有：由式（10）和（11），因而对所有的L个行程有： 若令： 因这样处理后，目标函数可做如下变形： Min =从而可以得到两个独立的子问题A和B：一个是关于变量，另一个是关于变量的子问题（A）： （A） s.t.: 问题A的解对应的目标函数值为垃圾收集费用，即需收集的街道上的垃圾收运费用。子问题（B）： （B） 问题B的解对应的目标函数为保证行驶的连通性而需重复行驶部分街道的费用。3.拖车调度方案模型的求解表一：各运输路径所包含的小区的中转站站、

14、运输量转运路线运输量139382534353910239333391033931321153910439473539105391937339106392633910739202912391083913291093912391010392273539101139273910123928353910133935397.2143916123910153912391016391353910173915183910183930181439101939621391020392221173910213991239102239101439102339241624391024392336391025393639

15、10问题2: 模型二转运站的合理规划和重建垃圾转运站的建设是为了使垃圾的收集作业和垃圾的最终处理作业之间的运输过程及预处理过程更经济、更有效、更合理。转运站的合理选址，不仅对垃圾转运站功能的发挥、经济效益的提高至关重要，而且对周边的环境、投资的规模等都有重要的影响。对于新规划的城区，因为道路和生活区规划条件较好，人口密度相对较低，可以考虑以小型机动车代替人力收集，这样可以建设覆盖范围广，转运能力大的转运站。转运站的选址可参考本文3.2，转运站的建设规模设计、工艺选择、成本核算、运行效果分析等问题可参考本文第四章内容。规划工作的协调与统一首先，各城区之间、各城区内部要做好垃圾收运工作的协调统一，

16、优势互补，加强区域之间的合作。其次，各城区之间、各城区内部要对转运系统的相同工艺的设备统一标准和规格，使相同转运工艺内的车辆和设备能够互相调用，降低维修难度，避免出现一个转运站一种设备的情况。最后，要做好垃圾收集转运系统的统计工作。要把每一座转运站的垃圾转运量、不同运输车辆的运输次数、垃圾的收集和运输距离和系统运行过程中产生的各种费用按时进行统计，以便于分析和改进。一、转运站的数量以及规模的确定按照口J27一2005城镇环境卫生设施设置标准，垃圾转运站的设置数量和规模取决于收集车的类型、收集范围和垃圾转运量。1.转运站数量的决定因素小型垃圾转运站服务半径不应超过23公里。当垃圾转运距离超过20

17、公里时，应设置大、中型转运站。当服务区平均运距大于30公里且垃圾量较大时，宜设置大型转运站。采用人力方式(三轮车、两轮板车等)进行垃圾收集时，收集服务半径不应超过1.0公里。采用小型机动车辆(有效载荷1一4吨)；进行垃圾收集时，收集服务半径不应超过5.0公里。采用中型机动车辆(有效载荷58吨)进行垃圾收集运输时，可根据实际情况调整服务半径。一般情况下，中型机动垃圾收集车均兼有压缩功能，可不经过转运直接将垃圾从收集点运往处理厂。当垃圾处理设施距垃圾收集服务区平均运距大于30公里且垃圾收集量足够大时，宜设置大型的二级转运站。目前，一般中小城市的垃圾主要是以人力车收集，转运站之间距离在2公里之间，意

18、味着最少每2公里就应设置一座转运站，都属于小型转运站。2.转运站规模的确定垃圾转运站可按其规模划分为大、中、小型或I、11、m、W、V五类。中小城市的大多数的转运站规模都在每日50吨以下，不到一百平米，其规模与大城市的垃圾收集房类似。 3.垃圾转运站的设计规模垃圾转运站的设计规模应以服务区域垃圾收集量为基础，并综合城市季节及经济变化特点考虑，具体计算公式如下: 其中: 一转运站的规模(吨/天); 一服务区日均垃圾收集量(吨/天); 一垃圾量变化系数，一般应按当地实际资料采用，无资料时，一般可取1.30一1.50。日均垃圾收集量数据，可按下式估算:式中:n一服务区内服务人数;q一服务区内人均垃圾

19、排放量(公斤/人天)，一般按当地实际资料采用，无资料时，可取0.8一1.2。4.垃圾产生量预测其中:p(t)为t时刻人口总量(万人); 为当前人口总量(万人);M为环境容量(万人);r为人口自然增长率。垃圾产生量预测模型依据垃圾的人均产生量和预测的服务人口数量，确定垃圾产生量即:其中: 为t时刻的垃圾产生量(吨)。 结语：城市垃圾收运费用在整个垃圾处理系统总费用占据很大的比例，分析研究收本具有现实意义。通过对垃圾收运车辆路线优化问题的研究，可有效完成垃圾清运的车辆行程，节省收运时间，可高效力的调度车辆和劳动力资源，从而降低收运成本。城市生活垃圾收运系统包括收集，运输和中转三个部分，根据是否设置

20、中转，将收运方式分为有中转收运模式和无中转收运模式。当设置中转时，车辆将收运的垃圾送往中转站，再由更大型的车辆将中转站垃圾送往垃圾处理厂；当没有设置中转时，车辆直接在收集区域与填埋场往返，这种车辆一般是具备压缩功能的中型车辆。对垃圾收运系统的概况归纳总结后，本文提出了垃圾收运车辆的路线问题。参考文献：【1】 盛金良，曹春华.城市垃圾收运模式设计【J】环境卫生工程，2008，8；【2】 刘东，垃圾收运系统规划设计的分析【J】.环境卫生局，2003,12【3】 王志刚，陈新庚等.城市垃圾小型转运设施设置实例研究【J】.环境卫生局，2000,2.【4】 陈炳禄，王志刚，陈新庚.广州市生活垃圾处理方式

21、及物流管理方案优化【J】，上海环境科学院，2000，19.【5】 聂永丰.三废处理工程手册 固体废物卷【M】.北京：化学工业出版，2000,136148【6】 刘通武，刘兆龙.线性规划在城市垃圾运输中的应用【J】.环境卫生工程，1996，（2）:227.附录1：垃圾转运站分布图：，对应程序如下：x=6.4042 7.9062 9.8938 10.1240 8.3632 8.8527 8.7659 9.7719 9.6635 9.1549 8.7021 8.5506 8.7425 10.9469 10.5163 9.8772 10.0237 9.2436 12.1417 11.6274 10.9747 12.6839 13.6559 12.7668 12.0305 10.7471 11.2476 10.6522 11.6475 12.1625 12.5870 10.6552 10.3136 9.9479 11.3776 9.0870 13.7566 14.6978 13.9476;y=0.9724 1.2110 0.9621 1.3547 3.0333 3.4680 3.8064 3.3987 3.9132 4.2926 4.5700 4.9595 5.4293 3.6536 4.3899