垃圾运输中最优调度方案的研究2.doc

垃圾运输中最优调度方案的研究 谢海明 邓书莉 蔡葵玉 刘文 刘国友 摘 要 本文就现实生活中的垃圾运输问题的调度方案予以研究，经分析发现本问题属于难问题，目前求解尤为困难。本文通过对问题的全面分析和合理的假设，采用规划的理论建立了单目标的非线性规划的数学模型。通过对算法的技巧性设计，使得变量数目由2000多个减少到800多个，运用软件得到了全局最优解，对此类问题的求解提供了一种较优的方案。 对于题中的问题（1），属于典型的难问题，而且更复杂的是，其中还包含着垃圾量和运输费用的累积计算问题，因此，文中以运输车所花费用最少为目标函数，以运输车载重量的大小、当天必须将所有垃圾清理完等为约束条件，以运输车是否从一个垃圾站点到达另一个垃圾站点为决策变量，建立了使得运输费用最小的单目标的非线性规划模型。运用求解，得出了最优的运输路线为10条，此时运输所花费用为2335.77元。通过分析，发现只需6辆运输车（载重量为6吨）即可完成所有任务，且每辆运输车的工作时间均在4个小时左右。具体结果见文中表3。 对于问题（2），当把已求出的10条路线看作为10个节点时，此时铲车运行路线的确定就成了单纯的TSP问题。因此建立了以运行路径最短为目标的单目标非线性规划模型。从而求出了使铲车费用最少的3条运行路线，且各条路线的工作时间较均衡。因此，处理站需投入3台铲车才能完成所有装载任务，且求得铲车所花费用为202.0元，三辆铲车的具体运行路线见文中表4。文中，我们假定垃圾处理站的运输工作从晚21：00开始，根据各铲车的运输路线和所花时间的大小，将铲车和运输车相互配合进行工作的时间做出了详细的安排见表5。 对于问题（3），要求给出，当有载重量为4吨、6吨、8吨三种运输车和分别求解，得出两种调度方案，但总的运输费用不变，均为2326.17元；对于方案一，有9条路径，分别需要4吨的运输车1辆；6吨的运输车2辆；8吨的运输车5辆，各运输车具体的运输线路见文中表8。对于方案二，有10条路径，分别需要4吨的运输车1辆；6吨的运输车1辆；8吨的运输车4辆，各运输车具体的运输线路见文中表10。 最后，对模型的优缺点进行了分析，并给出了模型的改进意见，对解决实际问题具有一定的指导意义。 关键字：难问题 垃圾运输的调度 非线性规划 1.问题的重述 某城区有个垃圾集中点，每天都要垃圾处理厂（第号节点）将垃圾。现有一种载重 6吨的运输车每个垃圾点需要用分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4小时。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。满意的运输调度方案以及计算程序运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）如果有载重量为4吨、6吨、8吨三种运输车，又如何调度 每天运输前第个垃圾站点的垃圾量； 第个垃圾站点向第个垃圾站点运输的垃圾量； 运输车是否从第个垃圾站点向第个垃圾站点运输的0-1变量； 第辆铲车是否从第条路径向第条路径运输的0-1变量； 第个垃圾站点和第个垃圾站点之间的距离； 第条路径到第条路径的有向距离； 垃圾运输车的单位量货物每公里的运输费用； 垃圾运输车和铲车每公里的空载费用； 铲车通过第条路径所需要的时间（包括在各垃圾站点装车的时间） 假设所需要的铲车的台数 4.问题的分析 对于第（1）问，该问题属于NP难问题。所不同的是，对于运输车调度方案的设计，不能仅仅考虑使运输车的行走路线最短（即TSP问题），因为此处还存在着垃圾的累积运输的花费问题，因此，我们的目标函数应该是使得所有运输的花费最少。在建模过程中，我们无需考虑投入的运输车台数，只需对各条路径所花费的时间进行和各运输车载重量约束即可，至于投入的车辆数，在各条路径确定后，计算出各路径运输所花费的时间，再根据题目中要求的每辆车平均工作时间为4小时左右进行计算即可。 第（2）问中，对于铲车的调度方案，因其无累积计算问题，因此只需要在已确定的各运输路径的基础上，使得铲车的行驶路径为最短。在此方案中，我们将已确定的各条路径看作为节点，那么铲车的调度方案就变成了单纯的TSP问题。建立使铲车运费最少（亦即路径最短）的非线性规划模型，在此需注意的是，由于垃圾运输为夜间运输，所以每辆铲车的工作时间也受到一定的限制，文中，我们假定铲车的工作时间为从（晚21：00～早6：00），因此每辆铲车的工作时间最多为9个小时，再由所有运输车完成任务所需的总时间判定所需铲车的台数，之后可以根据具体情况进行调整。同时应注意，由于运输车有工作时间的限制，而铲车没有严格的