蚁群算法在交通管理中的应用研究

董新捷，韩伟娟

(1.中国电子科技集团公司信息科学研究院，信息系统研究所，北京 100086；2.中国科学院自动化研究所，北京 100190)



工程与应用

蚁群算法在交通管理中的应用研究

董新捷1，韩伟娟2

(1.中国电子科技集团公司信息科学研究院，信息系统研究所，北京 100086；2.中国科学院自动化研究所，北京 100190)

近些年来，随着城市汽车数量的大幅增加，交通拥堵问题越来越严重，交通管理日益重要，但在交通拥挤问题、选择最优路径等方面仍然面临着很多亟待解决的问题。蚁群算法是一种解决最优路径的智能算法，基于蚁群算法提出了一种均衡路程长度和拥堵程度以解决交通问题的新方法，模拟实验结果表明，该方法具有良好的性能，在一定目标函数下，通过小幅增加车程分散汽车流，大幅度降低了拥堵程度。该法具有一定的现实意义。

交通管理；蚁群算法；路程；标准差；信息素；拥堵系数

0 引 言

交通问题一直是困扰城市特别是大城市发展的一个重要问题，在现有交通基础设施和机动车数量快速增长条件下,交通拥堵问题越来越严重。在错综复杂的城市路网中，如何使得行人车辆到达目的的路程距离和整体的交通拥堵程度之间取得一个最佳的平衡,是交通管理的一个重要研究方向，本文将这个问题进行探讨。

从自然界的蚂蚁在觅食时的行为中得到启发，意大利科学家Dorigo等人于1991年提出了一种模拟蚂蚁来寻找最优路径的算法即人工蚁群算法。蚁群算法不仅具有分布式计算的特征，而且能做到信息的正反馈和启发式的搜索，不仅适用于离散系统的优化，也适用连续问题的优化。近些年来，蚁群算法被用于交通管理问题，进行路网的实时监测处理。原有的以蚁群算法进行交通管理的论文大多集中于挥发系数和比例系数对结果的影响，本文将拥堵系数引入信息素更新参数因子，实现对路程长度和拥堵程度的平衡。

1 算法策略

1.1 目标函数

在交通问题中，一般有两个重要指标，一个路程，一个是花费的时间，如公式(1)、(2)、(3)所示，P代表总体目标函数值，σ代表平均路程距离，φ代表交通拥堵程度标准差，α和β为两者在整体目标中的调整系数，根据实际需要设置，代表两者的重要程度。在实验中随机产生一批蚂蚁，从某个节点出发，计算每个蚂蚁到目的节点的平均路程，n为找到有效路径的蚂蚁数，Ai表示每一只蚂蚁从起点到终点的路程长度，Lij为某一时刻一条路径上的蚂蚁数量，而L代表同一时刻所有路径上的平均蚂蚁数量，对于不连通的路径，取Lij等于L，k代表连通的有效路径数量。

P=α*σ+β*φ

(1)

(2)

(3)

实验步骤如下：

Step1: 根据实际需要确定α和β；

Step2: 产生一批蚂蚁，每只蚂蚁根据信息素进行路径选择；

Step3: 进行一次迭代，计算蚂蚁数标准差、平均路程长度以及目标函数值等，如果满足一定终止条件，终止，否则进入Step4；

Step4: 根据一定策略更新信息素；

Step5: 转到Step2。

终止条件包括找到目标的蚂蚁数达到一定比例、搜素目标的时间耗尽、蚂蚁总随机次数达到一定数值仍未找到目标则丢弃等。蚁群算法流程图如图1所示，每次迭代后根据每只蚂蚁的路径长度重新计算信息素，然后进行下一次迭代。

图1 蚁群算法流程图

1.2 信息素更新策略

在一般的蚁群算法中，最优路径和非最优路径有着不同的信息素更新策略，在下一轮蚂蚁的路径选择中发挥着选择概率大小的不同作用，同时信息素以一定的系数挥发。在这里挥发系数以参数ρ表示，λ为最优路径信息素增加量，本实验中采取某一定值，非最优路径乘以大小为μ的比例系数。Ιnfo-1表示迭代前某条路径上信息素量,Ιnfoi表示迭代后更新的该路径信息素量。最优路径信息素迭代如公式(4)所示，非最优路径信息素迭代公式(5)所示。

