详情

原文传递基于混合蚁群算法的船废收运路线优化研究

论文题名：	基于混合蚁群算法的船废收运路线优化研究
关键词：	船废收集;路线优化;混合蚁群算法;解决车辆路径问题
摘要：	近年来随着船舶水运事业快速发展在带来巨大的经济效益的同时，也带来了严重的河流水域污染问题。本文针对船废收集效率极低的现象，研究相关政策促使船废全部上岸，采用环卫车进行陆运收集至中转站(车辆路径问题)，最终采用水运由中转站运往老港等垃圾处理点。根据这一模式制定合理的船废收运路线，通过研究算法优化模型，降低船废收运路线成本，实现改善环境和降低经济成本的目的。　　本文将解决车辆路径问题( Vehicle Routing Problem, VRP)的前沿元启发算法的优缺点进行对比分析，最终选取在解决组合优化问题上有显著优势的蚁群算法，来优化环卫车辆收运船废垃圾的路线。　　通过调查内河船舶垃圾收运现状及参考国内外大量文献资料，并结合船废垃圾特点，建立不同约束条件下的三个收运模型：有　　容量限制的车辆路径问题，带中转的垃圾收集车辆路径问题，带时间窗的多车场多车型车辆路径问题。采用混合蚁群算法进行模型求解。具体工作如下：　　首先，采集船废收运系统中垃圾量与分布坐标，收集设施和中转设施等基础数据。通过船讯网对内河船废分布信息进行采集；根据13条免费收集航线垃圾收运信息，采用Excel进行处理预测各分布点的垃圾量。　　其次，对现有中转站和环卫车场车型等服务设施进行调研，建立相应的中转站设施优化模型，降低收运成本。根据行政区域和水网密度情况，选取不同的运输模式，如陆上中转运输模式、陆上直接运输模式或水陆集装运输模式。　　再次，对蚁群算法进行改进研究，将其应用在以上三个模型中，进行收运路线优化。主要从以下四个方面进行算法改进：　　(1)引入节约算子思想，平衡启发算子，从全局考虑，避免局部最优。　　(2)添加负反馈机制的局部信息素更新，扩大搜索范围；并采用正反馈机制的全局信息素更新方式，引导搜索方向。　　(3)为避免停滞，基于Ant-Q System和蚁群算法经典收敛曲线，动态调整参数设置，在搜索过程中动态调整状态转移概率，达到确定性和随机性选择平衡，使得收敛方向正确的同时，加快收敛速度。　　(4)结合轨迹式启发算法——变邻域搜索算法( Variable Neighborhood Search, VNS)，来扩大搜索范围，提高解的稳定性。　　为验证每一种改进算法的有效性，本文采用国际上公认的VRP问题库典型案例(solomon’s ins tanc es)进行仿真实验和分析。改进后的蚁群算法，在规模相对不大的CVRP问题中具有良好的优化效果和较强的鲁棒性。对大规模的问题，采用Kmeans算法先聚类，后转化为小规模问题，也取得了较好的效果。　　最后，本文根据上海市某区水域内垃圾收集点的相关数据，建立多车场多车型车辆路径模型，通过改进的蚁群算法进行模型求解，得出上海市某区的船废收运环卫车路线调度方案，实现经济效益和环境效益。
作者：	翟露露
专业：	控制科学与工程
导师：	王直杰
授予学位：	硕士
授予学位单位：	东华大学
学位年度：	2017
正文语种：	中文