时间依赖型车辆路径问题的一种改进蚁群算法
段征宇
杨东援
王上
1.同济大学交通运输工程学院,上海,2000922.同济大学交通运输工程学院,上海,2000923.同济大学交通运输工程学院,上海,200092
摘要：时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大一最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVIRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.
关键词：时间依赖型车辆路径规划问题蚁群算法最邻近算法
分类号：U491(交通工程与公路运输技术管理)
资助基金：国家自然科学基金(50738004)国家高技术研究发展计划（863计划）(863;2007AA11Z245)
论文发表日期：2010-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：7( 1557-1563 )
英文信息