Infoi=Infoi-1*(1-ρ)+λ

(4)

Infoi=Infoi-1*(1-ρ)+λ*μ

(5)

本实验将改进信息素更新策略，每一次迭代后，在根据路程长度更新信息素后引入拥堵系数，即实时计算此次迭代中每一条路径上平均经过的蚂蚁数，对于大于平均数的路径计算其差值，如果差值大于1，以信息素除以这个差值缩小信息素值，以减少其被后来的蚂蚁选择的概率，对于小于蚂蚁平均数的路径，得以相对增大信息素量从而增大其被选择的概率。Lij为某一时刻一条路径上的蚂蚁数量，而L代表同一时刻所有路径上的平均蚂蚁数量，Infoij表示该路径的信息素量，γ为调整系数，信息素更新在经过公式(4)和公式(5)的处理后，对于大于蚂蚁数平均值的路径如公式(6)处理。

(6)

2 实验设计

本实验算例如图2所示，起始节点0，目的节点20。进行两组实验，第一次实验使用路程优先的蚁群算法，每次蚂蚁信息素根据路程长度进行更新，如公式(4)和公式(5)所示。第二次实验在公式(4)和(5)的基础上，引入拥堵系数更新信息素，如公式(6)所示。

图2 本次实验节点和距离示意图

实验平台intel i7-4790处理器，主频3.6 GHz，内存16 GB，程序编译工具VS2010，仿真工具Matlab R2012a。

3 实验结果

第一次实验采取路程长短为导向的蚁群算法，即每次迭代中信息素量以路程长短为标准更新，基于公式(4)和公式(5)。每次实验采用100只蚂蚁，仅将到达目的的蚂蚁纳入计算范围，计算其平均路程长度和路程标准差，将标准差除以到达目的地的蚂蚁数量，ρ取0.1，μ取0.01，α取1，β取150，进行100次迭代，最后10次获取的结果如表1所示，保留两位有效数字。从实验结果可以看出，以路程为导向的蚁群算法能够在平均路程上取得较好的结果，但是各个道路经过的蚂蚁数量和平均经过的蚂蚁数量的标准差较大。

第二次实验在每次迭代后，计算每条路径上的蚂蚁数，引入拥堵系数。每条路径上经过的蚂蚁数表明这条路径较为拥挤，反之则较为顺畅，那么在根据公式(4)、(5)计算信息素后，在根据公式(6)进一步更新信息素，将导致信息素在拥挤程度较大的路径上减少，将缩小后来的蚂蚁对这条道路的选择概率，在顺畅的道路上信息素相对增大，增加被后来的蚂蚁选择的概率。经过调整进行实验，同样进行100次迭代后，最后10次的目标函数值如表2所示，保留两位有效数字。从实验结果可以看出，蚂蚁到达目的地所经过的平均路程明显增加，但所有路径上的蚂蚁数的平均标准差显著降低。ρ取0.1，μ取0.01，α取1，β取150，γ取1。

表2 第二次实验函数值

两次实验的路程对比如图3所示，蓝色虚线表示第一次实验蚂蚁平均路程长度，每只蚂蚁从起点到终点路程长度迅速收敛，稳定在10以下。红色实线表示第二次实验路程长度，可以看出，引入拥堵系数后每只蚂蚁所经过的路程长度变化较大，收敛不明显，且明显大于第一次实验中蚂蚁的路程。

图3 两次实验路程对比图

两次实验的时间对比如图4所示，蓝色虚线表示第一次实验每次迭代所花费的时间，每次迭代花费时间迅速下降，稳定在50毫秒左右。红色实线表示引入拥堵系数后每次迭代花费时间，大致在200毫秒到350毫秒之间浮动。

图4 两次实验时间对比图

在每次迭代后，首先计算每条路径上经过的平均蚂蚁数，然后计算每条路径的蚂蚁数和平均数之间的标准差，第一次实验如图5的蓝色虚线所示，第二次实验如图5的红色实线所示。可以明显看出，前者的标准差明显大于后者的标准差，表明没有引入拥堵系数时每条路径的蚂蚁数更偏离平均数，每条路上蚂蚁数分布更不均。而引入拥堵系数后，有效缩小了标准差，表明降低了拥堵程度，分散了蚂蚁流量，达到路程和蚂蚁数的均衡。

图5 两次实验标准差对比图

4 结 语

