2008年校“希望杯”数学建模竞赛赛试题及参考答案

1竞赛试题：垃圾运输问题某城区有26个垃圾集中点，每天都要从垃圾处理厂（第27号节点）出发将垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为35公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1.由于人力成本与车辆购置成本较大，垃圾处理场希望用尽可能少的车来完成任务。请就本题所给数据，确定需要车辆数。2.在问题（1）的前提下，确定运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）3.如果有载重量为4吨、6吨、8吨三种运输车，问题（1）、（2）有何变化？垃圾点地理坐标数据表序号站点编号垃圾量T坐标(km)序号站点编号垃圾量T坐标(km)xyxy111.503215151.40199221.501516161.20225330.850817171.601519441.3031118181.601514551.207919191.002017662.309620202.002113771.5014021212.102516881.1017322221.202818992.5014623231.9051210101.80101224241.6025711110.6071425251.2092012121.5021626261.5091513131.50111727270.000014140.8015122垃圾运输问题的数学建模（2008年校一等奖作品，没有标准答案，以下方案供参考））摘要垃圾的收集、转运和运输问题是垃圾收运的重要环节，是城市垃圾管理系统的重要组成部分，随着城市垃圾处理成本的增加，垃圾运收的统筹优化安排日益重要。该题目就是考察垃圾运输运营成本的优化问题。本文根据题目要求，运用多目标规划（VMP）模型，分别求解出了同吨位的运输车，不同吨位的运输车及铲车的最优调度方案，而且绘制出了直观图。并且结合题目要求与实际情况，对现有的垃圾集中点分布进行了优化合并。首先，将题目所给的垃圾站点坐标表格转换成站点位置坐标图，根据题目要求与实际情况做出一些合理的假设。然后，根据题设、点的位置、所做假设以及逻辑性的推导归纳出几点最基本的确定路线的原则。然后，在针对问题（1）提出的VMP模型中，确立运营费用的目标函数，以及时间约束、载重量约束、路线约束条件。由此，运用MATLAB软件求解出了6吨位运输车最优调度方案：11个车次，6辆车交替轮流担任各运输任务，共用22.12小时，总运营费用2339.17元。问题（3）的解决是在模型Ⅰ的基础上，增加两个车辆调度原则：吨位大的车优先与吨位小的车收尾原则，并相应改变载重约束条件提出模型Ⅱ而完成的。所求得的可变吨位运输车调度方案是：8个车次，其中8吨位的5车次，6吨位的2车次，4吨位的1车次，共用19.2小时，总运营费用2315.6元。针对问题（2）提出的模型Ⅲ是在模型Ⅰ的基础上，对铲车做出合理的假设。因为这些假设，再加上铲车不存在重载问题，所以此问求铲车最少运营费用可以转化成求满足时间约束条件的最小行走路径问题。由此统筹安排出了4辆铲车，共用15.9小时，总运营费用158.4元。而且，我们还拟列了一张车辆时间安排表，以更好更直观的指导工作实践。最后，为降低运营费用，我们综合优化了垃圾运输路线。将同属于一个圆周的几个站点进行合并，根据圆半径的不同值算出了不同的合并方案下的的运营费用。但是最终我们选择了折中的方案，因为考虑到实际生活中垃圾集中点确立有其他许多的影响因素。此外，还对模型进行了全面的评价，认为模型具有可信度高、简单易懂的优点，但它的最大的缺点是过度追求费用最小化，有一些偏离实际。1.问题重述和分析31.1问题重述某城区有36个垃圾集中点，每天都要从垃圾处理场（第37号节点，坐标（0，0），垃圾量为0）出发将垃圾运回。现有一种载重6吨的运输车，其运行平均速度为40公里/小时（晚上运输，不考虑堵车现象）；每辆车每日平均只能工作4小时。每个垃圾点需用10分钟的时间装车。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；假定街道方向均平行于坐标轴。求解最佳运输调度方案及计算程序。问题：（1）需要投入几台运输车，每台车的调度方案，运营费用（2）需要投入几台铲车，每台铲车的行车路线，运营费用（3）如果有载重量为4吨、6吨、8吨三种运输车，又应该如何调度？（4）讨论对现有的垃圾集中点的可行性合并措施，以降低运营费用？已知运输情况及车辆使用性能状况：运输车载重量：6吨运输车平均速度：40公里/小时运输车重载运费：1.8元/公里运输车空载及铲车费用：0.4元/公里每台车每日平均工作时间：4小时每个垃圾点需装车时间：10分钟已知垃圾点地理坐标图：1(3,2)2(1,5)3(5,4)4(4,7)6(0,8)5(3,11)7(7,9)8(9,6)9(10,2)10(14,0)11(17,3)12(14,6)13(12,9)14(10,12)20(7,14)16(2,16)17(6,18)18(11,17)19(15,12)15(19,9)32(22,5)22(21,0)23(27,9)24(15,19)25(15,14)26(20,17)27(21,13)28(24,20)29(25,16)30(28,18)31(5,12)21(17,16)33(25,7)34(9,20)35(9,15)36(30,12)37(0,0)051015202505101520253035yx垃圾站点坐标图1.2问题分析该问题是一个优化调度的问题，研究最佳路线选择，考虑用多目标规划求解，依题意须满足以下几点基本要求：（1）运营费用最低——运输路费是最主要的开支，所以应该将问题的最先考虑权放在运输路费上，然后再对车辆安排和路线的选择方面做出合理安排。（2）每车每天平均工时≤4小时——铲车的调度应该与运输车的调度同时进行，所以我们考虑在运输车的调度基础上，对铲车进行统筹安排调度。2.模型的假设及符号说明42.1模型的假设(1)运输车和铲车装运均正常，不会发生偶然事故；(2)运输车和铲车都不存在塞车现象；(3)运输车和铲车都走直线线路，并可任选路线；(4)忽略运输车和铲车行使时的拐弯时间；(5)各垃圾站点每天的垃圾量固定不变；(6)运输车到达每一个站点后必须将该站点的垃圾全部装完；(7)运输车和铲车行驶速度不变，固定为40公里/小时；(8)每天每车的工作时间固定不变；(9)铲车每装1吨垃圾的费用固定；(10)运输车和铲车使用数量均不受限制；(11)忽略运输车卸垃圾的时间，每站点垃圾装车时间均为10分钟；(12)忽略运输车等待铲车的时间；(13)运营费用里不考虑工人工资、车辆的油费及维修保养费用等。2.2符号说明1．iiyx,：第i个垃圾站点的坐标2．iw：第i个垃圾站点的垃圾量3．1M：运输车的总重载费用4．2M：运输车的总空载费用5．3M：运输车的总费用6．mM：第m辆铲车费用7．4M：铲车总费用8．N：运输车所需的总车次数9．ja：第j辆车的出车次数10．个站点为最远点次车不选择第第个站点为最远点次车选择第第ik,0ik,1bi11．个站点的垃圾次车不装载第第个站点的垃圾次车装载第第ik,0ik,1ci12．个站点次铲车不经过第第个站点次铲车经过第第ik,0ik,1di,k513．个站点为起始点铲车不选择第个站点为起始点铲车选择第i,0i,1gi14．个站点为终点铲车不选择第个站点为终点铲车选择第i,0i,1ih15．mZ：第m辆运输车的载重量（针对问题三而言）16.nr：nr＝n,垃圾站点的可合并范围，即如i站点在以j为中心，nr为半径的范围内，那么i和j可合并，zn17.可合并不存在可合并存在j,i,0j,i,1kij18.tM：垃圾集中费用3.模型的建立与求解3.1.模型ⅠVMP模型：从运输费用和车辆安排、路线选择等各种决策因素出来考虑，我们知道运输费用应该在所有决策因素中占的比率最大，所以我们将其作为有限考虑因素，其他的车辆安排与路线选择均是为其服务，运营路费最小化是我们最终的求解目标。运输车的运营费用是恒定的，总运费为重载与空载运费之和，而在运输车的费用中：空载费用比重载费用要低，所以求解的总的思路是：让空载运输车开到最远处，在保证时间和载重量不超额的情况下，沿途把各站点的垃圾带回。故总运费的确定就可以转化为一定条件下的各车次最远点的选择问题。在路径选择方面，应遵循如下原则：1）远者优先：即先让运输车开到尽量远的地方，再沿途返回将各经过的站点的垃圾带回，尽量不要让下一车次再到更远点去运回垃圾。2）不走回头路：即一方面，不能让运输车经过一个站点后再去下一个较原点比它更远的站点；另一方面，在同样路程情况下，由于重载费用比空载费用大得多，因此，尽量使车辆空载跑路。3）尽量控制车次数：一方面，相对最远点选择多，车次空载的路程就多，费用就高；另一方面，从现实角度，要考虑司机情感等因素。由以上分析，运输车费用如下表示所以我们得出以下的相关约束条件，及目标函数：目标函数：运输车重载费用：36118.1iiiiyxwM运输车空载费用：NkiiiiyxbM136124.06总费用：213MMM条件约束：时间约束：460104021361ajiiiicyx载重量约束：1.06iicw路线约束：1111,iiiiiiiiycycxcxc进而，再根据问题分析结果，我们应把站点30（28，18）,28(24,20),36(30,12)34（9，20），24（15，19），25（15，14），33（25，7），12（14，6）设为最远点,结合约束条件，可得第一车次原点→24（15，19）→18（11，17）→35（9，15）→7（7，9）→返回第二车次原点→4（4，11）第三车次原点→30（28，18）→29（25，16）→27（21，13）→3（5，4）→返回第四车次原点→33（25，7）→32（22，5）→22（21，0）→10（14，0）→返回第五车次原点→8（9，6）→2（1，5）→返回第六车次原点→28（24，20）→26（20，17）→21（17，16）→19（15，12）→14（11，12）→返回第七车次原点→34（9，20）→17（6，18）→16（2，16）→6（0，8）→返回第八车次原点→11（17，3）→返回第九车次原点→36（30，12）→23（27，9）→15（19，9）→13（12，9）→返回第十车次原点→25（15，14）→20(7,14)→31(5,12)→5(3,11)→返回第十一车次原点→12（14，6）→9（10，2）→1（3，2）→返回做出车辆行驶路线图如下：7根据以上确定的路线，可计算出各车次的运行时间、总载重、运营费用。所求结果列表如下：车次所用时间（小时）总载重（吨）运费（元）第一车次2．375.80286.48第二车次0.721.2028.16第三车次2.975.85404.05第四车次2.276.10269.12第五车次1.083.8084.3第六车次3.035.90350.78第七车次2.124.35169.64第八车次1.171.1047.6第九车次2.775.90344.4第十车次2.125.40208.7第十一车次1.505.60148.94合计22.1251.02339.17根据时间约束，至少派7辆车执行任务，因此把1与2、3与4、5与6、7与8车次分别合并，由4辆车执行此次任务，其余3个车次分别派3辆车执行。同时考虑到司机的休息时间，为最大限度节约时间，应该由一辆车连续执行两个车次，而做出安排，如下表所示：车辆车次第一辆车1、2第二辆车3、4第三辆车5、6第四辆车7、8第五辆车9、10第六辆车11、12第七辆车1