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

《2008年校“希望杯”数学建模竞赛赛试题及参考答案.doc》由会员分享，可在线阅读，更多相关《2008年校“希望杯”数学建模竞赛赛试题及参考答案.doc（21页珍藏版）》请在三一文库上搜索。

1、竞赛试题：垃圾运输问题某城区有26个垃圾集中点，每天都要从垃圾处理厂（第27号节点）出发将垃圾运回。现有一种载重 6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为35公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。 问题： 1.由于人力成本与车辆购置成本较大，垃圾处理场希望用尽可能少的车来完成任务。请就本题所给数据，确定需要车辆数。 2. 在问题（1）的前提下，确定运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营

2、费用） 3.如果有载重量为4吨、6吨、8吨三种运输车，问题（1）、（2）有何变化？ 垃圾点地理坐标数据表 序号 站点 编号 垃圾量T 坐标(km) 序号 站点 编号 垃圾量T 坐标(km) x y x y 1 1 1.50 3 2 15 15 1.40 19 9 2 2 1.50 1 5 16 16 1.20 22 5 3 3 0.85 0 8 17 17 1.60 15 19 4 4 1.30 3 11 18 18 1.60 15 14 5 5 1.20 7 9 19 19 1.00 20 17 6 6 2.30 9 6 20 20 2.00 21 13 7 7 1.50 14 0 21 2

3、1 2.10 25 16 8 8 1.10 17 3 22 22 1.20 28 18 9 9 2.50 14 6 23 23 1.90 5 12 10 10 1.80 10 12 24 24 1.60 25 7 11 11 0.60 7 14 25 25 1.20 9 20 12 12 1.50 2 16 26 26 1.50 9 15 13 13 1.50 11 17 27 27 0.00 0 0 14 14 0.80 15 12 垃圾运输问题的数学建模（2008年校一等奖作品，没有标准答案，以下方案供参考）摘要垃圾的收集、转运和运输问题是垃圾收运的重要环节，是城市垃圾管理系统的重要组成部

4、分，随着城市垃圾处理成本的增加，垃圾运收的统筹优化安排日益重要。该题目就是考察垃圾运输运营成本的优化问题。本文根据题目要求，运用多目标规划（VMP）模型，分别求解出了同吨位的运输车，不同吨位的运输车及铲车的最优调度方案，而且绘制出了直观图。并且结合题目要求与实际情况，对现有的垃圾集中点分布进行了优化合并。首先，将题目所给的垃圾站点坐标表格转换成站点位置坐标图，根据题目要求与实际情况做出一些合理的假设。然后，根据题设、点的位置、所做假设以及逻辑性的推导归纳出几点最基本的确定路线的原则。然后，在针对问题（1）提出的VMP模型中，确立运营费用的目标函数，以及时间约束、载重量约束、路线约束条件。由此，

5、运用MATLAB软件求解出了6吨位运输车最优调度方案：11个车次，6辆车交替轮流担任各运输任务，共用22.12小时，总运营费用2339.17元。问题（3）的解决是在模型的基础上，增加两个车辆调度原则：吨位大的车优先与吨位小的车收尾原则，并相应改变载重约束条件提出模型而完成的。所求得的可变吨位运输车调度方案是：8个车次，其中8吨位的5车次，6吨位的2车次，4吨位的1车次，共用19.2小时，总运营费用2315.6元。针对问题（2）提出的模型是在模型的基础上，对铲车做出合理的假设。因为这些假设，再加上铲车不存在重载问题，所以此问求铲车最少运营费用可以转化成求满足时间约束条件的最小行走路径问题。由此统

6、筹安排出了4辆铲车，共用15.9小时，总运营费用158.4元。而且，我们还拟列了一张车辆时间安排表，以更好更直观的指导工作实践。最后，为降低运营费用，我们综合优化了垃圾运输路线。将同属于一个圆周的几个站点进行合并，根据圆半径的不同值算出了不同的合并方案下的的运营费用。但是最终我们选择了折中的方案，因为考虑到实际生活中垃圾集中点确立有其他许多的影响因素。此外，还对模型进行了全面的评价，认为模型具有可信度高、简单易懂的优点，但它的最大的缺点是过度追求费用最小化，有一些偏离实际。 1.问题重述和分析1.1问题重述某城区有36个垃圾集中点，每天都要从垃圾处理场（第37号节点，坐标（0，0），垃圾量为0

