改进蚁群算法在交通分配模型中的应用

常玉林，汪小渟，张 鹏

(1.江苏大学 汽车与交通工程学院，江苏 镇江 212013； 2.东南大学 城市智能交通江苏省重点实验室，江苏 南京 211189)

改进蚁群算法在交通分配模型中的应用

常玉林1,2，汪小渟1，张 鹏1

(1.江苏大学 汽车与交通工程学院，江苏 镇江 212013； 2.东南大学 城市智能交通江苏省重点实验室，江苏 南京 211189)

为了更加准确快速地搜索到最优路径，通过分析车流经过信控交叉口的到达和驶离状况，提出一种考虑交叉口信控延误的改进蚁群算法模型.首先，用交叉口的信控延误和路段行走时间对基本蚁群算法的信息素更新方程进行改进，建立全新的信息素更新模型;其次，通过应用改进后蚁群算法对路网各路段的车流量进行分批分配，设计考虑交叉口延误的路段增量分配流程;最后，基于java程序语言，对路网的流量分配进行仿真，并且和基本蚁群算法对路网运行质量进行对比分析.结果表明，改进后的蚁群算法能够降低路网中路段和交叉口使用率，具有良好的寻优性，并能有效均衡路网流量和缓解交叉口的通行压力.

交通分配；交叉口延误；蚁群算法；最优路径

0 引言

交通分配作为四阶段法最后一步以及最重要一步，通过精确计算把各个小区发生与吸引量合理地分配到实际交通路网.蚁群算法的设计理念来源于自然界蚁群里蚂蚁个体的寻食行为，是意大利学者Dorigo首先提出并且不断改进而得到的新型优化算法[1].与传统的数学规划原理相比，该优化算法具有很好的稳定性，拥有分布计算、反馈信息以及启发式搜索的特性，并且能够动态响应和反馈路径选择过程中的外界影响.传统蚁群算法的原理是通过遗留在路径上的信息素浓度选择最优路径，表现形式是路径长度越短，遗留的浓度越大.以往的改进蚁群算法统一表现在信息素更新形式，重要的突破是以行走时间代替距离要素作为信息素更新要素的改进模型[2-4].文献[5]提出改进的蚁群系统算法求解可装卸货物的车辆路径问题，该算法通过使用多路径搜索原则，搜索不同路径上的客户，增大了搜索范围.文献[6]从路径转移规则和局部搜索的改进方程出发，提出一种能加快最优解收敛速度的改进蚁群算法，对带容量约束的弧路径问题进行求解.文献[7]通过使用AS模型对30个节点的TSP问题进行研究，总结了蚁群算法最优参数的设置方法.宋方[8]通过在状态转移规则中加入扰动因子，改进全局更新规则，并将信息素更新算子引入基本蚁群算法，提出一种改进蚁群算法求解城市道路权值仿真模型.

连续车流途经交叉口时的信控延误势必会影响信息素的更新，最终影响交通分配的结果.因此，笔者将车辆的信控延误加入信息素更新要素中，通过分析车流经过信号配时交叉口的到达和驶离状况，综合考虑交叉口延误时间和路段行程时间,提出了改进的、更加符合实际情况的、考虑交叉口延误的蚁群算法模型.但是由于交叉口延误的影响因素非常多，所以笔者在考虑交叉口延误时也做了一定的假设与妥协.

1 蚁群算法

1.1 蚁群算法的基本原理

蚁群算法根据的原理是：蚂蚁在寻找食物的过程当中，会相互协同工作，这中间起着关键作用的是蚂蚁自身分泌的一种激素——信息素[8-9].蚂蚁在寻找路径时，总是倾向于选择信息素浓度大的路径作为下一个行进方向，即信息素遗留越多、浓度越大的路径越容易被选中，被选中的路径又会增加其浓度，这就是所谓的正反馈机制.这种机制的一个好处就是蚂蚁对整个路径上的全部信息素的反馈要求降低，仅仅通过局部信息素的信息反馈就可以找出最短路径.整个蚁群的行为也会随外界环境的改变而改变，当有阻碍物出现在蚂蚁的行动路径上时，蚂蚁会快速地做出改变，并且重新找到另一条在当前环境下的最优路径.

1.2 基本模型

以经典TSP(旅行商问题)作为例子，来阐述蚁群算法的相关模型.旅行商问题的实质是：已知所有目标地点的总数为n，并且已知任意两个目标城市之间的距离[10-11].旅行商以任选一点作为起点出发，要求确定一条最短路径，并且这条最短路径只经过每个旅行地一次.

在最初t=0时刻，各条路的信息素浓度都为常数，设为τij(t0)=C，式中τij(t0)表示t0时刻路段(i，j)上的信息素浓度，C为常数.

在进行路径选择时，m只蚂蚁根据每条路径上留有的信息素浓度和自己的判断决定转移方向，在t时刻蚂蚁的转移概率

(1)

