基于移动Agent的公交与城轨路网博弈配流研究

韩东芮

(西南交通大学交通运输与物流学院)

基于移动Agent的公交与城轨路网博弈配流研究

韩东芮

(西南交通大学交通运输与物流学院)

为更深入的研究路网交通流的分配问题，采用移动Agent技术进行系统的构建，并采用博弈论方法、均衡方法进行建模的分析与论证，以此建立基于移动Agent的博弈配流模型。假设路网上有多个OD对，通过Wardrop第一均衡准则证明每个OD间的个体Agent是同质的，并建立混合策略的Nash均衡，得出路网交通流的均衡分配办法。在求解过程中，采用改进的蚁群算法对个体Agent的均衡过程进行模拟。算例结果表明:改进的蚁群结果非常合理的仿真了移动Agent博弈均衡过程。

城市交通;移动Agent;交通流分配;Wardrop均衡准则;混合策略的Nash均衡;改进蚁群算法

1 移动Agent与博弈方法

1.1 移动Agent技术

移动Agent具有可移动的特性，具有自我控制移动能力、跨平台兼容运行的能力，并且可以模拟人类智能行为，提供一定人类智能交互和服务的程序。移动Agent可以根据系统的需要生成子Agent，子Agent具有同父Agent相同的性质并在此基础上进行一定的延生和改进。移动Agent在分布式人工智能领域及分布对象领域运用广泛，它主要由六大模块组成，分别是Agent模块、生命周期模块、计算模块、安全模块、通讯模块和导航模块组成。这些模块共同组成了两个子系统:思考子系统和反应子系统。思考子系统中含有用符号和标号构成的目标模型，并在决策库中生成的人工智能的规划和决策。另一个是反应子系统，对系统中的重要事件立即做出反应。本文构建移动Agent结构模型图如图1所示，通过下图机制，将出行者转化为移动智能Agent体。

图1 Agent结构模型图

1.2 移动Agent交互系统的建立

通过基于Agent技术的交通分配分析，本文拟将公交与轨道交通之间的交通分配看作是路网中个OD间出行者之间的非合作博弈，但他们可以通过与其他Agent信息共享和路网agent之间的信息交互得出自己想要的信息，经过目标模型的转化后，最后通过决策系统得出将要采取的行为。这种基于Agent的交互和不断学习的过程实际就是Agent之间不断博弈以达到均衡的过程。

(1)个体Agent

个体Agent是基于出行者的愿望、目标、行为三大属性而建立的智能Agent体。因为出行者是具有智能判断的个体，所以个体Agent采取的是动态路由设计，即根据路网状态自由更改自己的组合策略。

个体Agent通过反应子系统与路网状态Agent进行人机交互，接受路网状态Agent传输的路网状态(DLrs，GLrs)

式中:DLrs和GLrs表示路段rs上轨道交通方式和公交方式的客流量负荷，用分数表示;和分别表示第j个OD的A-gent进行第k种乘车组合决策下采用轨道交通方式和公交方式是否经过路段rs(0－1变量);FDrs和FGrs分别表示公交路段rs和轨道交通路段rs上能容纳的最大客流量。

作为个体Agent而言，它们都有着共同的愿望，即以最少的支付到达目的地，且受路网状态、选择的路径和交通方式的影响，但这需要通过目标模型将愿望转化为决策系统可识别的目标。本文通过将纯乘车时间(零负荷状态下的乘车时间)与路网负荷对出行支出的影响进行整合，得出个体Agent的目标模型如下所示

式中:Zjk表示第j个OD的Agent进行第k种乘车组合决策下的综合支付函数;tk表示采用第K中乘车组合决策下的纯乘车时间;λk表示第k种乘车组合决策下的路段数;ξ表示修正系数。

决策系统是基于目标模型所得出的可识别目标进行路径和交通方式的搜索，对于每个Agent而言，都有自己的决策库;这些决策都是基于路网可达性条件下出行者可能采取的不同策略集合下的。个体Agent通过思考子系统中的目标模型的转化和决策系统的决策机制的搜索得到一种交通路线与方式联合函数;再将决策反馈给路网状态Agent，并更新此时路网的状态。该决策即为出行者采取的行为。

(2)路网状态Agent

对路网状态Agent来说，它其实就是出行个体Agent与路网交通的一个交互与共享的终端，当个体Agent出行并选用其中一种交通路线与方式组合策略的时候，个体Agent就会与路网状态Agent发生交互，路网状态Agent接受到每个出行Agent的组合信息，并及时更新历史路网状态。

1.3 Agent博弈均衡

对于每个OD间个体Agent而言，由于相同OD间个体Agent是同质的，当路网达到用户均衡时，Agent会选择总走行时间最短的决策集合，即Wardrop第一均衡准则。

由于不同个体Agent存在着博弈关系，本文使用博弈论的方法考虑交通均衡问题，不同OD间的Agent面临着不同组合策略选择的混合策略Nash均衡博弈。第j个OD的智能体Agent的混合策略为公交与轨道交通的组合决策与概率的线性组合

式中:pjk表示第j个OD的个体Agent做出决策k的概率。其中

综合支付函数包含路径、方式、路网状态的因素，本文将混合策略的综合支付函数表达如下

式中:DL、GL分别表示轨道交通和公交的路网状态。

同理，其他OD间的组合决策与概率的线性组合

