垃圾运输问题模型.docVIP

关于垃圾运输问题的数学模型 摘要 本文对于垃圾运输问题的优化，通过运用图论的TSP问题的有关知识对题目给出的坐标数据进行了处理，根据从最远点开始运载垃圾运输费用最低的原则，以及不走回路的前提，在条件时间约束下，建立了运输车和铲车的调度优化模型，得到运输车和铲车的安排路线和时间，在垃圾运输问题上，安排了六辆运输车，三辆铲车的最少调动车辆数目，达到最少运输费用。 关键词：哈密顿图；TSP问题；垃圾集中点；重载起点；运输路线 1 问题重述 某城区有36个垃圾集中点，每天都要从垃圾处理厂（第 37 号节点）出发将垃圾运回。现用一种载重 6 吨的运输车到期每个垃圾点载运垃圾,并需要用 10 分钟的时间装车，运输车平均速度为 40 公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4 小时。运输车重载运费 1.8 元 / 吨公里；运输车和装垃圾用的铲车空载费用 0.4 元 / 公里；并且假定街道方向均平行于坐标轴。要求给出满意的运输调度方案，使总运费最少。问题：1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用） 垃圾集中点坐标数据表如下表1： 表1:垃圾点地理坐标数据表 序号 站点编号 垃圾量 T 坐标 (km) 序号 站点编号 垃圾量 T 坐标 (km) x y x y 1 1 1.50 3 2 20 15 1.40 19 9 2 2 1.50 1 5 21 32 1.20 22 5 3 3 0.55 5 4 22 22 1.80 21 0 4 4 1.20 4 7 23 23 1.40 27 9 5 6 0.85 0 8 24 24 1.60 15 19 6 5 1.30 3 11 25 25 1.60 15 14 7 7 1.20 7 9 26 26 1.00 20 17 8 8 2.30 9 6 27 27 2.00 21 13 9 9 1.40 10 2 28 28 1.00 24 20 10 10 1.50 14 0 29 29 2.10 25 16 11 11 1.10 17 3 30 30 1.20 28 18 12 12 2.70 14 6 31 31 1.90 5 12 13 13 1.80 12 9 32 21 1.30 17 16 14 14 1.80 10 12 33 33 1.60 25 7 15 20 0.60 7 14 34 34 1.20 9 20 16 16 1.50 2 16 35 35 1.50 9 15 17 17 0.80 6 18 36 36 1.30 30 12 18 18 1.50 11 17 37 37 0.00 0 0 19 19 0.80 15 12  2 模型假设 2.1假设运输车重载与空载行走时间相同； 2.2假设运输车在工作过程中没有任何耽误； 2.3假设铲车的速度与运输车的速度一样； 2.4只要在满足每辆运输车在每天平均工作四小时的前提下,假设运输车工作时间允许超过四小时； 2.5假设运输车每天安排所走的路线不是固定不变的，有一个值班制度,使每辆运输车每天平均工作大约四小时。 3 符号说明 ：第个垃圾集中点的垃圾量,； ：第个垃圾集中点的横坐标，； ：第个垃圾集中点的纵坐标，； ：垃圾运输路线总条数； ：第条路线上垃圾集中点的个数，； :安排运输车的总数量； ：第条路线上的第个垃圾集中点的横坐标，； ：第条路线上的第个垃圾集中点的垃圾量，； :第条路线所需要的总时间； ：第辆车的运输总时间； ：运输车空载的总费用； ：运输车重载的总费用； ：运输车的总费用； ：铲车1的空载费用； ：铲车2的空载费用； ：铲车3的空载费用； ：全部铲车空载的总费用。 4 运输车调度优化模型 4.1 确定运输车路线算法 由于最远的垃圾集中点的运输时间不超过运输车每天平均工作时间，所以可以先不考虑时间的约束。从而建立如下算法： 确定重载起点 由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费用是不变的，所以为了使总运输费用最少，只要使空载的费用最少，即尽量安排较远的垃圾集中点在同一路线上，从而确定重载起点. 2）确定运输车路线走向 要求运输时走最短的路线，以及运输费用最低，而且