本文首先讨论了交通管理系统中路程和拥堵目标函数方程，然后用路程优先的蚁群算法和引入拥堵系数的蚁群算法进行两次实验。实验表明，引入拥堵系数后，蚂蚁的路程变长，而标准差变小，路程和标准差存在一定的替代关系，每个区域可根据实际情况设置路程和拥堵的权重系数，实现两者之间的平衡。

[1] 黄贵玲,高西全等. 基于蚁群算法的最短路径问题的研究和应用[J], 计算机工程与应用,2007,43(13):233-235.

[2] 宋锦娟，白艳萍. 基于改进蚁群算法的最短路径问题研究及应用[J], 数学的实践与认识,2013,43(3):156-164.

[3] 程世娟,卢伟等.基于蚁群算法的最短路径搜索方法研究[J].科学技术与工程,2007,7(21):1671-1819.

[4] 李士勇等著.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社,2004:53-77.

[5] 郑宇军,石海鹤,陈胜勇著.算法设计[M].北京：人民邮电出版社,2012:70-150.

[6] 段海滨著,蚁群算法原理及其应用[M],北京：科学出版社,2005:46-222.

[7] 刘经宇,方彦军.蚁群算法在城市交通路径选择中的应用[J].西南交通大学学报,2009,44(6):912-917.

[8] 闻育,吴铁军.基于蚁群算法的城域交通控制实时滚动优化[J].控制与决策,2004,19(9):1057-1063.

[9] 杨士勇,扬丹.基于改进蚁群算法的巡航导弹航迹规划[J],宇航学报,2007,28(4):903-907.

[10]税薇,葛艳,韩玉等.基于混合蚁群算法的无人机航路规划[J].系统仿真学报,2011,23(3):574-577.

[11]胡中华,赵敏,姚敏.引入导引因子蚁群算法的无人机二维航迹规划[J].中国机械工程,2011,22(3):322-325.

[12]王绪芝,姚敏,赵敏等.基于蚊群算法的无人机航迹规划及其动态仿真[J].指挥控制与仿真,2012,34(1):29-32.

[13]罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7):130-134.

[14]余剑峰,李原,于海山.基于自适应蚁群算法的协同制造项目资源优化配[J].计算机集成制造系统,2008,14(3):576-580.

[15]刘森琪,段海滨,余亚翔.基于Voronoi图和蚁群优化算法的无人作战飞机航路规划[J].系统仿真学报,2008,20(21):5936-5939.

[16]夏媛媛,马立云,王晓原.基于混沌蚁群算法的动态用户最优配流方法[J].山东理工大学学报(自然科学版),2011,25(3):17-21.

[17]闻育,吴铁军.基于蚁群算法的城域交通控制实时滚动优化[J].控制与决策,2004,19(9):1057-1063.

[18]刘经宇,方彦军.蚁群算法在城市交通路径选择中的应用[J].西南交通大学学报,2009,44(6):912-917.

[19]谷远利,李善梅,邵春福.基于蚁群算法的交通控制与诱导协同研究[J].系统仿真学报,2008,20(10):2754-2761.

董新捷(1985—)，河南人，工程师，主要研究方向为智能算法、图像处理等；

E-mail：dong3841919@163.com

韩伟娟(1986—)，河南人，工程师，主要研究方向为无线传感网络等。

Application Research of Ant Colony Algorithm in Traffic Management

Dong Xin-jie1, Han Wei-juan2

(1.Information Science Academy of CETC, Institute of Information System, Beijing 100086, China; 2.Institute of automation, Chinese Academy of Science,Beijing 100190, China)

City traffic congestion is becoming more and more serious with the increasing cars in recent years. Traffic management takes a very important part, but which still faces the difficulties such as traffic congestion and choice of the best path. Ant colony algorithm is an intelligent algorithm to solve the optimal path problem, and a new method is proposed based on ant colony algorithm to solve the traffic problem in a balanced path length and congestion degree. Simulation experiment shows that the method has good performance. Under a certain objective function, the method greatly reduces the degree of congestion and disperses traffic flow through a little increase in car distance. The method has certain practical significance.

traffic management; ant colony algorithm; distance; standard deviation; pheromone; congestion ratio

10.3969/j.issn.1673-5692.2016.06.019

2016-06-01

2016-09-02

：A

1673-5692(2016)06-663-04