《垃圾运输问题》PPT课件.ppt
垃圾运输问题,2008年数学建模竞赛题,小组成员：袁德琴周玲玲张 芳,某城区有36个垃圾集中点，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。现有一种载重 6吨的运输车。每个垃圾点需要用10分钟的时间装车，运输车平均速度为40公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4小时。运输车重载运费1.8元/吨公里；运输车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。,问题,1.由于人力成本与车辆购置成本较大，垃圾处理场希望用尽可能少的车来完成任务。请就本题所给数据，确定需要车辆数。2.在问题（1）的前提下，确定运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）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 21 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,1.问题重述和分析,1.1问题重述某城区有36个垃圾集中点，每天都要从垃圾处理场（第37号节点，坐标（0，0），垃圾量为0）出发将垃圾运回。现有一种载重6吨的运输车，其运行平均速度为40公里/小时（晚上运输，不考虑堵车现象）；每辆车每日平均只能工作4小时。每个垃圾点需用10分钟的时间装车。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；假定街道方向均平行于坐标轴。求解最佳运输调度方案及计算程序。问题：1.由于人力成本与车辆购置成本较大，垃圾处理场希望用尽可能少的车来完成任务。请就本题所给数据，确定需要车辆数。2.在问题（1）的前提下，确定运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）3.如果有载重量为4吨、6吨、8吨三种运输车，问题（1）、（2）有何变化？,垃圾点地理坐标图,运输情况及车辆使用性能状况,运输车载重量：6吨 运输车平均速度：40公里/小时 运输车重载运费：1.8元/公里 每台车每日平均工作时间：4小时 每个垃圾点需装车时间：10分钟,1.2问题分析该问题是一个优化调度的问题，研究最佳路线选择，考虑用多目标规划求解，依题意须满足以下几点基本要求：（1）运营费用最低运输路费是最主要的开支，所以应该将问题的最先考虑权放在运输路费上，然后再对车辆安排和路线的选择方面做出合理安排。（2）每车每天平均工时4小时.,2.模型的假设及符号说明,2.1模型的假设(1)运输车装运均正常，不会发生偶然事故；(2)运输车都不存在塞车现象；(3)运输车走直线线路，并可任选路线；(4)忽略运输车行使时的拐弯时间；(5)各垃圾站点每天的垃圾量固定不变；(6)运输车到达每一个站点后必须将该站点的垃圾全部装完；(7)运输车行驶速度不变，固定为40公里/小时；(8)每天每车的工作时间固定不变；(9)运输车使用数量均不受限制；(10)忽略运输车卸垃圾的时间，每站点垃圾装车时间均为10分钟；(11)运营费用里不考虑工人工资、车辆的油费及维修保养费用等。,2.2符号说明1：第i个垃圾站点的坐标2：第i个垃圾站点的垃圾量3：运输车的总重载费用4：运输车的总空载费用5：运输车的总费用6：运输车所需的总车次数7：第j辆车的出车次数89.,10：第m辆运输车的载重量（针对问题三而言）,3.模型的建立与求解,3.1.模型 与路线选择均是为其服务，运营路费最小化是我们最终的求解目标。运输车的运营费用是恒定的，总运费为重载与空载运费之和，而在运输车的费用中：空载费用比重载费用要低，所以求解的总的思路是：让空载运输车开到最远处，在保证时间和载重量不超额的情况下，沿途把各站点的垃圾带回。故总运费的确定就可以转化为一定条件下的各车次最远点的选择问题。在路径选择方面，应遵循如下原则：远者优先：即先让运输车开到尽量远的地方，再沿途返回将各经过的站点的垃圾带回，尽量不要让下一车次再到更远点去运回垃圾。不走回头路：即一方面，不能让运输车经过一个站点后再去下一个较原点比它更远的站点；另一方面，在同样路程情况下，由于重载费用比空载费用大得多，因此，尽量使车辆空载跑路。从运输费用和车辆安排、路线选择等各种决策因素出来考虑，我们知道运输费用应该在所有决策因素中占的比率最大，所以我们将其作为有限考虑因素，其他的车辆安排尽量控制车次数：一方面，相对最远点选择多，车次空载的路程就多，费用就高；另一方面，从现实角度，要考虑司机情感等因素。,由以上分析，运输车费用如下表示所以我们得出以下的相关约束条件，及目标函数.目标函数 运输车重载费用：运输车空载费用：总费用：条件约束时间约束：,载重量约束：路线约束：进而，再根据问题分析结果，我们应把站点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）返回,做出车辆行驶路线图如下：,根据以上确定的路线，可计算出各车次的运行时间、总载重、运营费用。所求结果列表如下：车次 所用时间（小时）总载重（吨）运费（元）第一车次 237 5.80 286.48第二车次 0.72 1.20 28.16第三车次 2.97 5.85 404.05第四车次 2.27 6.0 269.12第五车次 1.08 3.80 84.3第六车次 3.03 5.90 350.78第七车次 2.12 4.35 169.64第八车次 1.17 1.10 47.6第九车次 2.77 5.90 344.4第十车次 2.12 5.40 208.7第十一车次 1.50 5.60 148.94合计 22.12 51.0 2339.17,根据时间约束，至少派7辆车执行任务，因此把1与2、3与4、5与6、7与8车次分别合并，由4辆车执行此次任务，其余3个车次分别派3辆车执行。同时考虑到司机的休息时间，为最大限度节约时间，应该由一辆车连续执行两个车次，而做出安排，如下表所示：车辆 车次第一辆车 1、11第二辆车 2、7第三辆车 5、10第四辆车 4、8第五辆车 3第六辆车 6第七辆车 9,以上是本小组讨论第一个问题的结果，由于时间关系，剩下的两个问题，由同学们下来自己分析解答，并欢迎参加本小组的讨论。,谢谢！,3.2.模型：VMP模型：这是针对问题三提出的模型，由于各运输车的载重量不同，所以我们的总体思路是：在模型一中提出的三点考虑因素下，我们再让运输车中载重量大的车辆优先进行运输，这样有利于减少派出车辆的次数，减少运营费用。而让运输车中载重量小的车辆收尾，这样有利于灵活调用。所以我们仍旧可以得出以下这次目标函数以及约束条件：目标函数：运输车的重载费用：运输车的空载费用：运输车的总费用：,约束条件：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），设为最远点,结合约束条件，可得,以上是本小组讨论第一个问题的结果，由于时间关系，剩下的两个问题，由同学们下来自己分析解答，并欢迎参加本小组的讨论。,谢谢！,以上是本小组讨论第一个问题的结果，由于时间关系，剩下的两个问题，由同学们下来自己分析解答，并欢迎参加本小组的讨论。,谢谢！,以上是本小组讨论第一个问题的结果，由于时间关系，剩下的两个问题，由同学们下来自己分析解答，并欢迎参加本小组的讨论。,谢谢！,