式中：ηij为能见度因数，以两点之间的距离作为变量，距离越大ηij越小；α为路径上的信息素总量对蚂蚁行为的影响程度；β为路径长度对蚂蚁行为的影响程度；allowedk={C-tabuk}，表示除掉禁忌列表剩下的城市，即可以被选择的城市集合.人工蚂蚁具有真实蚂蚁不具备的特点，在进行选择时会增加一个禁忌列表.所有在本次循环中被选择过的城市都会被记录到禁忌列表里，避免被反复选择，禁忌列表里的城市会在循环结束后被释放，在下一次循环开始时，蚂蚁又能够从所有城市中进行选择.

经过n个时刻，当m只蚂蚁遍历完所有城市后，各条路径上的信息素根据下式进行调整：

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1).

(2)

(3)

式中：Q为每只蚂蚁在这次循环中释放的信息素量，是常数；Lk表示蚂蚁k在此次循环中经过的所有路段加起来组成的路径长度.

2 改进蚁群算法

笔者在传统蚁群算法模型的基础上，再加上交叉口延误，建立考虑交叉口延误的蚁群算法模型.引入交叉口延误的蚁群算法模型信息素更新方程为：

(5)

式中：Q为信息素常数；T为路段总花费时间，是路段行走时间和车辆在交叉口的信控延误之和，即T=tij(qij)+dij(qij).

信息素更新改进模型如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1).

(6)

(7)

其中信息素更新方程为：

(8)

(9)

dij=dij1+dij2；

(10)

(11)

(12)

式中：dij(qij)为城市i和j之间最短路径上交叉口处在流量qij时的延误时间；k=0.5；I=1.

3 基于改进的蚁群算法增量分配模型

(1)初始化.蚂蚁个数m;最大循环次数NC;循环次数n=1;τij=C(C为边(i，j)上的信息素量初始值)，Q;Δτij=0、α、β等.取出起点g和终点h以及相应的需求分配交通量.

(2)将总共m(m=n×m0)只人工蚂蚁放置在起点g上，采用分批分配方法以m0(m0=PA)只蚂蚁为一批，分配批次n=1.

(3)分批分配.让第一批人工蚂蚁随机选择路径，并保证每只蚂蚁完成一次循环选择，计算各路段蚂蚁数并更新总行驶时间tij和路段上的信息素轨迹τij.

(5)计算目标函数值，找出各OD点对之间的最优解，计算各路段qij(t)和tij(t).

(6)n=n+1，若m只人工蚂蚁全部循环一次结束，转至(7)，否则转至(4).

(7)满足条件，即n=NC，结果无退化行为，即在本次循环中得到的最优解等于N个循环之前的解，则循环结束并输出结果，否则转至(2).

4 案例分析

4.1 初始计算

图1 选用道路网络结构图

基于下述路网的OD分配量，对其进行数据筛选获得符合实际路网的交通OD表，并借助互联网地图及AutoCAD同比例缩放功能，以交叉口7为坐标原点，求得各个交叉口的相对坐标点.根据各交叉口间距、车辆行驶速度、初始行驶时间、每个交叉口的信号周期、信号绿信比、交叉口通行能力，计算得到各转向车道上车辆的延误时间和交叉口的延误时间.

4.2 程序仿真

采用java语言，在基本蚁群算法程序基础上，编入交叉口延误数据，并用MyEclips软件实现改进蚁群算法的功能.

对基本蚁群算法选择概率函数的各参数进行初始值设置：α=2，β=4，ρ=0.5，最大迭代次数200次，信息素Q=100，蚂蚁数30.设置信息素更新方程的路段行驶阻抗函数参数：α=1，β=4.在程序内输入交叉口坐标数据表、OD矩阵表、初始行驶时间表、延误对比表，运行程序得到各路段分配结果，如图2所示.

图2 蚁群算法改进前后的流量对比图

试验结果表明，采用改进蚁群算法分配路段交通流量，各路段的平均流量为411.4 pcu/h，方差为2 190.7；采用基本蚁群算法对各路段流量进行分配，各路段平均流量为485.2 pcu/h，方差达到3 096.4.在改进蚁群算法下，车次总延误时间为642 446.17 s，基本蚁群算法车次总延误时间为772 387.09 s.比较可得，改进算法比基本算法车均延误减少55.649 s.

基本蚁群算法并没有考虑交叉口的延误，实际情况中交叉口延误影响较大，所以笔者用基本蚁群算法，再运用公式计算对应流量下的延误时间，以两者时间之和作为基本蚁群算法的车辆行驶时间.通过对上万辆车的实测数据筛选结果，得出车辆实际行驶的时间,如表1所示.

没考虑交叉口延误的影响时，路段行驶时间是主要因素，而考虑交叉口延误之后，交叉口延误就成为了影响车辆行驶时间的主要因素.总车次上，改进蚁群算法同样小于基本蚁群算法.而总车次反映的是车均经过交叉口数的大小，这也反映了改进蚁群算法在路径寻优时更加具有方向性.本次的实例应用，主要的是缓解常武路路段上的拥堵情况，如表2所示.

表1 车均行驶时间对比表

表2 常武路交叉口使用率对比表

