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