改进蚁群算法求解带时间窗的应急物流开环车辆路径问题

摘要：

为解决受灾区域的物资运输问题,研究应急物流背景下带时间窗的开环车辆路径问题.将灾后道路通行性能差异及物资运输优先级考虑入约束范围,在确保应急物资运输可靠性的基础上,提出基于物流响应能力最大化的车辆路径模型.同时,考虑到传统优化算法收敛性差、易陷入局部最优的缺点,提出一种改进的蚁群算法以突破已有的算法瓶颈.该算法混合了人工鱼群算法与蚁群算法,将拥挤度因子引入蚁群算法以指导蚁群的聚集,从而提高蚁群算法求解的质量.通过一个基础算例对所提出模型与算法进行验证,得到最优解优化曲线并求解最优解,采用1组CMT与GWKC标准算例对提出的改进蚁群算法的性能进行评估计算试验.分别采用模拟退火算法、变邻域搜索算法及邻域搜索算法对标准算例进行求解.研究结果表明:提出的改进蚁群算法在求解收敛性与精确性上有显著优势,提出的算法在迭代60次后得到最优解,收敛速度比蚁群算法提前了68个迭代循环,最优解优化接近7.8％;在相同试验环境下,实例数据的规模与算法所求得最优解的差值无关,即算例规模并不影响算法求解的精确度;提出的改进蚁群算法在可接受时间范围内,通过适当延长邻域搜索运算时间可显著提升求解精度,在各组试验结果中相比于其他算法均求得了最优的结果,在CMT2中改进蚁群算法求得的最优解比已知上界优化了超过40％.

关键词：交通工程、应急物流、开环车辆路径问题、可靠性、蚁群算法、鱼群算法

所属期刊栏目：37

分类号：U491(交通工程与公路运输技术管理)

资助基金：国家自然科学基金项目61503043;中央高校基本科研业务费专项资金项目310822151030;陕西省自然科学基础研究计划项目2015JQ6214,2015JO7272

在线出版日期：2018-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：105-112