要步骤如下任取初始圈„,„„图示例图对所有的，垃圾车前往中转站卸下垃圾。所以构成第个子路线。由上述方法可以求出各个子路线，设为第个子路线的总路程，表示垃圾车的行驶速度，结合题目中中给出的数据及距离的计算公式，我们可以算出垃圾收运车在各个子路线上所花费的时间，„„，考虑到垃圾收运车的工作时间每天最多经过的垃圾收集点个数和每天的总载重量的限制，需要将这些子路线分配给多辆车来完成，在保证每辆车都能规定时间内回到车库的前提下，每辆车的工作时间都尽量接近小时的工作时长，这样就得到了垃圾收运车辆数目和每辆车的收运路线。例如第辆车的收运路线的分配过程如下第个子路线的时间为小时，第二个子路线的时间为小时，第三个子路线的时间为小时，第四个子路线的时间为小时，这四个子路线的总时间为小时，而第五个子路线的时间为小时，小时，这样就超过了垃圾收运车的工作时长，并且前四个子路线的总垃圾收集站点个数不超过，所以将前四个子路线分配给第辆车。模型的求解站点坐标首先根据附录中的数据，用编程代码见附录二可以得到车库中转站垃圾收集点的分布图如下图二站点坐标图遍历路径根据如图所示站点的坐标，先假设垃圾车的载重量无限大，可次将垃圾全部收集完，因此暂不考虑中转站问题，而直接从车库出发，找到条遍历所有收集点的最短路径，从而将问题转化成求解哈密顿回路的问题，这样就可求得最短收集路线。利用程序代码见附录三可得到最佳路径如下图三最佳路径注此程序结果中的站点数为题目附录中给出的站点数加，车库标号为。由此可知最短路径为表示车库，其余为题目附录中的站点数运用画出遍历路径如下图四最短路径根据上图的最佳路径，可列出如下数据表格表各站点信息序号经过站点号站点垃圾量装卸时间垃圾运往中转站后该站点剩余垃圾量即用柱状图表示该站点的垃圾量和剩余垃圾量为图四站点垃圾与剩余垃圾量柱状图所用车辆及路径根据表格与图三，垃圾收运车沿求出的路线收集垃圾，考虑垃圾车的最大载重量和工作时间，在上述求解出最短路径后，用辆垃圾收运车按照图二中的遍历路径开始收集垃圾，当载重量接近或达到吨时，运往中转站，再接着收集余下的垃圾。由此，我们可以得出辆垃圾车的收运路线。从上述的最短路线的结果中，可以看出垃圾车要去中转站次，则最短路径被分成个子线路。由于有时间限制，所以需要多辆车去收集垃圾，经过计算，我们得出需要辆车来收集垃圾以及每辆车的收运路线。以下是每辆车的收运路线第辆车中转站中转站中转站车库中转站第二辆车中转站中转站中转站车库第三辆车中转站中转站中转站车库第四辆车中转站中转站中转站车库第五辆车中转站中转站中转站车库第六辆车中转站中转站中转站车库第七辆车中转站中转站中转站车库第八辆车中转中转站中转站中转站车库站由子路线及每辆车所用的时间可得如下表格表二路线分布表子路线号车号路线运载量时间子线路号车号路线运载量时间子线路号车号路线运载量时间模型二基于遗传算法的规划模型模型的建立对问题的求解，模型是通过图论中的哈密顿回路来解决的。在求解哈密顿回路的过程，因为事先未知前往中转站的次数，所以没有考虑中转站，这样就会造成定的误差。为了减小误差，进步接近最优解，我们建立模型二。收运垃圾的过程可以概述为车辆从车库出发，按照定的路线，将各个收集点的垃圾集中后运往统的中转站处理。现将问题反过来思考收运车从中转站出发，将中转站的垃圾按定的路线运往各收集点。这样听起来似乎不合常理，但是，问题就转化为了物流配送中的车辆调度问题。中转站即对应配送中心，收集点的垃圾量对应各个客户的需求量。其目标函数和约束条件基本相同。所以，借用物流配送中的车辆调度问题模型来求解。而此模型较好而又成熟的方法则是遗传算法。考虑到垃圾收运过程中，每辆垃圾车到从中转站到车库的次数是固定的只有完成工作之后从中转站回到车库为次，建模过程中，垃圾车以中转站为起点，前往各收集站点收运垃圾。下边将基于城市垃圾收集路径优化问题的特殊性，采用改进的遗传算法来建立改进后的模型，算法的主要步骤如下车辆调度数学模型安排垃圾收运车的收运路线问题，使总运输距离最小作为目标函数，根据题中算法终止条件最短路径连续保持不变代数,最短路经出现代数最短路经终止条件终止条件二最短路经长度最初路经长度零化路径长度零化适应概率路径长度计算个体路径长度对路径长度调整，增加起始点到路径首尾点的距离累计总路径长度计算个体路径长度更新最短路径长度更新最短路径适应概率个体总和。已作调整，大小作了调换显示适应概率累积概率显示累积概率零化新种群甩随机数显示甩出的随机数显示被选中的新种群个体初始化后代改进方向优势个体保留，劣势个体不参与交叉选择另参与交叉的个体产生,里的随机数确定交叉宽度,随机产生交叉点，做差确保不溢出显示交叉后子代显示突变后子代,生活垃圾管理系统摘要随着我国城市经济发展和人口的增加，城市生活垃圾产生量在迅速增加，垃圾的收集运输问题越来越受到关注，而收集运输工作的科学性和经济性的关键是合理的安排收集和运输路线。本文将针对城市垃圾的收集与运输的优化过程进行讨论。为了在垃圾收运过程中可以达到路径短，时间少，车辆少的目标,我们深入分析建立了两种模型基于图论的最短路径模型和基于遗传算法的规划模型。模型基于图论的最短路径模型。首先假定辆无限大载重的车能够跑完全程，利用图论知识，用编程求解出遍历个站点的哈密顿回路，得到垃圾车收运的最短路线。然后基于此哈密顿回路，辆垃圾车从车库出发，逐步算出垃圾车在行驶过程中装载的垃圾量，当垃圾量达到垃圾车的最大装载量吨时，垃圾车便开往中转站卸下所有垃圾，然后返回站点继续收集垃圾。由此可得垃圾车前往中转站的次数为次，即可将该条线路划分为个子线路。最后从第条子路线开始，逐步求解出垃圾车在行驶过程中所用的时间，当收运垃圾时间总接近垃圾车工作总时间时，则另分配车辆继续按照已求出的最短路线来收运垃圾。根据上述方法，计算可知需将任务分派给辆车来完成，所有垃圾车在该线路上收集垃圾时所行驶的总里程为，花费的总时间为。模型二基于遗传算法的规划模型。针对模型中存在的不足，我们采用遗传算法进行改进。首先将问题类比物流配送中的车辆调度问题其次建立车辆路线安排的数学模型，把总运输距离最小作为目标函数，并结合车容量吨时间窗小时等约束条件，得到车辆优化调度的规划模型最后，根据上述规划模型并结合遗传算法中选择交叉变异等基本操作，使问题的解代代的优化，最终逼近最优解。通过软件编程计算，得到最终结果为车辆数目为辆，行驶的总里程为，花费的总时间为。模型适用性和算法的稳健性模型利用了图论中的哈密顿回路，此模型可以解决类似的类问题模型二利用了遗传算法，可以用于解决车辆优化调度等类问题。两个模型都具有广泛的适用性。两个模型中分别用到的求解哈密顿回路算法和遗传算法，都是比较成熟的算法，具有良好的鲁棒性。关键词图论哈密顿回路规划模型遗传算法问题重述问题背景随着人类生活水平的提高以及城市垃圾处理事业的发展，垃圾分类处理与清运的优化问题也开始受到了大家的重视。城市生活垃圾的年增长速度达，严重污染环境。城市垃圾管理包括计划组织行政金融法律和工程等多方面，并涉及到城市生活垃圾收集运输和处置。而中国目前处置水平低，管理办法不多，更是急待解决的问题。在这方面，世界许多国家在谋求解决城市生活垃圾过程中，产生出许多好的办法，并在此过程中总结了经验和教训。涉及材料背景车库拥有最大装载量为吨的垃圾收集车辆，并且该区的垃圾收集点待收集垃圾的点有个，该城市共有垃圾中转站座。每天辆垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。以上收运过程均在车库的工作时间进行。问题提出根据所有的资料，建立垃圾收运路线的数学模型，设计出有效的算法，使垃圾收运车辆尽可能少，行车里程尽可能短或者垃圾收运时间尽可能少。针对附录中给出的数据，求解模型，并对模型的结果做出合理分析和解释。二问题分析本题是个在城市生活垃圾收运过程中,构造条路径短，时间少，车辆少收运路线的问题。不考虑垃圾车运往中转站，直接求出遍历各个垃圾站点的最短路径，并进步求出最少的车辆和最短的时间为达到城市垃圾的收运车辆尽可能少，行车里程尽可能短或者垃圾收运时间尽可能少的目标，我们首先考虑如何在满足工作时间和载重量限制的条件下，使垃圾车的行驶路径最短。根据附录中的站点坐标，假定辆车可以跑完全程，并利用图论的知识，编程得到条哈密顿回路，这样来，便可得到遍历所有站点的最短路径，那么这条路径即为所有车辆行驶的最短路径。在保证了最短路径之后，为了达到在行驶过程中车辆最少，时间最短的目标。我们首先假定车辆必须在装满之后才运往转运站，从而使得每辆车的利用率可以达到最大，进而可以保证车辆达到最少。进步优化模型，并求出最短路径最少车辆和最短时间为了进步优化模型，得到更优解。仔细分析研究问题可知，本题模型与物流配送中的车辆调度模型类似。车辆路径问题是个完全问题，只有在需求点和路段数较少时才可求得精确解。而遗传算法可以很好解决这问题，因此用遗传算法求解该问题是我们的个思路。建立基于遗传算法的规划模型，对车辆调度进行优化，即合理地进行垃圾收运优化，尤其是收运路线的优化，能够提高运行路线的利用率，减少行驶里程和行驶时间。三模型假设每次垃圾车到达垃圾收集点时，该收集点的垃圾产量处于最大值。每辆车只考虑在垃圾装满之后才开往中转站。不考虑周围环境气候等因素对垃圾运输过程中造成的影响。假设垃圾车行驶的速度保持不变。假设各个垃圾点与垃圾点和车库都是可达的。四符号说明主要符号符号意义表示收集车量的序号表示运输车的量数表示每个收集点的垃圾量表示每辆车的载重量表示点到点的距离变量，表示车是否由驶向变量