通过对改进蚁群模型、基本蚁群模型和实测数据的分析可知，虽然基本蚁群算法也能够缓解交叉口通行压力，使交叉口使用率从109.44%下降到97.90%，但是改进蚁群模型在缓解交叉口使用率，从而缓解交叉口拥堵方面能够比基本蚁群算法效果更好，在基本蚁群算法的基础上，再下降8.11个百分点至89.79%.

5 结论

在基本蚁群算法的基础上，通过将交叉口延误时间和行驶时间之和引入信息素更新方程中，即用车辆在交叉口的延误时间和在路段的行驶时间之和替代路段长度对信息素进行更新.试验表明，改进后的蚁群算法相比基本蚁群算法在路径选择时更具方向性，并且能够更好地做到均衡分配，能够将车流尽可能地分配到整个路网上，使得整体流量限制在了一个比较小的区间内，减轻OD点量大的路段上的负担.

[1] MULLEN R J, MONEKOSSO D, BARMAN S, et al. A review of ant algorithms[J]. Expert system with applications,2009,36(6):9608-9617.

[2] ATTIRATANASUNTHRON N, FAKCHAROENPHOL J. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs[J]. Information processing letters,2008,105(3):88-92.

[3] 吴斌,史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333.

[4] 林泉,许伦辉,唐德华. 改进蚁群算法在动态交通分配中的应用研究[J].科学技术与工程,2009,9(18):5410-5414.

[5] GAJPAL Y, ABAD P L. An ant colony system(ACS) for vehicle routing problem with simultaneous delivery and pickup[J]. Computers and operations research, 2009,36(12): 3215～3223.

[6] LUIS S, JOAO C R, JOHN R C. An improved ant colony optimization based algorithm for the capacitated arc routing problem[J]. Transportation research part B: methodological, 2010,44(2):246～266.

[7] 詹士昌,徐婕,吴俊. 蚁群算法中有关算法参数的最选择[J]. 科技通报,2003,19(5):381～386.

[8] 宋方,汪镭. 改进蚁群算法在智能交通中的应用[J]. 数学的实践与认识, 2013,43(3):66-72.

[9] 段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社,2007.

[10]温惠英,徐建闽. 基于改进型蚁群算法的车辆导航路径规划研究[J]. 公路交通科技,2009,26(1):125-129.

[11]SOLNON C. Combining two pheromone structures for solving the car sequencing problem with ant colony optimization[J]. European journal of operational research, 2008,191(3):1043-1055.

[12]DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE transaction on systems man and cybernetics part B,1996, 26(1):29-41.

[13]HUTCHINSON T P. Delay at a fixed time traffic signal-II:numerical comparisons of some theoretical Expressions[J]. Transportation science,1972,6(3):286-305.

[14]吴兵,李晔.交通管理与控制[M].北京:人民交通出版社, 2013.

[15]MISRA S, OOMMEN B J. An efficient dynamic algorithm for maintaining all-pairs shortest paths in stochastic networks[J]. IEEE transactions on computers,2006,55(6): 686-702.

[16]靳凯文, 李春葆, 秦前清. 基于蚁群算法的最短路径搜索方法研究[J]. 公路交通科技, 2006,23(3):128-130,134.

[17]唐亮,靖可,何杰. 网络化制造模式下基于改进蚁群算法的供应链调度优化研究[J]. 系统工程理论与实践, 2014,34(5):1267-1275.

Modified Ant Colony Algorithm and Its Application on Traffic Assignment Model

CHANG Yulin1,2, WANG Xiaoting1, ZHANG Peng1

(1.School of Automotive and Traffic Engineering, Jiangsu University, Zhenjiang 212013, China;2.Jiangsu Key Laboratory of Urban ITS, Southeast University, Nanjing 211189, China)

In order to more quickly and accurately search for the optimal path, an improved ant colony algorithm was established through analyzing the process of car arriving and departure in the signalized intersection. First of all, a new pheromone update model was put forward by improving properly the pheromone update function in traditional ant colony algorithm, which used signal control delay in the intersection and the travel time of vehicles in the road section as pheromone update operators. Then, road section incremental allocation process considering intersection delays, which was through partial distributing traffic flow in the network, was designed based on improved ant colony algorithm.Finally, flow distribution in the road network was simulated based on computer language, and the network running quality was compared with traditional ant colony algorithm. The experimental results showed that the improved ant colony algorithm, which could reduce road section and intersection using rate, was of good optimization ability, and could effectively balance the network traffic and alleviate the pressure of intersections.

traffic assignment; intersection delay; ant algorithm; optimal path

2016-05-01；

2016-09-02

江苏省高校自然科学基金资助项目(13KJB580003)；江苏省城市智能交通重点实验室开放研究经费资助项目(JTKF2014004)；江苏大学高级专业人才科研启动基金资助项目(12JDG056)

常玉林(1963— )，男，江苏大学教授，博士，主要从事交通运输规划与系统优化技术研究，E-mail:ylchang@ujs.edu.cn.

1671-6833(2017)02-0041-04

U491.1+23

A

10.13705/j.issn.1671-6833.2017.02.010