交通应急调度系统的蚁群算法优化设计

刘长鹤 邵清亮 李明沂 曹云淏 余冬

摘 要：随着公路建设规模的不断扩大和交通量的不断增加，汽车碰撞、追尾等交通事故的发生频率也随之增加。因此，在发生各种事故后，运输部门应及时进行任务分配和应急物资运输路线规划。针对蚁群算法在传统调度系统中的不足，本文提出的系统通过适当改变信息素挥发因子，加快收敛到染色体最优解的速度，建立了蚁群自适应优化算法，利用优化算法求解规划模型。结果表明，该算法的收敛速度和优化结果均优于传统的蚁群算法。

关键词：智能交通系统;蚁群算法;信息素因子;应急管理

中图分类号：X928 文献标识码：A

0 引言

层出不穷的交通事件和不可抗力灾害是造成交通网络各种拥堵的关键原因，将对城市乃至全国的经济建设和服务效率造成巨大损失。因此，科学地运用蚁群算法对城市交通进行引导和分类，是有效减少交通事故、灾害、资源运输等事件的有效方法。

交通调度问题[1]（Traffic Scheduling Problem，TSP）是1959年由Dantzig和Ramser提出。TSP具有较高的实用性和广泛的应用。但是，TSP没有使用大规模的邻域搜索技术，对于多目标车辆计数调度，响应速度慢，调度周期长，容易受到一系列条件的限制。其蚁群算法与动态搜索算法无关，不具备将动态车辆调度问题转化为一系列静态车辆调度问题的能力，也不足以达到有效的收敛速度。本文提出的自适應蚁群优化算法动态调整调度路径中散发的信息素，适当增大随机选择的概率，进一步完善搜索解空间，克服了传统蚁群算法的缺点，加快了收敛速度。避免给国民经济建设和服务效率造成巨大损失。因此，科学地运用蚁群算法对城市交通进行引导和分类，是有效减少交通事故、灾害、资源运输等事件的有效方法。

1 传统蚁群算法

传统蚁群算法[2]是一种模拟自然界蚂蚁搜索路径的启发式算法。该算法不受限于特定的数学描述。该算法拥有全局优化、高并行性、强鲁棒性、短求解时间、便于计算机仿真等优点。它包含蚁群算法、最优排序蚁群算法、极大值蚁群算法、自适应蚁群算法等。

1.1 解空间[3]的构建及信息素的初始化和更新

，表示立体网络结构中的节点，表示紧急物资从出发点输送到终点的完整路径。

信息素为，表示蚂蚁位于网络节点[4]时，选择节点出发的第j条路线的期望程度。执行迭代前，各路径信息素初始值，其中为与节点相连的边的总数。设为信息素的挥发系数，0<<1，n为迭代次数，为本次迭代后的信息素增量，每次迭代后，各条路径上更新后的信息素更新为：

（1）

目标函数，作为蚁群算法的评价函数，测定蚂蚁构建出的解的质量，信息素增量，基于下式确定：

（2）

其他 （3）

1.2 选择策略

蚂蚁k从节点选择路径e（i，j）向节点转移的概率基于下式确定：

（4）

其他 （5）

其中，为蚂蚁k下一步允许选择的城市集合，为启发式信息，基于下式确定：

（6）

传统蚁群算法虽然在整体脉络上非常清晰，但是收敛速率仍具有较大的提升空间，我们应该做的是改变传统蚁群算法的信息素的更迭模式。

2 改进蚁群算法

在此，我们将改进上述传统的蚁群算法。蚂蚁k在运动过程中，其移动方向是由各路径的信息素分布情况决定的，其中是蚂蚁k下一步可选择的城市;是能见度因数，常取。反映了蚂蚁在运动过程中信息素的积累，反映了启发信息在选择路径中的相对重要程度，为信息启发式因子，为期望启发式因子。是信息素挥发因子，（0，1），（t）表示本次循环中信息素增量，表示第k只蚂蚁在这次循环中存在的信息素。Q表示信息素水平，收敛速度会受算法的影响，过高会使局部收敛，过低会影响收敛速度。表示在本次循环中路径的长度。

，蚂蚁k经过路径（i，j）;

=0，蚂蚁k不经过路径（i，j） （7）

2.1 构造状态转移规则

结合确定性进行选择，使用随机性的策略适当地增加随机选择概率。更优的、更全面的对解空间进行搜索，攻克了传统蚁群算法的缺点。基于方程（4）（5）确定蚂蚁k由i移动到j的状态转移概率。q是随机数[0，1]，是参数，[0，1]，一般在0.80到0.90中取值。蚂蚁将选择下一个结点前，根据上文，由式（8）来选最好的方向，否则按照式（7）来选一个方向，对求得的各个结点的转移概率进行叠加，并与生成的随机数进行比较，直到满足要求，蚂蚁才可移动到下一个结点。