7、）出发将垃圾运回。现有一种载重6吨的运输车，其运行平均速度为40公里/小时（晚上运输，不考虑堵车现象）；每辆车每日平均只能工作4小时。每个垃圾点需用10分钟的时间装车。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；假定街道方向均平行于坐标轴。求解最佳运输调度方案及计算程序。问题：（1） 需要投入几台运输车，每台车的调度方案，运营费用（2） 需要投入几台铲车，每台铲车的行车路线，运营费用（3） 如果有载重量为4吨、6吨、8吨三种运输车，又应该如何调度？（4） 讨论对现有的垃圾集中点的可行性合并措施，以降低运营费用？已知运输情况及车辆使用性能状况： 运输车载重量：6

8、吨 运输车平均速度：40公里/小时 运输车重载运费：1.8元/公里 运输车空载及铲车费用：0.4元/公里 每台车每日平均工作时间：4小时 每个垃圾点需装车时间：10分钟已知垃圾点地理坐标图：1.2问题分析该问题是一个优化调度的问题，研究最佳路线选择，考虑用多目标规划求解，依题意须满足以下几点基本要求：（1）运营费用最低运输路费是最主要的开支，所以应该将问题的最先考虑权放在运输路费上，然后再对车辆安排和路线的选择方面做出合理安排。（2）每车每天平均工时4小时铲车的调度应该与运输车的调度同时进行，所以我们考虑在运输车的调度基础上，对铲车进行统筹安排调度。2.模型的假设及符号说明2.1模型的假设(1

9、)运输车和铲车装运均正常，不会发生偶然事故；(2)运输车和铲车都不存在塞车现象；(3)运输车和铲车都走直线线路，并可任选路线；(4)忽略运输车和铲车行使时的拐弯时间；(5)各垃圾站点每天的垃圾量固定不变；(6)运输车到达每一个站点后必须将该站点的垃圾全部装完；(7)运输车和铲车行驶速度不变，固定为40公里/小时；(8)每天每车的工作时间固定不变；(9)铲车每装1吨垃圾的费用固定；(10)运输车和铲车使用数量均不受限制；(11)忽略运输车卸垃圾的时间，每站点垃圾装车时间均为10分钟；(12)忽略运输车等待铲车的时间；(13)运营费用里不考虑工人工资、车辆的油费及维修保养费用等。2.2符号说明1：

10、第i个垃圾站点的坐标2 ：第i个垃圾站点的垃圾量3：运输车的总重载费用4：运输车的总空载费用5：运输车的总费用6：第m辆铲车费用7：铲车总费用8：运输车所需的总车次数9 ：第j辆车的出车次数10 1112 13 1415：第m辆运输车的载重量（针对问题三而言）16.：n,垃圾站点的可合并范围，即如i站点在以j为中心，为半径的范围内，那么i和j可合并，17. 18.：垃圾集中费用3.模型的建立与求解3.1.模型VMP模型：从运输费用和车辆安排、路线选择等各种决策因素出来考虑，我们知道运输费用应该在所有决策因素中占的比率最大，所以我们将其作为有限考虑因素，其他的车辆安排与路线选择均是为其服务，运营

11、路费最小化是我们最终的求解目标。运输车的运营费用是恒定的，总运费为重载与空载运费之和，而在运输车的费用中：空载费用比重载费用要低，所以求解的总的思路是：让空载运输车开到最远处，在保证时间和载重量不超额的情况下，沿途把各站点的垃圾带回。故总运费的确定就可以转化为一定条件下的各车次最远点的选择问题。在路径选择方面，应遵循如下原则：1） 远者优先：即先让运输车开到尽量远的地方，再沿途返回将各经过的站点的垃圾带回，尽量不要让下一车次再到更远点去运回垃圾。2） 不走回头路：即一方面，不能让运输车经过一个站点后再去下一个较原点比它更远的站点；另一方面，在同样路程情况下，由于重载费用比空载费用大得多，因此，

12、尽量使车辆空载跑路。3） 尽量控制车次数：一方面，相对最远点选择多，车次空载的路程就多，费用就高；另一方面，从现实角度，要考虑司机情感等因素。由以上分析，运输车费用如下表示所以我们得出以下的相关约束条件，及目标函数：目标函数： 运输车重载费用： 运输车空载费用： 总费用： 条件约束：时间约束： 载重量约束： 路线约束： 进而，再根据问题分析结果，我们应把站点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，1

13、5）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,

14、12)5(3,11)返回第十一车次原点12（14，6）9（10，2）1（3，2）返回做出车辆行驶路线图如下：根据以上确定的路线，可计算出各车次的运行时间、总载重、运营费用。所求结果列表如下：车次所用时间（小时）总载重（吨）运费（元）第一车次2375.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.6

