时变路网条件下车辆路径问题的自适应蚁群算法  

Adaptive ant colony optimization for vehicle routing problem in time varying networks environment

作　　者：蔡延光[1] 汤雅连[1] 蔡颢[2] 

机构地区：[1]广东工业大学自动化学院,广州510006 [2]奥尔堡大学健康科学与工程系

出　　处：《计算机应用研究》2015年第8期2309-2312,2346,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61074147;61074185);广东省自然科学基金资助项目(S2011010005059;8351009001000002);广东省教育部产学研结合项目(2012B091000171;2011B090400460);广东省科技计划资助项目(2012B050600028;2010B090301042)

摘　　要：考虑实际生活中道路路况影响运输成本及油耗率与运载量相关的因素、处理跨多时段的问题,建立时变路网条件下的车辆路径问题数学模型。通过聚类算法和节约算法构造初始解,提高求解速度;自适应地改变启发式因子和期望启发式因子,提高算法全局收敛能力;结合油耗率,将油耗率转换成信息素挥发因子,自适应更新信息素,保证其收敛速度;通过3-opt策略,提高算法的局部搜索能力。基于以上方法构造自适应蚁群算法,对八个客户规模的实例进行仿真表明,提出的算法在收敛速度和寻优结果两方面略优于自适应遗传算法和蚁群算法,并且因为考虑了不同运载量的油耗,为准确估计运输成本提供了方法。Considering road condition affect transport cost and fuel consumption rate was associated with carry load in real life, dealing with crossing multi-period problem, this paper established vehicle routing problem in time-varying networks environment mathematical model. At first, constructing initial solution through cluster algorithm and saving algorithm could improve search speed, changing information heuristic factor and pheromone expectation heuristic factor adaptively could improve global convergence ability. Secondly, combining the fuel consumption rate to update pheromone adaptively ensured the convergence speed. At last, it used 3-opt strategy to improve local search ability. Thus, it constructed adaptive ant colony optimization （ AACO）, using this algorithm to solve VRP for 8 clients. Experiments show that AACO is better than adaptive genetic algorithm （AGA） and ant colony optimization （ACO） in convergence speed and optimal results. Considering the different carry load of fuel consumption, it provides a more accurate for estimating transportation cost.

关 键 词：车辆路径问题 时变路网 蚁群优化 自适应 多时段 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]