搜索概率 （8）

2.2 信息素更新

（1）保持最佳的解决方案。每次循环后保持最好的解。

（2）自适应性变化。虽然它可以提高算法的全局搜索能力[5]，但也会降低算法的收敛速度，因此需要对其进行自适应的改变。的初始值，当该算法得到的最优值没有显著提高N周期，将如方程（9）所示。可以防止算法的收敛速度增加由于值太小而减少。

（9）

2.3 自适应蚁群优化算法求解步骤

（1）混沌搜索，生成初始种群，设计自适应蚁群算法的参数。

（2）构建状态转移规则。

（3）以蚂蚁最佳路径遍历所有增加信息素的点。

（4）更新信息素。

（5）满足条件后，达到最大迭代次数或多次生成相同解，以结束。否则，转到3。

3 多智能体调度

3.1 多智能体和跨区域调度的概念

（1）多智能体是由一系列具有分布性、自主性和协调性的相互作用的智能体组成的。内部智能体通过相互交流、帮助和竞赛来完成个别智能体无法完成的工作，由此可以做到将复杂问题完成简化分解。基于多智能体协作规则，得到适合系统的应急物资调度任务。

（2）跨区域综合交通应急调度是在突发事件发生时，通过不同区域、不同部门之间的相互协调，提高应急资源配置的一种救援策略。有效配置各区域资源，确保跨区域合作行动的快速响应，控制事件发展，减少灾害损失，对于促进交通资源信息共享，促进交通资源的合理配置具有重要意义。

（3）在城市地区，由于城市规划的问题和救援装备的大型化特点，救援装备一般不放置在人口密集的中心区域。同时，每个地区的材料储存是有限的。一旦需要大量的救灾物资，当地的物资将无法满足需求。此时应考虑跨区域应急救援。跨区域综合交通应急调度的核心任务是跨区域任务的分配和应急物资运输路径的规划。灾难或事故后，有必要把材料从紧急材料储备点广泛分布在全国各地，充分利用各种运输方式的运输紧急材料的需求点，和任务需要澄清的类别，流动方向，流路径，运输方式的组合和所需的多式联运作业点。

3.2 多智能体的应急物资调度

（1）灾害发生后，在邻近的多个灾区形成一个大型物资配送中心，每个大型物资配送中心生成一个需求点智能体，统计灾情和应急物资需求信息。救援点对应于一个个分布在全国各地的应急物资储备点。

（2）救援点智能体接收到需求点智能体发送的救援信息后，根据综合路网规划的运输路径，形成包括应急物资种类、应急物资数量、应急多式联運路径等信息的救援方案。并将其发送给需求点智能体。需求点智能体同意救援点智能体提交的救援方案后，救援点智能体开始执行任务。当任务因各种原因无法完成时，救援点智能体需要将信息反馈给需求点智能体进行动态调整。

3.3 出救点智能体路径规划

假设装货只在该区域进行，不同区域之间只进行物料运输。构建了包含3N+2个点的智能体运输路径网络。G=（T，e）e是弧集，T是点集。N为沿途起点、终点及可能发生的应急物资转运区域，A为虚拟原点;C表示虚拟接收器。A到出发地和C到目的地的时间和费用为0。弧是每个节点之间的连接线。弧组可分为运输弧和过渡弧。运输弧表示网络结构中的水平连接线;过渡弧表示网络结构中节点间的纵向连接。给出了该节点物料跨越运输的相关指标，起到了非常重要的作用。

4 结论

本文对交通突发事件进行了调度，并在蚁群算法优化领域进行了有益的探索和研究，为完善我国主要城市的交通突发事件管理系统提供了参考依据。对于传统的蚁群算法，我们对其信息素代谢进行了更深入的分析。经过改进，得到了一种自适应蚁群优化算法。从多种途径中选择最短、最合理、最经济的路径资源，可以达到安排交通应急措施的目的。

参考文献：

[1]高学英.大规模应急救援资源布局与调度优化方法研究[D].吉林大学，2012.

[2]吴启迪.蚁群算法的研究现状及应用[A].中国控制与决策学术年会论文集[C].2001（5）：340-344.

[3]张纪会，徐心和，胡勇.一种新型模拟进化算法—蚁群算法[J].系统工程理论与实践，1999（3）：84-87.

[4]刘志硕.基于自适应蚁群算法的车辆路径研究[J].控制与决策，2005（5）：562-566.

[5]李妍峰，李军，赵达.基于迭代局域搜索的智能优化算法求解车辆调度问题研究[J].系统工程理论与实践，2007（5）：75-81.