1、垃圾运输问题姓名： 冯慧班级：服装 162学号：201609070203学院：设计与艺术院垃圾运输问题摘 要我们就生活中垃圾运输的问题的调度方案予以研究。本文通过对问题的分析和合理的假设，采用规划的理论建立了单目标的非线性规划的数学模型。 ，运用 软件得到了全局最优解，对此类问题的求解提供了一种较优的方案。LINGO题中的问题（1）包含着垃圾量和运输费用的累积计算问题，因此，文中以运输车所花费用最少为目标函数，以运输车载重量的大小、当天必须将所有垃圾清理完等为约束条件，以运输车是否从一个垃圾站点到达另一个垃圾站点为决策变量，建立了使得运输费用最小的单目标的非线性规划模型。运用求解，得出了最优的
2、运输路线为 10 条，此时运输所花费用为 2335.77LINGO元。通过分析，发现只需 6 辆运输车（载重量为 6 吨）即可完成所有任务，且每辆运输车的工作时间均在 4 个小时左右。具体结果见文中表 3。问题（2） ，建立了以运行路径最短为目标的单目标非线性规划模型。从而求出了使铲车费用最少的 3 条运行路线，且各条路线的工作时间较均衡。因此，处理站需投入 3 台铲车才能完成所有装载任务，且求得铲车所花费用为 202.0元，三辆铲车的具体运行路线见文中表 4。文中，我们假定垃圾处理站的运输工作从晚 21：00 开始，根据各铲车的运输路线和所花时间的大小，将铲车和运输车相互配合进行工作的时间做
3、出了详细的安排见表 5。问题（3） ，要求给出当有载重量为 4 吨、6 吨、8 吨三种运输车时的最优的调度方案。基于第（1）问中的模型，修改载重量的约束条件，用 和LINGO分别求解，得出两种调度方案，但总的运输费用不变，均为 2326.17MATLB元；对于方案一，有 9 条路径，分别需要 4 吨的运输车 1 辆；6 吨的运输车 2辆；8 吨的运输车 5 辆，各运输车具体的运输线路见文中表 8。对于方案二，有10 条路径，分别需要 4 吨的运输车 1 辆；6 吨的运输车 1 辆；8 吨的运输车 4辆，各运输车具体的运输线路见文中表 10。最后，对模型的优缺点进行了分析，并给出了模型的改进意见
4、，对解决实际问题具有一定的指导意义。关键字： 垃圾运输的调度；线性规划；最优解问题的分析这是一个便利问题，此问题的困难之处在于确定铲车的行走路线，并使得运输车工作时尽量不要等待铲车，才能使得运输车的工作时间满足题目的要求每日平均工作四小时，为此，应该使铲车跟着运输车跑完一条线路，也就是说，应该使铲车铲完一条线路后再接着铲下一条线路。第（1）问，对于运输车调度方案的设计，不能仅仅考虑使运输车的行走路线最短，因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使得所有运输的花费最少。在建模过程中，我们无需考虑投入的运输车台数，只需对各条路径所花费的时间进行和各运输车载重量约束即可，
5、至于投入的车辆数，在各条路径确定后，计算出各路径运输所花费的时间，再根据题目中要求的每辆车平均工作时间为 4 小时左右进行计算即可。第（2）问中，对于铲车的调度方案，因其无累积计算问题，因此只需要在已确定的各运输路径的基础上，使得铲车的行驶路径为最短。在此方案中，我们将已确定的各条路径看作为节点，建立使铲车运费最少（亦即路径最短）的非线性规划模型，在此需注意的是，由于垃圾运输为夜间运输，所以每辆铲车的工作时间也受到一定的限制，文中，我们假定铲车的工作时间为从（晚21：00早 6：00） ，因此每辆铲车的工作时间最多为 9 个小时，再由所有运输车完成任务所需的总时间判定所需铲车的台数，之后可以根
6、据具体情况进行调整。同时应注意，由于运输车有工作时间的限制，而铲车没有严格的限制（除工作时间不能超过 9 小时以外） ，所以，在确定铲车出行的时间时，应保证只可让铲车等待运输车，而不能让运输车等待铲车。对于第（3）问，是在第一问的基础上将对运输车载重的约束条件从不大于6 吨改为不大于 8 吨，在求得各条路线中，对于垃圾量不大于 4 吨的路线，调用 4 吨的运输车；对于垃圾量在（46 吨）之间的路线，调用 6 吨的运输车；对于垃圾量在（68 吨）之间的路线，调用 8 吨的运输车。一 模型假设（1）假设各站点每天的垃圾量是不变的；（2）假设各站点的垃圾都必须在当天清理完毕；（3）不考虑运输车和铲车
7、在行驶过程中出现的塞车、抛锚等耽误时间的情况；（4）不允许运输车有超载现象；（5）每个垃圾站点均位于街道旁，保证运输车和铲车行驶顺畅；二 模型的建立及求解1 符号说明 每天运输前第 个垃圾站点的垃圾量；isi第 个垃圾站点向第 个垃圾站点运输的垃圾量；jix, j运输车是否从第 个垃圾站点向第 个垃圾站点运输的 0-1 变量；jiu, ij第 辆铲车是否从第 条路径向第 条路径运输的 0-1 变量；kji,第 个垃圾站点和第 个垃圾站点之间的距离；jid, j第 条路径到第 条路径的有向距离；ji,垃圾运输车的单位量货物每公里的运输费用；a垃圾运输车和铲车每公里的空载费用；b铲车通过第 条路径
8、所需要的时间（包括在各垃圾站点装车的时间）jtj假设所需要的铲车的台数 N2 模型的建立21 运输车调度方案的模型对于运输车的调度方案，我们建立单目标规划的非线性模型使得运输费用最小，模型如下。2.1.1 目标函数的建立考虑使运输费用最小时，目标函数包括两个方面的费用：空载费用和重载费用。其中，空载费用为第 37 号站点直接到达的其他各 点所花的费用；而重载费用为上一个垃 圾 站点（除 37 号站点）到下一个 点（包括 37 号站点）所花的费用，表示如下：垃 圾 站 垃 圾 站：Min371,361,37,)(ijjitt dxaudbF2.1.2 约束条件的确立（1）对于各个垃圾站点，只有一
9、辆运输车经过，即每个站点的运进点和运出点均是有且只有一个，即： )36,21(;371, tuit ),(;371, tiit其中， )37,21,(;,10, jijiuji 号 垃 圾 站 点号 垃 圾 站 点 到 了 第表 示 运 输 车 不 从 第 号 垃 圾 站 点号 垃 圾 站 点 到 了 第表 示 运 输 车 从 第（2）运输车到达某个站点后，必须将此站点的所有垃圾带走： )36,21(;)(371, txsuxkttkt（3）不允许出现自己往自己站点运输垃圾的现象,即当 时有：ji)372,(;0, jiuji（4）不允许从第 37 号站点（垃圾处理站）运出垃圾，即： )6,1
10、(;,37jxj（5）各 点的垃圾都必须在当天清理完毕，不允许有滞留：垃 圾 站 513617,ix（6）各垃圾运输车不允许有超载现象，即每辆车的载重最多为 6 吨：)37,2;36,2(6, jixji21.3 单目标规划模型在给出了目标函数和约束条件后，即可得到一个使得运输费用最小的单目标规划模型如下：Min371,361,37,)(ijjitt dxaudbF )37,21;36,21(65),(03721)36,(),(2.,317, ,371, jixjiutxsxtutsjiiji ktttktiitit（1）2.2 铲车调度方案的模型此模型的建立基于上问模型的结果，从以上运输车的
11、调度方案得出共有 10 条路径，在此模型中，我们将 10 条路径分别看作 10 个节点，而把垃圾处理站看作为第 11 个节点（以下将各路径均称作节点） ，建立了使铲车行驶所需费用最小的模型。在此需要说明的是，由于运输车的路径已经确定，我们只能让铲车跟随着运输车，而不能让运输车在垃圾站点等待铲车。由此可以确定,铲车必须跟随着运输车行走完一条路径，才能转到其他路径继续工作。而对于各路径，其行走方案已定，所以各路径内的费用已经确定。因此，我们需要做的是，找出一种调度方案使铲车在各路径之间的行走所需的费用为最小。2.2.1 目标函数的建立各路径内的费用已定，因此我们建立以下使铲车在各路径之间行走所需费
12、用最小的目标函数如下： Nkij kjijiudbFMin1,2:2.2.2 约束条件的确立：（1）对于 1 到 10 号的每个节点，只允许一辆铲车通过，且只通过一次： Nkjkjttu1, )10,2(Nkikttu1, )10,2(（2）所有的铲车必须从第 11 号节点（垃圾处理站）出发，并最终回到 11 号节点，即从11 号节点发出的铲车数和最终返回 11 号节点的铲车数均为 N：uuNktkNktt 10,10,（3）为保证每辆铲车均从 11 号节点出发最终回到 11 号节点，且不重复已走的路径，则需控制铲车所走路径均为一个环，即对于每个节点，只要有铲车进入则必有铲车出，不进则无出，进
13、与出的状态保持一致： ),21;,21(1,1, Nktuikitikt （4）对于每个节点，不允许出现铲车向自己节点运行的路径： ),21;,21(0, kiuki （5）不允许出现铲车的路径为，除 11 号节点以外，在其他节点相互运行的路径： ),21;0,21,(, Nktiukitkti （6）由于垃圾的运输均在夜间进行，则每辆铲车的工作时间不能大于 9 个小时（即假定工作时间为从晚 21：00早 6：00） ，另外，由于题目中没有给定铲车的运行速度，不妨假定其平均速度与运输车的平均速度相同，为 40 公里/小时，的约束条件为： ),21(9)40/(1,1, Nkutudijkjii
14、j kjiji 2.2.3 铲车规划模型在给出了目标函数和约束条件后，即可得到一个使得铲车运行费用最小的单目标规划模型如下：Nkij kjijiudbFMin1,2: ),21(9)40/( ),21;,21,(;0,;,)10,2(,. ,1,1,1,001,1,1, NkutudktiNtututsijjiij kjijiitktiikitiktNtNkttkiktNjjt （2）2.3 载重量不同的运输车调度方案模型此问在第一问的基础上，通过改变垃圾运输车载重量的大小，从而得到垃圾处理厂在拥有不同载重量的运输车时，采用怎样的运输方案使得所花运输费用最少。此模型的目标函数与第一问中的运输车
15、调度方案模型相同，只是在约束条件上将第（6）个约束条件中的载重最多为 6 吨变成最多为 8 吨，：Min371,361,37,)(ijjitt dxaudbF （3）)37,21;36,21(85),(03721)36,(),(21.,3617, ,371, jixjiutxsxtutsjiiji ktttktiitit从而可求出在拥有不同载重量运输车的情况下，各运输车的调度方案。模型的求解3 运输车调度方案模型的求解利用 LINGO10 编程，对运输车调度方案的模型（1）进行求解,求得各垃圾站点的运输方案如表 2 所示，此时，求得将所有垃圾运回到 37 号站点运输车所需费用为 2335.77
16、 元。表 2：各运输路径所包含的垃圾站点、运输量及所需时间路径 包含的站点 运输垃圾总量 每条线路所需时间 1 37 30 29 27 37 5.3 吨 3 小时 46 分钟2 37 28 26 21 25 19 37 5.7 吨 3 小时 02 分钟3 37 36 23 33 32 37 5.5 吨 2 小时 46 分钟4 37 24 18 35 20 37 5.2 吨 2 小时 22 分钟5 37 34 17 16 2 37 5.0 吨 2 小时 7 分钟6 37 15 13 7 4 37 5.6 吨 2 小时 4 分钟7 37 14 31 5 6 37 5.85 吨 1 小时 46 分钟
17、8 37 22 10 37 3.3 吨 1 小时 23 分钟9 37 12 8 3 37 5.55 吨 1 小时 30 分钟10 37 11 9 1 37 4.0 吨 1 小时 30 分钟从上表可以看出，对于这 10 条路径上的垃圾总量，有 8 条都超过了 5 吨，另两条也超过了载重量的一半，运输车得到了充分地利用，结果非常好。各运输路径以图示表示如下：图 1：运输车行走路线图由图 1 可以看出，10 条路径中只有 2 条路径有交叉点，其他路径各自互不干扰，结果很理想。由题目可知，每台运输车的平均工作时间为 4 小时，根据此条件对以上 10条路径进行规划，发现用 6 台运输车即可按要求行走完 10 条路径，所以，处理站只需投入 6 台垃圾运输车即可完成任务。各运输车行走的路径分别表示如下：表 3：各运输车的行走路径、具体路线及所需时间运输车编号 路径编号 行走路线 所需时间第一辆 2 37 28 26 21 25 19 37 3 小时 02 分钟第二辆 1 37 30 29 27 37 3 小时 46 分钟8 37 22 10 37第三辆3 37 36 23 33 32 374 小时 9 分钟9 37 12 8 3 37第四辆5 37 34 17 16 2 373 小时 37 分钟4 37 24 18 35 20 37第五辆10 37 11 9 1 373 小时 52 分钟
