城市生活垃圾收集与运输路线的优化

基于这些路线问题，针对不同的实际情况，需对这些路线问题变形，使其具有实际应用的意义，从而产生了一些新的路线问题的研究领域，如乡村邮政员问题（Rural Postman Problem，RPP）、容量弧路线问题（Capacitated Arc Routing Problem，CARP）、周期性车辆路线问题（Periodic Vehicle Routing Problem，PVRP）。例如，Candida Mourao M通过求解含边界约束的CARP问题得到葡萄牙里斯本（Lisbon）的一个区的生活垃圾收运的优化路线等。
发达国家经过多年的研究实践，对城市生活垃圾的收运模型已有一套完善的理论体系。他们采用的优化模型大多是以运筹学理论为基础的。运筹学包含大量的优化技术，主要分为确定性规划和不确定性规划两大类。其中确定性规划主要有：线性规划（LP）、混合整数规划（MIP）、动态规划（DP）和多目标规划等；不确定性规划主要分为随机规划、区间或灰色规划以及模糊规划。近几十年来，各种运筹学优化技术被广泛用于垃圾线路的优化模型当中。
Heish和Ho（1993），Lund和Tchobanoglous（1994）分别将一个线性规划模型应用于固体废物处理和回收系统的最优化当中，规划结果支持了决策人员的研究工作。1995年，Changt针对经济投入和环境影响之间的冲突进行系统分析，指出在垃圾的收运过程中有很多不确定的因素，运用灰色多目标混合整数规划模型（FIMOMIP ）可以结合多目标分析结构中的间隔数据对模型中的不确定参数进行量化从而得出可行解。之后，Julian等又对灰色规划模型进一步改进，对系统中的未知和不确定参数进行更准确的量化使结果进一步合理。Thierry Kulcar （1996 ）建立了一个混合整数规划模型，用于解决城市生活垃圾的收集管理工程。Mauricio Pantus M等（1999）考虑到资源评价中存在的不确定因素，在评价过程中运用了多目标优化技术和试算法，如运用模拟器ASPENPLUS。Diamadopoulos E等发明了一种整数线性规划模型，用于设计城市固体废物的最优回收系统，此模型应用于Chania含有废纸、玻璃、铝和生活垃圾的废物回收系统，取得了很好的经济效益。2000年，Chang等采用模糊多目标非线性整数规划模型对回收利用率急剧下降地区进行规划，保证花费最小、回收率最大的情况下设置回收站的网络位置和规模，并采用遗传算法进行计算。Cordeau et al.（2002）and Simonetto and Borenstein（2007）应用可操作性的研究方法对垃圾车辆优化路线进行计算机工具的模拟。Badran and El-Haggar （2006）用运筹学开发了基于定量组合的电脑技术用于车辆分配的启发示算法中。
在优化算法方面，采用了现代数学的方法，如智能方法，来求解这些路线问题的数学模型，主要的算法有启发式算法、平行节约启发式算法、禁忌搜索算法、遗传算法等。
启发示算法最早由克拉克（Clarke）和怀特（ Wright）提出的节约法（Saving Method）成功的解决人车辆调度方面的难题，其主要目的就是如何从许多条可供选择的路线中选出最佳的运输路线的方法；Potvin和Rousseau采用禁忌搜索算法（Tabu Search Heuristic）解决一类带时间窗约束的车辆调度问题；Ball等提出了用贪心前瞻搜索法求解多重车辆调度问题（MVRP）；Holland J H等于70年代发展了遗传算法（Genetic Algorithm，简记AG），它是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。此外，还对多种算法的交叉结合改进研究而得出新的算法，例如将节约法，禁忌搜索算法与遗传算法相结合的二分邻域搜索算法等。
2.2国内的研究进展
我国对城市生活垃圾的收集与运输路线的优化研究起步较晚，在固体废物的环境管理系统中处于薄弱环节，缺乏科学的规划和研究，因此造成人力、物力、财力的大量损失及有用资源的严重浪费，为后续的垃圾处理增加困难。为解决这一问题，近年来，我国不少学者在借鉴国外研究结果的同时又根据我国的基本情况，对垃圾车辆的优化路线作了大量研究，理论和方法趋于成熟，优化方法经历了从单目标到多目标的优化模型，从简单的函数到不确定多目标数学模型的阶段，如图1所示。

图1城市生活垃圾收集与运输路线的研究发展阶段
最初由于垃圾产生量不大，对环境造成的影响不明显，城市生活垃圾的管理处于零散管理的状态，任其在环境中自然消散。随着人口的增多，城市的发展以及人们生活水平的提高，生活垃圾的产量越来越大，人们逐渐意识到若不对生活垃圾进行有效管理将会带来严重的环境和健康问题，于是开始对垃圾的管理模式进行科学的研究和试验，起步的研究方法是单目标优化方法。单目标优化模型重点考虑了经济投入，简单易行，但考虑问题具有片面性，适合中小城市的管理模式，而对于大城市则必须考虑到环境影响和社会效应，因而对于大城市的生活垃圾收运模式，单目标优化模式表现也很大的局限性。