15、0148.94合计22.1251.0 2339.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第七辆车13、14在上述模型中，车辆用了7辆，而总运输时间为22.12小时， 每辆车每天平均工作时间为3.16小时，车辆安排作进一步修改。假设条件改为每台车几天工作总时间之和除以天数不大于4，那么：L为车辆工作天

16、数。因为22.124=5.53，故最少要安排6辆车，安排车辆的总体思路为让工作时间少的与工作时间多的车辆交替轮流担任各车次的运输工作，同时考虑到要把司机休息的时间合并到一起，应该把某辆车所执行的两个车次放在一起，做出安排如下表： 车辆车次第一辆车1、111、2第二辆车3、103、4第三辆车4、9 5、6第四辆车5、87、8第五辆车6、79、10第六辆车2 113.2.模型：VMP模型：这是针对问题三提出的模型，由于各运输车的载重量不同，所以我们的总体思路是：在模型一中提出的三点考虑因素下，我们再让运输车中载重量大的车辆优先进行运输，这样有利于减少派出车辆的次数，减少运营费用。而让运输车中载重量

17、小的车辆收尾，这样有利于灵活调用。所以我们仍旧可以得出以下这次目标函数以及约束条件：目标函数：运输车的重载费用： 运输车的空载费用： 运输车的总费用： 约束条件：1） 时间条件约束：2）运输车的载重量约束：3）路线约束： 同样根据模型的确定车辆路线的思路，我们应该把36(30,12)，30（28，18）,28(24,20), 24（15，19），12（14，6），34（9，20），15（19，9），22（21，0），设为最远点,结合约束条件，可得第一车次原点36（30，12）23（27，9）33（25，7）32（22，5）11（17，3）9（10，2）返回第二车次原点30（28，18）29（2

18、5，16）27（21，13）19（15，12）14（11，12）返回第三车次原点28（24，20）26（20，17）21（17，16）25（15，14）15(7,14) 4（4，7）返回第四车次原点24（15，19）18（11，17）35（9，15）31(5,12)5(0，8)返回第五车次原点12（14，6）8（9，6）3（5，4）1（3，2）返回第六车次原点34（9，20）17（6，18）16（2，16）2（1，5）返回第七车次原点20(19,9)13（12，9）7（7，9）6（3，11）返回第八车次原点22（21，0）10（14，0）返回此时车辆行驶路线图如下：根据这些车次的路线信息，我们

19、运用matlab计算出个车次、车辆型号的运用、所用时间、载重量及总运营费用，得到的结果如下表3所示：车次所经站数车辆型号所用时间（小时）总载重（吨）运费（元）第一车次683.18430.98第二车次53.137.9505.3第三车次63.26.7394.88第四车次52.537.8342.82第五车次41.677.05189.71第六车次462.125173.6第七车次42.075.25217.12第八车次241.383.3114.24合计3619.2512368.653.3.模型VMP模型：铲车的调度主要涉及到了铲车的数量、每台铲车的行走路线及运营费用。就费用而言，铲车每日每站的垃圾量不变，

20、铲车每装1吨垃圾的费用和速度固定，且不存在重载问题，唯一的变量铲车的空载费用0.4元/公里，所以要考虑铲车的调度问题，在这里我们最需要考虑的是每台铲车的行走路线。我们在模型一的基础上，可以将铲车的最小费用问题转化为满足一定条件的最小路径行走问题。转化为最小路径行走问题时该考虑的条件有：由于铲车每日每站的垃圾量不变，铲车每装1吨垃圾的费用和速度固定，但存在一个与路程有关的空载费用，且长时间行驶也影响工时，所以铲车要多装垃圾少走路，尽量考虑沿途装垃圾。运输车存在着工时问题，所以铲车与运输车的调度时间要合理安排，运输车的调度时间应尽量配合铲车的调度时间，即运输车跟着铲车走，尽量避免运输车或者铲车中间

21、空闲的情况发生。模型的计算由以上分析，可以得出目标函数：约束条件：时间约束：我们先大致计算铲车至少要工作的时间：铲车需要在每个垃圾站点装车10分钟，共需3610=360分钟，即6小时。我们选取最远的三个站点：站点30、站点28、站点36：最远站点30（28，18）离原点距离为：（2818）46公里，铲车起码要走两个来回共需46240=2.3小时，第二远的站点28（24，20）的纵坐标比30（28，18）远2公里，一个来回远4公里，共需2240=0.1小时第三远的站点36（30，12）的横坐标比30（28，18）远2公里，一个来回远4公路，共需2240=0.1小时综上所述：铲车至少要工走：62.

