基于改进型蚁群算法的餐厨垃圾收运路线优化研究

摘要

随着城市化进程的加快及人民生活水平的提高，餐厨垃圾的产生量越来越大。如今对餐厨垃圾的研究基本都停留在末端治理和源头控制，对餐厨垃圾的收运路线关注很少，带来了不良的经济效益、社会效益和环境效益。而对于收运路线的研究:也只是单一地研究收运路线，结合实际收运系统研究的较少;只是研究单一车型的数学模型，多车型研究的较少;只是单一地利用蚁群算法或遗传算法求解，对于蚁群算法自身的改进、与遗传算法融合算法研究的较少。本文以垃圾收运路线问题的三个研究不足为突破口，探讨基于改进型蚁群算法重庆餐厨垃圾收运路线优化研究。
　　通过对餐厨垃圾收运系统的各因子进行了定性和定量地分析，结合重庆市餐厨垃圾收运的现状和现场的调查，从而分析了重庆市餐厨垃圾收运系统;在此基础上，提出了重庆餐厨垃圾收运路线优化问题。
　　重庆餐厨垃圾收运路线是餐厨垃圾车在车库、收集区域、转运站（或处理场）间的行驶，形成了一个往返的环游。将环游分解为三种类型的行程:即从车库到收集区域到转运站（或处理场）的最初行程;从转运站到收集区域（或处理场）到转运站的中间行程;从转运站（或处理场）到车库的最终行程，中间行程可为一次或多次。本文采用优化理论中的图论和网络流的知识对实际问题建立网络权重的单一车型和多车型模型，并对此模型的目标函数和约束条件进行了分析研究，再用改进型蚁群算法对实际问题的模型进行求解。
　　对于求解垃圾收运路线问题的算法研究，单一的蚁群算法和遗传算法在求解时间和精确度方面不能兼得，所以选用蚁群算法的改进型算法，有两方面改进:自身的改进和与遗传算法融合的改进，自身的改进分为参数选取的优化和蚁群系统（Ant Colony System，ACS）。运用了两个经典的车辆路径问题(Vehicle RoutingProblem，VRP)实例，第一个实例说明了蚁群算法中参数选取的优化;第二个实例说明了动态蚂蚁遗传混合算法（Dynamic Ant Algorithm-Genetic Algorithm，DAAGA）在解决VRP时，比蚂蚁算法(Ant Algorithm，AA)、遗传算法(GeneticAlgorithm，GA)、蚁群系统(Ant Colony System，ACS)和蚁群遗传算法(AntColony System-Genetic Algorithm，ACSGA)的性能都好。
　　最后以重庆市主城区的江北区作为实例一，沙坪坝区作为实例二，在实际的餐厨垃圾收运系统的基础上，采用DAAGA对餐厨垃圾收运路线进行了优化，并且在研究的过程中运用了收集点合并、聚类分区和垃圾分配技术。对于实例一:江北区，案例一与案例二、案例三和案例四进行求解和对比，得出结论:在江北区的实例中DAAGA优化的一级转运收运模式的多车型的餐厨垃圾收运路线优于直接收运模式、单一车型和实际情况的三种餐厨垃圾收运路线;对于实例二:沙坪坝区，将最优的情况应用在沙坪坝区的餐厨垃圾收运线路，得到了理想的结果，说明了所建立的模型、所应用的算法在其他实例中也适用，证明了其具有可行性和普遍性。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究目的和意义

1．3 国内外相关研究现状

1．3．1 收运和转运路线的研究现状

1．3．2 VRP问题的研究现状

1．3．3 求解VRP问题算法的研究现状

1．4 研究内容、方法和技术路线

第二章 重庆市餐厨垃圾收运系统的概况

2．1 城市垃圾收运系统的属性

2．2 城市餐厨垃圾收运系统的因子分析及选择

2．2．1 餐厨垃圾收集方式、搬运和贮存

2．2．2 收集容器的分析与选择

2．2．3 运输机具的分析与选择

2．2．4 转运站的分析与选择

2．2．5 垃圾处理场的分析与选择

2．3 收运模式

2．3．1 餐厨垃圾收运模式概述

2．3．2 垃圾收运模式分类

2．3．3 重庆主城区的分区

2．3．4 重庆市主城区餐厨垃圾收运模式的选择

2．4 城市餐厨垃圾收运路线

2．4．1 实际路线设计

2．4．2 区域路线设计

2．4．3 设计收运路线的一般步骤

2．5 本章小结

第三章 城市餐厨垃圾收运路线的数学模型

3．1 餐厨垃圾收运路线问题

3．1．1 餐厨垃圾收运路线问题的提出

3．1．2 餐厨垃圾收运路线问题的界定

3．1．3 餐厨垃圾收运路线问题的分类

3．2 垃圾收运线路优化模型建立

3．2．1 图论与网络流

3．2．2 单一车型数学模型的建立

3．2．3 多车型数学模型的建立

3．3 垃圾收运路线模型分析

3．4 本章小结

第四章 求解垃圾收运路线优化模型的算法研究

4．1 求解垃圾收运路线模型的算法概述

4．2 蚁群算法(AA)

4．2．1 蚁群算法的概述

4．2．2 蚁群算法的数学模型及其运行步骤

4．2．3 基本蚁群算法的特点

4．3 蚁群算法自身的改进

4．3．1 参数选择的优化

4．3．2 蚁群系统(ACS)

4．4 蚁群算法的融合改进—动态蚁群遗传混合算法(DAAGA)

4．4．1 遗传算法的概述(GA)

4．4．2 动态蚁群遗传算法(DAAGA)

4．5 改进型蚁群算法的测试对比

4．6 本章小结

第五章 改进型蚁群算法求解餐厨垃圾收运路线的应用

5．1 重庆市餐厨垃圾调查研究

5．1．1 重庆市主城区概况

5．1．2 重庆市餐厨垃圾产量现状

5．1．3 重庆市餐厨垃圾收运现状

5．1．4 重庆市餐厨垃圾处理现状

5．2 实例的研究

5．2．1 问题的提出

5．2．2 实例一：江北区

5．2．3 实例二：沙坪坝区

5．3 本章小结

第六章 结论与展望

6．1 主要成果和结论

6．2 展望

致谢

参考文献

在学期间发表的论著及取得的科研成果