文档介绍：,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。我们参赛选择的题号是(从A/B/C中选择一项填写):C 我们的参赛报名号为(如果赛区设置报名号的话):所属学院(请填写完整的全名):计算机科学与技术学院参赛队员(打印并签名)::2011年7月9日评阅编号(教师评阅时填写):C题:生活垃圾管理系统摘要随着我国城市经济发展和人口的增加,城市生活垃圾产生量在迅速增加,垃圾的收集运输问题越来越受到关注,而收集运输工作的科学性和经济性的关键是合理的安排收集和运输路线。本文将针对城市垃圾的收集与运输的优化过程进行讨论。为了在垃圾收运过程中可以达到“路径短,时间少,车辆少”的目标,我们深入分析建立了两种模型:基于图论的最短路径模型和基于遗传算法的规划模型。模型一:基于图论的最短路径模型。首先假定一辆无限大载重的车能够跑完全程,利用图论知识,用C++编程求解出遍历50个站点的哈密顿回路,得到垃圾车收运的最短路线。然后基于此哈密顿回路,某辆垃圾车从车库出发,逐步算出垃圾车在行驶过程中装载的垃圾量,当垃圾量达到垃圾车的最大装载量1吨时,垃圾车便开往中转站卸下所有垃圾,然后返回站点继续收集垃圾。由此可得垃圾车前往中转站的次数为25次,即可将该条线路划分为25个子线路。最后从第一条子路线开始,逐步求解出垃圾车在行驶过程中所用的时间,当收运垃圾时间总接近垃圾车工作总时间时,则另分配车辆继续按照已求出的最短路线来收运垃圾。根据上述方法,计算可知需将任务分派给8辆车来完成,所有垃圾车在该线路上收集垃圾时所行驶的总里程为897752m,。模型二:基于遗传算法的规划模型。针对模型一中存在的不足,我们采用遗传算法进行改进。首先将问题类比物流配送中的车辆调度问题;其次建立车辆路线安排的数学模型,把总运输距离最小作为目标函数,并结合车容量1吨、时间窗8小时等约束条件,得到车辆优化调度的规划模型;最后,根据上述规划模型并结合遗传算法中选择、交叉、变异等基本操作,使问题的解一代一代的优化,最终逼近最优解。通过MATLAB软件编程计算,得到最终结果为:车辆数目为6辆,行驶的总里程为6225959m,。模型适用性和算法的稳健性:模型一利用了图论中的哈密顿回路,此模型可以解决类似TSP的一类问题;模型二利用了遗传算法,可以用于解决车辆优化调度等一类问题。两个模型都具有广泛的适用性。两个模型中分别用到的“求解哈密顿回路”算法和遗传算法,都是比较成熟的算法,具有良好的鲁棒性。关键词:图论哈密顿回路规划模型遗传算法一、,垃圾分类处理与清运的优化问题也开始受到了大家的重视。城市生活垃圾的年增长速度达8-10%,严重污染环境。城市垃圾管理包括计划、组织、行政、金融、法律和工程等多方面,并涉及到城市生活垃圾收集、运输和处置。而中国目前处置水平低,管理办法不多,更是急待解决的问题。在这方面,世界许多国家在谋求解决城市生活垃圾过程中,产生出许多好的办法,并在此过程中总结了经验和教训。,并且该区的垃圾收集点(待收集垃圾的点)有50个,该城市共有垃圾中转站1座。每天k辆垃圾车从车库出发,经过收集点收集垃圾,当垃圾负载达到最大装载量时,垃圾车运往中转站,在中转站卸下所有收运的垃圾,然后再出站收集垃圾,如此反复,直到所有收集点的垃圾都被收集完,垃圾车返回车库。以上收运过程均在车库的工作时间进行。,建立垃圾收运路线的数学模型,设计出有效的算法,使垃圾收运车辆尽可能少,行车里程尽可能短或者垃圾收运时间尽可能少。,求解模型,并对模型的结果做出合理分析和解释。二、问题分析本题是一个在城市生活垃圾收运过程中,构造一条“路径短,时间少,车辆少”收运路线的问题。,直接求出遍历各个垃圾站点的最短路径,并进一步求出最少的车辆和最短的时间为达到城市垃圾的收运车辆尽可能少,行车里程尽可能短或者垃圾收运时间尽可能少的目标,我们首先考虑如何在满足工作时间和载重量限制的条件下,使垃圾车的行驶路径最短。根据附录一中的站点坐标,假定一辆车可以