22、3+0.1+0.18.5小时所以，铲车的投入量不得小于3辆，综合考虑成本和需求，我们确定铲车数量为4辆。如下所示的4辆铲车的路径图：辆次路线1号37(0,0)28(24,20)26(20,17)9(15,12)14(11，12)24（15，19）18（11，17）35（9，15）7（7，9）4（4，11）37(0,0)2号3730（28，18）29（25，16）27（21，13）36（30，12）23（27，9）15（19，9）13（12，9）8（9，6）2（1，5）37(0,0)3号3733（25，7）32（22，5）22（21，0）10（14，0）11（17，3）12（14，6）9（10，

23、2）1（3，2）3(5,4)37(0,0)3号3725（15，14）20(7,14)31(5,12)5(3,11)34（9，20）17（6，18）16（2，16）6（0，8）37根据上图，综合考虑铲车和运输车的调度配合，我们假设铲车和运输车同时从18：00派出，由已知速度，结合路程，可得铲车到站时间，综合得出铲车的工作时间和费用，详见表铲车辆次运输车车次铲车派出时间铲车到站时间运输车派出时间铲车工作时间（小时）铲车费用（元）1618：0019：0618：004.4444.4120：47 19：56222：1221：552319：0720：2621：554.2043.2921：2919：0752

24、2：5022：273418：0018：4818：003.7335.6820：0419：341120：2319：5341018：0018：4418：003.5335.2720：1719：33合计15.9158.4平均3.9753.4.模型VMP模型 这里考虑的合并垃圾集中点的措施，是基于降低运营费用的可行下的。也就是说运营费用是该项措施考虑的最主要因素，我们在这里可以看成是唯一因素。而从之前的模型可以看出铲车的费用较运输车的费用要小得多，所以我们在追求运营费用最低的情况下， 主要来看运输车的运输费用。 我们将在模型的基础上，在一定范围内，可合并的垃圾集中点进行合并，以减少垃圾站点的数量，计算每条

25、车次的运费的现值，与原值进行比较，看是否比原来的方案的运费更低。据上分析，得目标函数： 可合并范围：n, 运输车重载费用： 运输车空载费用： 总费用： 条件约束：时间约束： 载重量约束： 路线约束： 在原运输车调度路线的基础上,我们来进行计算：1. 1，02. 2，03.3，1，存在i、j可合并（据图，之后均存在可合并点，将不再说明） （1）第一车次：18（11，17）合并 35（9，15） （2）第十车次：20(7,14) 合并 31(5,12) 合并 5(3,11)4.4， （1）第六车次：26（20，17） 合并 21（17，16） （2）第三车次：30（28，18） 合并 29（25，

26、16） （3）第四车次：33（25，7） 合并 32（22，5） （4）第二车次和第五车次：4（4，11） 合并 2（1，5） （5）第七车次：34（9，20） 合并 17（6，18）5. 5， （1）第十一车次和第八车次：11（17，3） 合并12（14，6） （2）第九车次：25（15，14） 合并20(7,14) 至此，所有线路都有所变动，同时有些车次出现了二次变动： （3）第三车次：30（28，18） 合并 29（25，16） 合并 27（21，13） （4）第六车次：26（20，17） 合并 21（17，16） 19（15，12） 合并14（11，12） （5）第七车次：34（9，2

27、0） 合并 17（6，18） 合并 16（2，16）6. 6，（1）第一车次：24（15，19）合并18（11，17）合并35（9，15）；（2）第三车次：30（28，18）合并29（25，16）合并27（21，13）；（3）第四车次：33（25，7）合并32（22，5）合并 22（21，0）；（4）第五车次：4（4，7）合并2（1，5）；（5）第六车次：28（24，20）合并26（20，17）合并21（17，16）合并19（15，12）合并14（10，12）（6）第七车次：34（9，20）合并17（6，18）合并16（2，16）（7）第九车次：36（30，12）合并23（27，9）（8）第十

28、车次：20（7，14）合并31（5，12）合并5（3，11）（9）第十一车次：12(14,6)合并9（10，2）r=5r=4根据以上确定的路线，利用MATLAB可计算出各车次的运行时间、总载重、运营费用。所求结果列表如下：当3，车次所用时间（小时）总载重（吨）运费（元）第一车次2.205.80272.8第二车次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第十车次1.795.

