改进多目标蚁群算法在动态路径优化中的应用

为对城市动态车辆路径进行优化,设计一种具有贪婪转移准则的改进多目标蚁群算法。对蚂蚁执行多目标迭代局部搜索,在多个邻域上优化解或产生新的帕累托解。使用SUMO和NS2仿真软件,并用TraNS软件进行交互,对西安市区500组不同出发点和终点数据进行测试。结果表明,与两种传统优化算法相比,计算复杂度略有增加,但求解旅行时间明显缩短(平均少10%左右);与三种最新优化算法对比,在不同迭代次数和不同车辆数量条件下,虽然收敛速度不全都最快,但求解旅行时间均为最短(平均少5%左右)。该算法能更好满足行车时间硬要求,规避交通拥堵,能较好应用于动态车辆路径优化问题。

APPLICATION OF IMPROVED MUTIL-OBJECTIVE ANT COLONY ALGORITHM IN DYNAMIC PATH OPTIMIZATION

In order to optimize the dynamic path of urban vehicles,we designed an improved multi-objective ant colony algorithm with greedy transfer criterion.Multi-objective iterative local search was performed on ants to optimize solutions or generate new Pareto solutions in multiple neighborhoods.SUMO and NS2 simulation software were used,and TraNS software was adopted to interact.We tested the data of 500 groups with different starting points and endpoints in Xi’an city.The results show that the computational complexity of the algorithm proposed is slightly increased compared with the two traditional optimization algorithms,but the travel time is obviously shorter(about 10%less on average).Compared with the three latest optimization algorithms,under the conditions of different iterations and different number of vehicles,the convergence speed is not the fastest,but the travel time is the shortest(about 5%less on average).The algorithm can better meet the requirements of travelling time and avoid traffic congestion,which can be better applied to the dynamic vehicle routing optimization problem.