城市垃圾运输问题——数学建模二等奖(附MATLAB程序代码)

魅魅魅力力力数数数模模模美美美丽丽丽师师师大大大浙江师范大学“同梦杯”第八届数学建模竞赛自信创新合作快乐AB√论文题目城市垃圾运输问题编号评分监制：浙江师范大学数学建模研究会（2009年5月7日）（说明：评分一栏为评阅人填写，请参赛者不要填写）城市垃圾运输问题一、摘要通过对垃圾运输问题的具体分析，得出运输车问题应先于铲车问题。运输车利用目标规划模型，运用计算机随机搜索方法得出了12条分路径，考虑实际情况优化成11条分路径。在铲车问题中将11条线路用数学方法模拟成11个加权点，构造恰当的有向或无向赋权图，把问题转化成图论中的TSP问题，并利用蚁群算法解决TSP问题,.从而使原问题获得满意的解答。关键词垃圾运输问题，目标规划模型，计算机随机搜索算法，蚁群算法，哈密顿圈，图论中的TSP问题（旅行商问题）城市垃圾运输问题2二、问题重述某城区有37个垃圾集中点，每天都要从垃圾处理厂（第38号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费2元/吨公里；运输车和装垃圾用的铲车空载费用0.5元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3.如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？垃圾点地理坐标数据表坐标(km)坐标(km)序号站点编号垃圾量Txy序号站点编号垃圾量Txy111.503220151.40199221.501521321.20225330.755422221.80210441.204723231.40279560.850824241.601519651.3031125251.901514771.207926261.002017882.309627272.002113991.4010228281.00242010101.8014029292.10251611111.1017330301.20281812122.7014631311.9051213131.8012932211.30171614141.80101233331.6025715200.6071434341.2092016161.5021635351.5091517170.8061836362.30301218181.50111737371.7081019190.90151238380.0000表格1城市垃圾运输问题3三、引言对于求解n个城市的TSP问题，存在（n-1）！条闭合路径的排列方案，因此TSP问题是一个典型的NP完全问题。对于这类问题很难用全局搜索法精确地求出其昀优解，因此研究相应的有效算法寻找其昀优或近似昀优解具有重要的理论意义，另外，很多实际实用的问题，如印刷电路板的钻孔路线方案、连锁店的货物配送路线等经过简化处理后，均可建模为旅行商问题，因此对旅游商问题求解方法的研究也具有重要的实用价值。目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、神经网络算法、二叉树描述算法，蚁群算法是求解此类NP完全问题的一种比较有效的方法。四、符号含义|A|表示A点到原点的距离，恒正|B|表示B点到原点的距离，恒正|A-B|表示A,B两点之间的距离,恒正Ta表示A点所在地的垃圾量装的足够多运输车当前的载重离限载不大于0.6吨(垃圾点的昀小垃圾量)Zcost载物费用Kcost空载费用Allcost总费用分路径在车辆运输过程中，需要在一次内一起完成垃圾运输的点的连线所构成的路径加权点由分路径模拟成的可以替代原分路径计算的点五、模型分析（一）模型的假设1．假设运输车、铲车数量不受限制。但每个垃圾站点的垃圾只能由一辆运输车运载。2．车辆的运行状况和路线都设为理想状态，即始终保持已知条件情况。3．街道设为理想状态，即行车线路无需考虑街道影响。4．垃圾设为理想状态，即在运输过程中无新垃圾入站；在垃圾车到达垃圾站时，垃圾数量已经为题目中给定数量；各垃圾站都能在十分钟内装上运输车。（二）模型建立及算法的原则原则1：运输车昀少原则；原则2：运费昀少原则；原则3：运输车优先于铲车原则；原则4：运输车先远后进原则；原则5：铲车昀少原则；注：以上原则优先级依次降低。城市垃圾运输问题4（三）问题的分析与模型的建立1.分路径的规划垃圾运输问题昀终可以归结为昀优路径搜索问题，根据具体问题设计出计算机随即搜索法，可以搜寻到令人满意的可行解。得出搜索的基本原则：（1）先后顺序并不影响所需的时间。而“先远后近”可以省出车载着B点的垃圾奔到A点再返回B点即1.8*|A-B|*2*Tb这部分的钱，所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多所以一般情况下，不采用单独运输。（2）车在装的足够多的情况下应该直接返回原点（38点）；（3）每一次布局和每条线路的搜索从剩下未搜点中的昀大值开始。（4）在垃圾车的剩余载物量小于垃圾点垃圾量的昀小值0.5时，由于对于下一垃圾点(假设为A点)内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的，等于1.8*Ta*，因此|A|车是直接返回38点更合理。2.铲车路径的规划铲车调配问题可以转化为图论中的TSP问题，先用一辆铲车求解昀优路线。已知n个垃圾集中点之间的相互距离，现有一辆铲车必须驶遍这n个垃圾集中点，并且每个垃圾集中点只能访问一次，昀后又必须返回出发垃圾集中点。如何安排他对这些垃圾集中点的行进路线，可使其路线的总长度昀短。用图论的术语来说，假设有一个连同无向图G=(V,E)，其中V是顶点集，E是边集，设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有昀短距离的回路，即昀佳哈密顿圈或H圈。这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1=t1，则旅行商问题的数学模型为：minl=σd(t(i),t(i+1))（i=1,…,n）旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与垃圾集中点数目n是成指数型增长的，所以一般很难精确地求出其昀优解，本文采用蚁群算法求其近似解。（四）模型的求解1.在不考虑铲车的情况下首先根据题所给的数据画出散点图（点的坐标及编号是按照题目中所给的坐标和序号进行标注）城市垃圾运输问题5图表1由于载物费用仅和各站点到原点的路程有关，且运输车单位路程单位质量的运费为常数，所以载物费用恒定，zcost=2639.30。程序见代码1。建立目标规划模型，运用计算机随机搜索方法得出了12条分路径。利用MATLAB画出12条路线图。程序见代码2。图表2得出结果后，我们结合实际操作对结果进行分析。发现将38-1和9-12两条分路径中1，2两点连接，将12条线路合并成11条分路径，如下图所示城市垃圾运输问题6图表3线路时间1时间2总时间/小时13029272.301/22.8022826322532.205/63.0333623332.101/22.604241835151.702/32.37534171651.452/32.1262011101.401/21.907191381.351/21.85821221.351/31.6891437741.102/31.771012911.001/21.501131620.851/21.350.0016.806.1722.97表格2得出运营总费用为：2639.30其中运输费用是2807.30空载费用为168。程序见代码3。2.在加入铲车后下面用数学方法证明上一步骤中的条分路径可以模拟成加权点。令某条分路径上有n个点，分别为（X1，Y1），（X2，Y2）……（Xn，Yn）,这n个点在路径上依次排列，不妨设X1X2X3……Xn。起点为（X0,Y0），终点为（Xn+1,Yn+1）,起点，终点都在路径外。设Sk为点（Xk，Yk）到点（Xk+1,Yk+1）的距离，S0为起点（X0,Y0）到（X1，Y1）的距离，Sn为（Xn，Yn）到终点（Xn+1,Yn+1）的距离。S0=|X0-X1|+|Y0-Y1|;S1=|X1-X2|+|Y1-Y2|;城市垃圾运输问题7S2=|X2-X3|+|Y2-Y3|;……Sn-1=|Xn-1-Xn|+|Yn-1-Yn|;Sn=|Xn-Xn+1|+|Yn-Yn+1|；总距离S=S0+S1+……+Sn-1+Sn=|X0-X1|+|X1-X2|+|X2-X3|+……+|Xn-1-Xn|+|Xn-Xn+1|+|Y0-Y1|+|Y1-Y2|+|Y2-Y3|+……+|Yn-1-Yn|+|Yn-Yn+1|=|X0-X1|+X1-X2+X2-X3+……+Xn-1-Xn+|Xn-Xn+1|+|Y0-Y1|+Y1-Y2+Y2-Y3+……+Yn-1-Yn+|Yn-Yn+1|=|X0-X1|+X1-Xn+|Xn-Xn+1|+|Y0-Y1|+Y1-Yn+|Yn-Yn+1|=|X0-X1|+|Y0-Y1|+|Xn-Xn+1|+|Yn-Yn+1|+X1-Xn+Y1-Yn令此路径上的n个点的重心为（X,Y），X=(X1+X2+X3+……+Xn)/n；Y=(Y1+Y2+Y3+……+Yn)/n；起点（X0,Y0）到重心（X，Y）的距离为：Sa=|X0-X|+|Y0-Y|=|X0-(X1+X2+X3+……+Xn)/n|+|Y0-(Y1+Y2+Y3+……+Yn)/n|；终点（Xn+1,Yn+1）到重心（X，Y）的距离为：Sb=|Xn+1-X|+|Yn+1-Y|=|Xn+1-(X1+X2+X3+……+Xn)/n|+|Yn+1-(Y1+Y2+Y3+……+Yn)/n|；路径长度为：L=|X1-Xn|+|Y1-Yn|；数学模拟总路径长度为：S·=Sa+Sb+L=[|X0-(X1+X2+X3+……+Xn)/n|+|Y0-(Y1+Y2+Y3+……+Yn)/n|]+[|Xn+1-(X1+X2+X3+……+Xn)/n|+|Yn+1-(Y1+Y2+Y3+……+Yn)/n|]+[|X1-Xn|+|Y1-Yn|]又经过计算机数据模拟，|Xn-Xn+1|+|Yn-Yn+1|+X1-Xn+Y1-Yn≈[|X0-(X1+X2+X3+……+Xn)/n|+|Y0-(Y1+Y2+Y3+……+Yn)/n|]+[|Xn+1-(X1+X2+X3+……+Xn)/n|+|Yn+1-(Y1+Y2+Y3+……+Yn)/n|]；所以，S≈S·。命题得证。此重心就称为此路径的加权点。将11条分路径用数学方法模拟成11个加权点，如下图所示。程序见代码6。城市垃圾运输问题8图表4根据程序求出的铲车昀短路径图：程序代码见代码7。图表5通过程序，我们找到了铲车的昀短路程图（昀佳哈密顿圈），见表5，即为8→3→1→2→4→5→11→9→7→10→6。根据运输车需要数是6辆，由原则5及运输车和铲车的时间安排，分析知需要6辆铲车。根据铲车循环工作思路，分析易知5辆铲车进行循环，一辆铲车，只在一条路径上，每天进行一个来回的工作。城市垃圾运输问题9根据距离昀短原则（此处原则是，这条路径的起点到上一条路径的终点与这条路径的终点到下一条路径的起点的距离和昀短），我们找出了路径2，同时我们考虑到路径2只与1辆运输车一一对应，分析知路径2即为昀佳结果。让此路径上有一辆铲车每天进行一个来回的工作。于是，得到新的昀短路程图8→3→1→4→5→11→9→7→10→6。我们又用了相同程序代码见（代码7）进行了计算得到结果如下。考虑实际情况，去掉点2后的铲车路线图图表6