聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽 首页聽|聽简介聽|聽编委会聽|聽征稿简则聽|聽英文刊聽|聽稿件流程聽|聽致读者聽|聽下载区聽|聽常见问题说明
时间依赖型车辆路径问题的一种改进蚁群算法
Improved ant colony optimization algorithm for time-dependent vehicle routing problem
摘要点击聽67聽聽全文点击聽39聽聽投稿时间:2009/11/7聽聽最后修改时间:2010/3/15
查看全文聽聽查看/发表评论聽聽下载PDF阅读器
DOI编号聽聽
聽聽2010,27(11):1557-1563
中文关键词聽聽时间依赖型车辆路径规划问题聽聽蚁群算法聽聽最邻近算法
英文关键词聽聽time-dependent vehicle routing problem聽聽ant colony optimization algorithm聽聽nearest neighbor algorithm
基金项目聽聽
学科分类代码聽聽580.70;120.60
作者单位E-mail
段征宇同济大学 交通运输工程学院d_zy@163.com
杨东援同济大学 交通运输工程学院
王上同济大学 交通运输工程学院
中文摘要
聽聽聽聽聽聽时间依赖型车辆路径规划问题(TDVRP), 是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化. 传统车辆路径问题(VRP)已被证明是NP-hard问题, 因此, 考虑交通状况时变特征的TDVRP问题求解更为困难. 本文设计了一种TDVRP问题的改进蚁群算法, 采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解, 通过局部搜索操作提高可行解的质量, 采用最大--最小蚂蚁系统信息素更新策略. 测试结果表明, 与最邻近算法和遗传算法相比, 改进蚁群算法具有更高的效率, 能够得到更优的结果; 对于大规模TDVRP问题, 改进蚁群算法也表现出良好的性能, 即使客户节点数量达到1000, 算法的优化时间依然在可接受的范围内.
英文摘要
聽聽聽聽聽聽Time-dependent vehicle routing problem (TDVRP) is concerned with vehicle routing optimization in road networks with fluctuant link travel time. The traditional vehicle routing problem (VRP) has been proven to be an NPhard problem, so it is difficult to solve TDVRP in considering traffic conditions. We design an improved ant colony optimization algorithm (ACO) for TDVRP. It uses nearest neighbor algorithm based on minimum cost(NNC algorithm) to generate the initial solution, improves feasible solution by local search operations, and updates pheromone with max/min ant system strategy. Test results show that compared with the nearest neighbor algorithm and genetic algorithm, the improved ACO algorithm is more efficient and able to get better solutions. Furthermore, this improved ACO algorithm show good performance in large scale TDVRP instances, even if the customer number of TDVRP reaches 1000, the computation time is still in an acceptable range.
 
  聽聽聽聽聽聽聽聽聽 您是第725083位访问者  

主办单位:华南理工大学 中国科学院数学与系统科学研究院聽聽聽聽聽 单位地址:广州市天河区五山路381号

服务热线:020-87111464聽聽 传真:020-87111464聽聽 邮编:510640 聽聽Email: aukzllyy@scut.edu.cn
 

聽聽聽聽本系统由北京勤云科技发展有限公司设计聽聽京ICP备09084417号
美女图片