垃圾运输问题

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

1、基于最优搜索算法和0-1规划的垃圾运输模型摘要本文要求我们规划深圳市南山区的垃圾运输问题，首先确定了各垃圾转运站和垃圾处理厂的坐标，然后运用优化理论，基于最优搜索和最优分配的优化理论，求解出了拖车的具体调度方案。随后，在假设增加一个垃圾处理厂的前提下，确定了最优的垃圾处理厂的坐标，具体分析如下：对于问题一，我们通过题目所给的地图，对原图建立坐标系，得到各个垃圾转运站的初始坐标。再通过谷歌地图查找经纬度，以及百度的API坐标转换工具，得到实际距离与图中距离的比例关系，将38个转运站及两个垃圾处理站的初始坐标转换成实际坐标（单位为公里）。而后得到根据垃圾转运站去更近的垃圾处理厂

2、处理的原则，将垃圾转运站分类。之后根据最优搜索的理论，通过matlab编程得到最优的运输路线方案，再根据最优分配的理论编写了lingo代码，从而得到每辆车的具体调度方案，其中南山垃圾焚烧厂安排6辆拖车，下坪固体废弃物填埋场安排3辆拖车。同时也求出了总的运营费用为236287元。之后我们又通过遗传算法与本题采用的方法进行了比较分析，从算法的准确性来看，本题算法更好。对于问题二，我们通过在南山区内随机模拟第三个处理厂的位置，计算出38个垃圾站到3个站的最短距离，然后以38个垃圾站到处理厂距离和最小为目标函数建立了两种类似的0-1线性规划模型，运用lingo求解得到两个处理厂的位

3、置，然后以新建处理厂与南山区之间的区域包涵的垃圾站输与总垃圾站个数的比值为处理厂位置的合理性指标，得到两个点的比值都是44.7%然后根据距离最短，得到处理厂的坐标为(33.16563，2.637373),然后根据对居民区的考虑，对处理厂位置的人性化做了处理，增加约束求出更加人性化的处理厂坐标（31.630,1.4）。关键词：垃圾运输最优搜索遗传算法选址1一、问题重述1.1问题背景深圳市南山区环境卫生管理总站负责南山区所有38个垃圾转运站的垃圾清运，每天晚上都要从垃圾处理厂出发用拖车将垃圾运回，对垃圾作回收、填埋和焚烧等处理。1.2问题条件南山区的垃圾清运设备主要是大型拖车，

4、每辆大型拖车可装载十吨垃圾，并且专门用于从转运站运载垃圾到垃圾处理厂。大型拖车的平均吨耗油25L—30L柴油/百公里。每个垃圾转运站需要用10分钟的时间装车，运输车平均速度为60公里／小时（夜里运输，不考虑塞车现象），每台车每晚平均工作6小时。运输车重载运费20元/吨公里，运输车空载费用5元/公里。1.3题目要求题目要求通过适当的假设，为管理总站设计出满意的运输调度方案1.4解决的问题（1）给出满意的调度方案（投入运输车台数，每台车的调度方案，运营费用等）。（2）如果计划在区内再增加一个垃圾处理厂，该厂应该建在什么地方？二、问题分析与符号说明2.1问题分析1.问题一的分析：

5、（1）本题首先要获得各垃圾转运站、垃圾处理厂之间的距离，之后便是实现运营费用、车辆数量优化的多目标最优问题。最低这是一个优化问题。在保证能够将每个垃圾转运站的垃圾全都运到垃圾处理厂的情况下，确定派出的车辆数，以及每辆车的运输方案，使投入的成本最低，产生运营费用最小。考虑到求解的便利性，先把目标定为运营费用的最优。运营费用包括两个方面：油费和运输费。油费在载重总量相同时，与路程存在线性的正比例关系，路程越短油费越低。而运输费用，也与运输路程存在正比例的类线性关系。因此，我们可以把运营费用的最优简化成运输距离的最优。（2）由于垃圾处理站有两个，我们需要考虑每个转运站的处理厂的选

6、择，考虑到运输距离的最优，因此采取每个垃圾转运站去更近的垃圾处理厂处理的判断。（3）对于每个垃圾转运站的垃圾总量，对于整10的部分，毫无疑问只需派拖车拖运即可，而对于额外的5吨的部分，则需要做一个搭配。之后再对所有的拖车的方案进行一个分配，使得每辆拖车的平均工作时间为6小时左右。2.问题二的分析：如果计划在区内再增加一个垃圾处理厂，则需要考虑将38个垃圾站分配到3个处理厂，使38个垃圾站到3个处理厂的运营费用最小，将问题简化成38个点到3个处理厂的距离最小的问题，通过运输车的载重量约束和垃圾站的垃圾量的约束和最小距离的两种求法建立了两个0-1线性规划模型。运用lingo进行

7、求解得出了两个第三个处理厂的坐标，然后根据新建处理厂和南山区处理厂之间包涵的垃圾站个数与总数的比值来衡量处理厂的合理性，比较路程所用的长短，得到最终的处理厂坐标。22.2符号说明：符号字母符号意义单位a柴油价格元/升L耗油量升第k辆车去第i个垃圾站需要的趟数ki第k辆车去第i，j两个站之间的距离公里dkij第k辆车去的第i个垃圾站离处理厂的距离公里dki第i个垃圾站到第1，2，3个处理厂之间的距离dd,,d1i2i3ix若从第i个垃圾站去第j个垃圾站x为1，否则为0ijijf/F费用元第k辆车去第i个垃圾站所运垃