论文_final(垃圾运输路线)

《论文_final(垃圾运输路线)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C题：生活垃圾管理系统摘要本文对城市垃圾运输车的分配路线进行入了深入研究。面对这个庞大而复杂的系统，在解决问题时，我们把它看作一个复杂化的旅行商问题，并主要运用遗传算法（Genetic Algorithm，GA）建立数学模型，找到了各个垃圾站点之间的近似最短路径。然后以全局优化为解题目标，即在规定的时间里，尽可能让发车数量少，行车里程短，每辆车的工作时间尽量均衡去完成整个任务。根据我们的建立模型，使每辆运输船最大化地接近约束条件，在满足所有约束条件的前提下遍历完整个最短路径。根据Matlab求解

2、，具体安排路径为：车辆编号行程具体路线11→47→35→52→35→34→36→40→52→40→3→52→3→2→4→49→52→46→52→121→48→50→38→42→52→42→51→52→51→52→131→44→39→52→39→37→52→37→5241→22→45→52→45→41→33→52→33→43→52→151→26→21→30→52→30→19→28→52→161→12→18→14→52→14→52→14→10→52→171→24→16→15→52→15→6→25→7

3、→52→181→9→32→52→27→5→8→52→191→11→29→52→29→31→20→52→23→17→13→52→1之后，我们运用其他算法做对比（本文以蚁群算法为主要对比对象），对我们所建立模型的合理性和算法的稳定性做出具体分析,最后我们对全文做出总结，并提出了模型的改进。虽然TSP算法能找到近似最优解，但是他没有考虑题中的中转站的位置对最短路径的影响，因此我们对模型进行了修改，提出了基于遗传的VRP算法（Vehicle Routing Problem, 即多回路运输问题）的模型，并

4、作出简单分析。关键词:最短路径遗传算法全局优化TSP问题　VRP问题一．问题重述人们正面临着城市生活垃圾所带来的威胁。随着人类生产和生活的不断发展，由此而产生的垃圾对生态环境及人类生存带来极大的威胁，成为重要的社会问题。城市生活垃圾的年增长速度达8-10%，严重污染环境。中国目前处置水平低，管理办法不多，更是急待解决的问题。在这方面，世界许多国家在谋求解决城市生活垃圾过程中，产生出许多好的办法，并在此过程中总结了经验和教训。我们知道，城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收

5、集与运输，这一过程称为城市垃圾的收运。收运过程可简述如下：某城市有多个行政区，每个区内均有一个车库，假设某一车库拥有最大装载量为w的垃圾收集车k辆，并且该区的垃圾收集点（待收集垃圾的点）有n个，该城市共有垃圾中转站p座。每天k辆垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。以上收运过程均在各点的工作区间之内完成。现考虑以下问题：1.查阅相关文献，建立垃圾

6、收运路线的数学模型，设计出有效的算法，使垃圾收运车辆尽可能少，行车里程尽可能短或者垃圾收运时间尽可能少。2.针对附录中给出的数据，求解模型。并且对模型的适用性、算法的稳健性做出分析。二．符号说明字母表示符号意义垃圾车的数量每辆垃圾车的容量（所有车辆具有相同的能力）第i辆垃圾车第辆垃圾车行驶的路程长度从第个节点到第个节点的距离第k辆车离开第i个节点时车中的垃圾量第i个节点的垃圾量车辆由点i驶向点j从第个节点到第个节点的行车时间第k辆车的收集过程中进入中转站的次数每辆车的最大容量种群规模终止代数交叉

7、概率变异概率染色体三．问题的分析此问题我们可看作一个复杂化的多人旅行商问题，然而大规模的TSP问题通常无法求得最优解。回顾这些年对多人TSP问题的研究可以发现一些问题。其中最主要的的是，对多人TSP问题的研究停留在以所有成员路径总和最小为标准的单人TSP问题，从而可以运用已有的单人TSP问题求解方法。但是，以所有成员路径总和最小值为优化标准对另一类多人ＴＳＰ问题却无能为力。我们能做的，就是运用一个有效的算法，对本问题建立模型，使其优化程度高。　　对本问题进一步研究，我们发现它比一般的TSP问题主

8、要有以下几个难点。１，题目的约束条件很多，例如每辆车每次的装载量和当天最大装载量，上班时间。２，每次装载量到达上限后，都要往返中转站，而不是在当前垃圾站继续装载或去下一个垃圾站，因此会大大增加计算量。３，某一些垃圾站的垃圾数由于量大，会被多次到访进行装运。４，某几辆车可能会到同一个垃圾站共同完成任务。可以看出，此题比一般TSP问题的复杂程度高出许多。面对这样大规模的大规模的TSP问题，运用精确算法的效果没有近似算法的效果好。因此，我们选择具有良好的全局搜索能力的遗传算法（Genetic　Algo