垃圾运输问题

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

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

3、 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个垃圾集中点，

4、每天都要从垃圾处理场（第37号节点，坐 标（0，0），垃圾量为0）出发将垃圾运回。现有一种载重6吨的运输 车，其运行平均速度为40公里/小时（晚上运输，不考虑堵车现象）； 每辆车每日平均只能工作4小时。每个垃圾点需用10分钟的时间装车。 运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4 元/公里；假定街道方向均平行于坐标轴。求解最佳运输调度方案及计 算程序。 问题： 1.由于人力成本与车辆购置成本较大，垃圾处理场希望用尽可能少的 车来完成任务。请就本题所给数据，确定需要车辆数。 2. 在问题（1）的前提下，确定运输车应如何调度（需要投入多少台 运输车，每台车的调度方案，运营

5、费用） 3.如果有载重量为4吨、6吨、8吨三种运输车，问题（1）、（2）有 何变化？ 垃圾点地理坐标图 运输情况及车辆使用性能状况 运输车载重量：6吨 运输车平均速度：40公里/小时 运输车重载运费：1.8元/公里 每台车每日平均工作时间：4小时 每个垃圾点需装车时间：10分钟 1.2问题分析 该问题是一个优化调度的问题，研究最佳 路线选择，考虑用多目标规划求解，依题 意须满足以下几点基本要求： （1）运营费用最低运输路费是最主要 的开支，所以应该将问题的最先考虑权放 在运输路费上，然后再对车辆安排和路线 的选择方面做出合理安排。 （2）每车每天平均工时4小时. 2.模型的假设及符号说明 2.

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

7、的总重载费用 4 ：运输车的总空载费用 5 ：运输车的总费用 6 ：运输车所需的总车次数 7 ：第j辆车的出车次数 8 9. ii yx , i w 1 M 2 M 3 M N j a 个站点为最远点次车不选择第第 个站点为最远点次车选择第第 ik, 0 ik, 1 bi 个站点的垃圾次车不装载第第 个站点的垃圾次车装载第第 ik, 0 ik, 1 c i 10 ：第m辆运输车的载重量（针对问题三 而言） 3.模型的建立与求解 3.1.模型 与路线选择均是为其服务，运营路费最小化是我们最终的求解目 标。 运输车的运营费用是恒定的，总运费为重载与空载运费之和，而在运 输车的费用中：空载费用比重载

8、费用要低，所以求解的总的思路是： 让空载运输车开到最远处，在保证时间和载重量不超额的情况下，沿 途把各站点的垃圾带回。故总运费的确定就可以转化为一定条件下的 各车次最远点的选择问题。 在路径选择方面，应遵循如下原则： 远者优先：即先让运输车开到尽量远的地方，再沿途返回将各经过的 站点的垃圾带回，尽量不要让下一车次再到更远点去运回垃圾。 不走回头路：即一方面，不能让运输车经过一个站点后再去下一个较 原点比它更远的站点；另一方面，在同样路程情况下，由于重载费用 比空载费用大得多，因此，尽量使车辆空载跑路。从运输费用和车辆 安排、路线选择等各种决策因素出来考虑，我们知道运输费用应该在 所有决策因素中

9、占的比率最大，所以我们将其作为有限考虑因素，其 他的车辆安排 尽量控制车次数：一方面，相对最远点选择多，车次空载的路程就多， 费用就高；另一方面，从现实角度，要考虑司机情感等因素。 由以上分析，运输车费用如下表示 所以我们得出以下的相关约束条件，及目标函数. 目标函数 运输车重载费用： 运输车空载费用： 总费用： 条件约束 时间约束： 36 1 1 8 .1 i iii yxwM N ki iii yxbM 1 36 1 2 4 . 0 213 MMM 4 60 10 40 2 1 36 1 a ji i ii c yx 载重量约束： 路线约束： 进而，再根据问题分析结果，我们应把站点30 （

10、28，18）,28(24,20),36(30,12) 34（9，20），24（15，19），25（15，14）， 33（25，7），12（14，6）设为最远点,结合约 束条件，可得 6 iic w 1111 , iiiiiiii ycycxcxc 第一车次原点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

11、）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）返回 做出车辆行驶路线图如下： 根据以上确定的路线，可计算出各车次的 运行时间、总载重、运营费用。所求结果 列表如下： 车次 所用时间（小时） 总载重（吨） 运费（元） 第一车次

12、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辆车执

13、行此次任务， 其余3个车次分别派3辆车执行。同时考虑到司机的休息时 间，为最大限度节约时间，应该由一辆车连续执行两个车 次，而做出安排，如下表所示： 车辆 车次 第一辆车 1、11 第二辆车 2、7 第三辆车 5、10 第四辆车 4、8 第五辆车 3 第六辆车 6 第七辆车 9 以上是本小组讨论第一个问题的结果，由 于时间关系，剩下的两个问题，由同学们 下来自己分析解答，并欢迎参加本小组的 讨论。 3.2.模型： VMP模型： 这是针对问题三提出的模型，由于各运输车的载重量不同，所以我 们的总体思路是：在模型一中提出的三点考虑因素下，我们再让运 输车中载重量大的车辆优先进行运输，这样有利于减少

14、派出车辆的 次数，减少运营费用。而让运输车中载重量小的车辆收尾，这样有 利于灵活调用。 所以我们仍旧可以得出以下这次目标函数以及约束条件： 目标函数： 运输车的重载费用： 运输车的空载费用： 运输车的总费用： 36 1 1 8 . 1 i iii yxwM N ki iii yxbM 1 36 1 2 4 . 0 213 MMM 约束条件： 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），设为最远点,结合约束条件，可得 4 60 10 40 2 1 36 1 a ji i ii c yx mii zcw 1111 , iiiiiiii ycycxcxc 第一车次 原点36（30，12）23（27，9）33（25，7） 32（22，5）11（17，3）9（10，2）返回 第二车次 原点30（28，18）29（25，16）27（21，13） 19（