29、40197.72第十一车次1.505.60148.94合计21.6251.0 2317.51当4时，4车次所用时间（小时）总载重（吨）运费（元）第一车次2.205.80272.8第二车次第三车次2.805.85391.5第四车次2.106.10258.32第五车次1.085.0097.26第六车次2.865.90343.58第七车次1.954.35158.84第八车次1.171.1047.6第九车次2.775.90344.4第十车次1.795.40197.72第十一车次1.505.60148.94合计20.2251.0 2260.96当5时，车次所用时间（小时）总载重（吨）运费（元）第一车次2

30、375.80272.8第二车次第三车次2.635.85346.87第四车次2.276.10258.32第五车次1.085.0097.26第六车次2.705.90336.38第七车次1.794.35132.84第八车次第九车次2.605.90327.96第十车次2.125.40197.72第十一车次1.56.70148.94合计19.651.0 2119.09当 6时，车次所用时间（小时）总载重（吨）运费（元）第一车次1.535.80242.88第二车次第三车次2.035.85346.87第四车次1.386.10220.08第五车次1.085.0097.26第六车次1.275.90242.44第

31、七车次1.234.35132.84第八车次第九车次2.305.90327.96第十车次1.785.40190.88第十一车次0.936.70132.62合计13.5351.0 1933.83从以上我们可以看出可合并范围越大，运营费用越低， ，费用最低点为37（0，0），即垃圾处理厂。但这显然是不合理的，在合并垃圾站时，我们不可能单单考虑运费，我们还得考虑集中成本，包括收集垃圾时的产生的车辆费用、工人的工资及居民反对的可能性等。集中成本主要有：垃圾转运成本、人工费、空车成本、维修费用及其它费用，即：对于不同的r的取值，其减少的运输总费用若比集中成本少，则应采用r越大的方案越好。若其减少的运输总费

32、用若比集中成本多，则应采用r越小的方案越好，即总的花费成本越少，此时采用的方案为r3时的方案，即第一车次：18（11，17）合并 35（9，15）； 第十车次：20(7,14) 合并 31(5,12) 合并 5(3,11)各车次的运行时间、总载重、运营费用。所求结果列表如下：车次所用时间（小时）总载重（吨）运费（元）第一车次2.205.80272.8第二车次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第九车

33、次2.775.90344.4第十车次1.795.40197.72第十一车次1.505.60148.94合计21.6251.0 2317.514.模型分析与检验由模型和模型的结果可以知道，模型的运输费用比模型中的运输费用要小，这说明我们可以充分利用每个车辆的最大载重量。这也更说明了对于不同的运输车辆，当车辆的额定载重量越大时，最远点的数量其实会相对应的减少，也就决定了运输费用减少。当然我们也从垃圾站点的布设来分析，从模型和模型中可以看出，垃圾站点的布设没有一定的规律性，这就间接地增加了运输费用。在模型中，铲车的调度与运输车的调度同时进行，且让工作时间少的车辆与工作时间多的车辆轮流担任装载工作，最

34、大限度的节约时间与成本费用。而模型中，通过求解半径不同的合并方案，基于寻找一定范围内的最短路径，我们可以看出离原点既垃圾处理厂越近，所花费成本越少。但是考虑到现实意义，只有满足一定条件，综合规划才可以合理安排合并方案，减少费用。而最后由各个模型的求解过程可以知道，每个模型得出的结论都必须满足同一个约束条件：时间约束：即每台车每日平均工作时间不得超过4小时。而结果也是符合要求的，并且我们最大限度地控制了运输车的费用，这是首要考虑的目标函数。5.模型评价模型之优点：1） 三个模型均是运用多目标规划模型，来自运筹学，具有一定的可信性，并且系统给出了运输车和铲车的车辆调度方案。2） 模型方便、直观，通

35、俗易懂，并且这种多目标规划模型的方法可以运用到很多数学模型或者其他领域中，具有广泛的实用性。模型之缺点：1） 模型过分去追求最小的运输费用，以至于其他的方面并不够重视，所以安排的方面有点缺陷。2） 模型假设方面，我们是将每站每天的垃圾总量视为一个不变的数，为不现实之处。3） 第四个模型未将居民可接受的扔垃圾距离考虑在内，故此处在应用于实践方面，还应做进一步改进。6.模型推广1） 模型简单、直观，可应用于计算机模拟。2） 此模型不仅可应用于垃圾运输问题，还可应用于车辆调度问题，如露天矿生产车辆安排、公交车调度方案优化问题等，还可推及电站和城市垃圾转运站的选址问题。参考文献1 吴建国，数学建模案例精编，北京，中国水利水电出版社，20052 姜启源，数学建模，北京，高等教育出版社，20003 张伯生，运筹学，北京，科学出版社，2008 （注：可编辑下载，若有不当之处，请指正，谢谢!）