垃圾运输问题模型

《垃圾运输问题模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关于垃圾运输问题的数学模型摘要本文对于垃圾运输问题的优化，通过运用图论的TSP问题的有关知识对题目给出的坐标数据进行了处理，根据从最远点开始运载垃圾运输费用最低的原则，以及不走回路的前提，在条件时间约束下，建立了运输车和铲车的调度优化模型，得到运输车和铲车的安排路线和时间，在垃圾运输问题上，安排了六辆运输车，三辆铲车的最少调动车辆数目，达到最少运输费用。关键词：哈密顿图；TSP问题；垃圾集中点；重载起点；运输路线1问题重述某城区有36个垃圾集中点，每天都要从垃圾处理厂（第37号节点）出发将垃圾运回。现用一种载重6吨的运输车到期每个垃圾点载运垃圾,并需要用10分钟的时间

2、装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作4小时。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。要求给出满意的运输调度方案，使总运费最少。问题：1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）垃圾集中点坐标数据表如下表1：表1:垃圾点地理坐标数据表序号站点编号垃圾量T坐标(km)序号站点编号垃圾量T坐标(km)xyxy111.503220151.40199221.501521

3、321.20225330.555422221.80210441.204723231.40279560.850824241.601519651.3031125251.601514771.207926261.002017882.309627272.002113991.4010228281.00242010101.5014029292.10251611111.1017330301.20281812122.7014631311.9051213131.8012932211.30171614141.80101233331.6025715200.6071434341.2092016

4、161.5021635351.5091517170.8061836361.30301218181.50111737370.000019190.8015122模型假设2.1假设运输车重载与空载行走时间相同；2.2假设运输车在工作过程中没有任何耽误；2.3假设铲车的速度与运输车的速度一样；2.4只要在满足每辆运输车在每天平均工作四小时的前提下,假设运输车工作时间允许超过四小时；2.5假设运输车每天安排所走的路线不是固定不变的，有一个值班制度,使每辆运输车每天平均工作大约四小时。3符号说明：第个垃圾集中点的垃圾量,；：第个垃圾集中点的横坐标，；：第个垃圾集中点的纵坐标，；：

5、垃圾运输路线总条数；：第条路线上垃圾集中点的个数，；:安排运输车的总数量；：第条路线上的第个垃圾集中点的横坐标，；：第条路线上的第个垃圾集中点的垃圾量，；:第条路线所需要的总时间；：第辆车的运输总时间；：运输车空载的总费用；：运输车重载的总费用；：运输车的总费用；：铲车1的空载费用；：铲车2的空载费用；：铲车3的空载费用；：全部铲车空载的总费用。4运输车调度优化模型4.1确定运输车路线算法由于最远的垃圾集中点的运输时间不超过运输车每天平均工作时间，所以可以先不考虑时间的约束。从而建立如下算法：1)确定重载起点由于每个垃圾集中点的垃圾量及其坐标是不变，重载运输的费用是不

6、变的，所以为了使总运输费用最少，只要使空载的费用最少，即尽量安排较远的垃圾集中点在同一路线上，从而确定重载起点.2）确定运输车路线走向要求运输时走最短的路线，以及运输费用最低，而且由于运输车的重载费用1.8元/吨是空载费用0.4元/吨的4.5倍，为了使运输总费用最少,那只能从最远的点（）开始运载垃圾，下一个点编号为，走一条路线，向垃圾处理站（坐标原点）方向运回。顺次经过的点遵循满足条件：即其横坐标以及纵坐标均不超过前一点的横、纵坐标，并且各点横、纵坐标递减进行搭配，由若干个点组成一条路线。3）确定运输车路线垃圾集中点数根据每个垃圾集中点的垃圾量，每条路线上的垃圾总量不

7、超过运输车的最大运输量：根据上面算法,建立运输车费用优化模型:4.2运输车调度方案在运输过程中假设没有运输车等待的情况,在四个小时的工作时间里,根据垃圾运输费用优化模型，得到垃圾集中点分配的路线及其时间,为了达到安排运输车最少，把所有的路线分成()类，每类配置一辆运输车，每辆运输车的工作时间：5铲车调度优化模型这是一个遍历问题，要确定铲车的行走路线，并使得运输车工作时尽量不要等待铲车，为此，应使铲车跟着运输车跑完一条线路，也就是说，应使铲车跟着运输车铲完一条线路后再接着铲下一条线路。再跑下一条路线。可是运输车的工作时间有限制，都不能超过每日平均工作4