基于演化博弈的车辆路径选择研究

安莉

摘 要：基于演化博弈论，围绕如何在车辆路径选择中提高诱导信息有效性和诱导效率等问题展开了研究。通过建立无诱导信息条件下的路网模型和建立诱导信息模型，研究不同初始条件对驾驶员的作用规律；通过拓展无诱导信息条件下的车辆路径选择的模型，设计了结合八邻域摩尔模型和公共物品博弈模型的驾驶员群体策略演化机制，提高了诱导信息有效性和诱导效率。

关键词：演化博弈 路径选择 公共物品博弈

中图分类号：U495 文献标识码：A 文章编号：1672-3791（2018）04（c）-0126-03

伴随着我国经济的腾飞和“十三五”规划的顺利进行，现在我国汽车数量的增长速度相当惊人。汽车数量的井喷式增长，造成了对交通管理的严峻挑战，如何实现对道路资源的有效配置，成为了国内外学者研究的热点问题。为了缓解这个问题，既需要增加基础设施的建设，同时也需要加强对道路资源的有效配置优化[1]。

交通诱导是智能交通最重要的研究领域之一，交通诱导可以为车辆驾驶员提供实时交通信息[2]，帮助车辆驾驶员做选择和决策，提高整个网络现有速率的综合利用率，避免出现局部道路拥堵而另一部分道路没有有效利用的情况[3]。因为上述对交通管理的重要作用，交通诱导一直是国内外研究领域热点。交通诱导是从整个系统的角度出发，通过发布诱导信息可以使整个网络实现最高的利用率，降低车辆驾驶员选择路径的最低成本。诱导信息最直接的作用是通过提供适当的交通信息来诱导车辆驾驶员的路径选择行为。

1 诱导信息条件下的车辆路径选择研究

1.1 路网模型描述

为了更好的分析道路网络路径诱导系统，构建路网模型如图所示：

1.2 诱导信息条件下车辆路径选择模型的建立

距离相近的驾驶员之间组成八邻域摩尔模型，八邻域摩尔模型属于二维方格网络的元胞自动机，具有周期边界条件，每个节点代表每个车辆驾驶员，每个驾驶均有八个邻域驾驶员，如图表示，该拓扑关系表示驾驶员与其邻域驾驶员的的群体博弈关系。

距离相近的驾驶员之间组成八邻域摩尔模型，八邻域摩尔模型属于二维方格网络的元胞自动机，具有周期边界条件，每个节点代表每个车辆驾驶员，每个驾驶均有八个邻域驾驶员，如图表示，该拓扑关系表示驾驶员与其邻域驾驶员的群体博弈关系。公共物品博弈模型中，每个驾驶员和邻域驾驶员进行博弈，每个驾驶员既参加以自己为中心的群体博弈，也要参与以其邻域驾驶员为中心的群体博弈，整个模型初始状态是接受诱导的驾驶员与拒绝诱导的驾驶员均匀混合分布在这个驾驶员群体中，每个驾驶员在初始时以等概率选择接受诱导信息或拒绝诱导信息，即每个驾驶员的博弈策略可选有接受诱导信息（C）和拒绝诱导信息（D）两种。

公式（3）中，nc与nd分别代表这个群体中选择接受诱导的驾驶员数量和拒绝诱导信息的驾驶员数，c（x）代表驾驶员i的成本。驾驶员i收益将以r的倍数增值，然后平分给群体中的所有驾驶员。在该模型中，驾驶员在有诱导信息的条件下，为了提高自身收益，缩短出行时间，向周围邻域驾驶员学习，不断改进自身的策略，选择更优的路径。

1.3 诱导信息条件下车辆路径选择模型的演化

其演化规则如图3所示，其步骤如下：

Step 0：h=h+1，x=0.1，i=0，给r、k、T、β赋值（x为诱导路径的流量所占比例）；

Step 1：初始化，给出模型的初始状态；

Step 2：根据时间行程函数求得选择路径的通过时间；

Step 3：根判断驾驶员第i次收益，确定博弈的初始状态；

Step 4：由博弈初始状态确定第i+1次路径L的流量；

Step 5：i=i+1，若i<100，转 Step 2；否则转 Step 6；

Step 6：若Δpi>0，x=x+0.1，转 Step 1，否则转 Step 7；

Step 7：若Δpi<0，转 Step 0，否则结束。

1.4 数值仿真

如图4-（a）所示，横坐标为演化代数，纵坐标为接受诱导的驾驶员比例。在该初始条件 下，因为考虑一定的非理性因素，一部分驾驶员并没有及时改进自己的策略接受诱导，在演化前期接受诱导的驾驶员比例有一定的下降趋势；随着演化代数的继续增加，驾驶员通过利用模仿邻域驾驶员的学习机制，越来越多的驾驶员开始接受诱导并提高了自身收益。接受诱导的驾驶员比例提高迅速，很快就趋近于1，说明该学习机制下达到交通诱导需要的演化代数更少，收益提高更明显，诱导效率更高，诱导效果更显著。

将图4-（a）与图4-（b）做对比可发现，同样的初始条件下，八领域摩尔模型协作机制下达到博弈均衡只需要20 代左右的演化，而传统演化博弈机制下达到博弈均衡需要100 代左右的演化，说明结合八邻域摩尔模型的交通诱导算法微观上减少了驾驶员的行程时间，减少了需要到达博弈均衡的演化代数，加快了诱导效率。

2 结语

本文在现有车辆路径选择算法研究的基础上，设计了基于演化博弈的诱导信息，进而重点讨论了诱导信息对车辆路径诱导的作用规律并研究了如何提高诱导信息的有效性。并对上述的车辆路径选择算法进行了仿真研究工作，取得了一定的成果。

参考文献

[1] 中华人民共和国国家统计局.中华人民共和国2016 年国民经济和社会发展统计公报[N].人民日报，2017-03-01（010）.

[2] 陆化普，孫智源，屈闻聪.大数据及其在城市智能交通系统中的应用综述[J].交通运输系统工程与信息，2015，15 （5）：45-52.

[3] 赵娜，袁家斌，徐晗.智能交通系统综述[J].计算机科学，2014，5（11）：7-11.

[4] 何增镇.基于Multi-Agent 与博弈论的城市交通控制诱导系统及其关键技术研究[D].湖南：中南大学，2010.

[5] 董斌杰，李克平，廖明军.诱导信息下基于博弈论的路径选择模型[J].北华大学学报：自然科学版，2007（1）：88-91.