对于有j个OD的Agent系统而言，不同个体Agent在信息共享和与终端Agent交互条件下，独立无合作追求最大利益情形下的博弈平衡，这样就形成在Wardrop第一均衡准则下的混合策略Nash均衡。

2 基于移动Agent的博弈配流模型

通过对Wardrop第一均衡准则下的混合策略Nash均衡博弈分析，基于移动Agent的建模可以表示为如下一维极值问题，对每个OD对j的智能体Agent来说，都有如下极值问题

3 改进蚁群求解算法

3.1 改进蚁群算法依据

根据对移动Agent路径、方式走向设计的博弈配流模型建立与分析，一方面，通过个体Agent与路网Agent终端的交互，体现了OD对之间的相互抑制，是逆向反馈的过程;另一方面，相同OD对之间的信息共享，体现了个体Agent之间的相互促进作用，是正向反馈的过程。这是人工智能的表现。蚁群算法也是一种智能算法，通过模拟蚂蚁外出觅食时根据前面蚂蚁所遗留下的信息素的强度来指导自己的运动，而通过的对信息素识别和正负反馈的改进刚好可以实现上述两个方面的智能。所以本文选择了蚁群算法。

结合本文的研究情况，将对蚁群算法进行如下两个方面改进:

第一，蚂蚁能通过不同OD间的浓度进行识别;

第二，浓度的在不同范围内能进行正负反馈;

第三，不同OD对的蚂蚁能识别相应的路径方向;

第四，需对同一个OD间的个体Agent之间通过信息素来进行正向反馈，而不同OD间的个体Agent之间则通过信息素相互抑制的问题进行修正。

3.2 蚁群算法的改进

(1)能见度与转移规则改进

将j个OD对集合假设为蚁群A1，A2，…Aj，由于个体A-gent倾向于采用路径综合支付函数较小的组合决策，所以对能见度ηrs规则进行如下修正

G(t，1)，(t，2)，…(t，j);轨道交通决策方式路径rs上信息素浓度为(t，1)(t，2)，…(t，j)。为了浓度的在不同范围内能进行正负反馈，定义一个负指数函数

式中:τrs为路段rs上的最佳浓度;ε为负指数分布的陡峭系数，ε越小，曲线越陡峭。

此时蚁群Aj的蚂蚁a由路段r转移到路段s的转移概率可表示为

(2)局部规则改进

对局部规则的改进可以有效地避免个体Agent大量收敛到某一路径或方式，个体Agent在完成每一步搜索后，应用下面的更新规则更新它所经过路径的信息素强度

式中:Q表示信息素强度;La表示第a个体Agent在本次循环中所走路径组合长度。

基于以上改进方法，算法步骤如下

Step1:禁忌表tabua置空，初始化τrs和Δτrs(归0)，将个体Agent A1，A2…，Aj分别置于1…j个顶点上;

Step3:根据tabua的记录，不断更新τrs与Δτrs;

Step4:对各路径(r，s)分别设置Δτrs=0;

Step5:记录到目前为止路径组合，若不满足终止条件，清空禁忌表，转步骤(2);

Step6:输出最后的方案。

4 算法仿真

本文假设一个路网图进行算例分析如图1所示，其中红色箭头表示轨道交通线路(双向);直线表示公交线路;其布局图节点之间纯走行时间数据如表1所示，其中G开头表示公交线路时间，D开头表示轨道交通线路时间(min)。

图2 网络布局图

表1 节点走行时间表

公交线路与轨道交通开通路线设置如表2所示。

表2 线路设计表

我们初始化OD如表3所示，单位为min。

表3 OD表

续表3

本文为了仿真更真实，对换乘时间做如下规定:换乘时间随着换乘次数进行累加，时间为5 min，现在按照算法步骤进行迭代，迭代出的配流部分结果如表4所示。

表4 地铁1号线各路段配流仿真表

表5 1路公交车各路段配流仿真表

部分计算结果见表4、表5，由试验结果可以看出，相对于传统的蚁群算法，改进的算法在基于Agent人工智能方面的做了相当大的提升，能非常好的模拟智能体也就是出行者的出行选择的思维和博弈的过程;迭代次数也大幅度减少。相对于传统的蚁群算法而言，改进的智能蚁群算法具有更好的全局最优解搜索能力和智能性，收敛性更好。通过对蚁群算法的改进，本文很好的实现了移动Agent系统的仿真与求解。

5 结论

用移动Agent理论结合博弈论来模拟解决交通分配中的出行者意愿选择是非常具有研究意义的;根据对War drop均衡和混合策略Nash均衡准则研究用来表述出行选择能够体现出行行为的多重性和多元性。而蚁群算法的引入求解非常合理的解决了这个复杂的Agent智能博弈模型的求解方法问题，也为问题的完善开辟了一条新思路。

［1］ 艾毅，李宗平.基于蚁群算法的多维Stackelberg博弈配流研究［J］.城市轨道交通研究，2014，(1):95－98.

［2］ 何增镇.基于Mu1ti－Agent与博弈论的城市交通控制诱导系统及其关键技术研究［D］.博士学位论文.中南大学，2009.

［3］ 袁长伟，蔚欣欣，陆化普，卞长志.基于斯塔克尔伯格博弈的路网均衡交通分配方法［J］.中国公路学报，2009，(5):90－93.

U491

C

1008－3383(2015)10－0161－03

2015－03－09

韩东芮(1988－)，男，硕士研究生，研究方向:城市轨道交通。