基于适应度的驾驶员路径选择模型及仿真

张金金，苏 婧，刘宝迅，张 杰，刘小明

(1.北方工业大学自动化系，北京 100144;2.交通运输部公路科学研究院，北京 100088)

0 引言

动态路径选择问题已取得较为丰富的成果［1-7］，目前，对应该问题的算法与模型研究仍然备受关注。研究表明，城市交通状态在一定程度上存在自相似性［8-10］，而在现代城市中，存在着一大部分这样的车辆，即每天同样的时间点从某一固定的出发地出发到某一固定的目的地，比如说早晚高峰时的上下班车辆。很显然，具有这种特性的车辆对每天同一时段内整个路网车流相似状态的产生起到了很大的作用，也正是这种相似性，使交通流短期预测成为了可能。在一个路网中，驾驶员从出发点到目的点可走的路径非常之多，但驾驶员在出行时的路径选择过程中，常存在以下几种现象:

(1)驾驶员可能在途中根据实际交通状况临时变换预定的行驶路径。

(2)驾驶员一般不会盲目地进行路径更换，其对所更换的路径往往具有一定的先验知识。驾驶员在动态的交通流中决定选择哪条路径一般是在不确定背景下做出的决策，他可能不完全甚至完全不知道目前将要选择的几条路径上交通流的状态，而往往凭借对各条备选路径以往的交通状态知识做出选择。

基于上述分析，在没有信息诱导的情况下，不考虑驾驶员本身对路段的偏好，本文认为驾驶员对各条路径的最近经验和历史经验对本次路径选择过程起到决定性作用，主要依据以下2个条件进行路径选择:

(1)最近一次出行所选路径的行驶时间会对下一次出行有一定影响。

(2)历史出行在各条路径上的行驶时间会对下一次出行有一定影响。

基于此，本文将通过重复多时间步模拟的方法，以上述所列路径选择的两个条件为依据，对驾驶员路径选择自组织演变的整个过程进行分析，以期进一步完善人工交通或交通仿真中车辆模型的建立。

1 宏观微观结合的演变方式

路网由路段和交叉口组成，在从一点到另一点的路径中，可能包括很多条路段和交叉口。实际上，所有路径都可以看作是由图1所示的单元组成(单元中的路径数可能不同)。为分析简单，单元中各路径认为只有路段，实际可以包含路口在里面。如在图2所示的路网中，假设起点为a，终点为d，设某驾驶员只走过如下这几条路径:a-b-c-d;a-b-e-f-d;a-e-f-d。则在行驶过程中面临两次路径的选择，一次在a点，一次在b点。整个路径可以分解成如下几个单元:从a点到 e点 a、b、e组成的单元;从 b 点到 d 点 b、c、d、e、f组成的单元。因此，可以将大路网路径选择过程转换为N个小的路径选择单元，通过对图1路径单元的路径选择进行分析，可进一步反推较大路网中驾驶员的路径选择过程。

定义路网分解规则如下:

(1)某2点间存在大于1条的路径数。

(2)2点间存在的路径包含在定义好的驾驶员可行路径之中。

(3)2点间存在的路径不可能再划分成更小的路径选择单元。

一个具体的路网所包含的最小路径单元数应该有一个计算方式，限于篇幅关系，此处不再对该问题深入探讨。

图1 路径单元示意图

在图1 中，设 A 为起点，B 为终点，L1、L2、L3分别为从起点到终点的3条路径，其长度(或行程时间等)L1＜L2＜L3，从最初的状态开始，此处假设以行驶时间最短为驾驶员选择路径的判据，一般驾驶员在选择路径时在一段时间内通常会尝试在不同的路径上行驶，尝试的结果将对后面出行的路径选择起到指导作用。

图2 路网示意图

对于整个交通系统来说，驾驶员路径选择是一个微观层次的问题，而交通流分配则是一个宏观层次的问题。交通流分配对路段的直接作用结果是对路段车流密度和路段车流平均速度产生影响，而驾驶员作为交通流中的一员，会对路段平均速度有所感受，感受的结果能够对驾驶员下次选择路径产生影响;也就是说，交通分配是路网中所有驾驶员路径选择的最终结果。通过将二者相结合后宏观和微观层次的相互作用、相互影响，最终完成车辆在不同路径上的分配。如图3所示。

图3 交通分配与路径选择间动态关系

微观层次以单个车辆作为分析对象，分析单个车辆在选择路径时所受因素的影响。在确定车辆选择路径的规则后，由于在一次路径选择过程中，与实际相符合，驾驶员并不清楚目前某条路径上的交通状况，而只能凭借以前在该路径上行驶的经验来判定。因此可以逐个车辆循环处理，处理完毕后，统计各路径车辆分布情况，并计算车辆在各条路径上行驶的平均速度。每辆车在选择完路径后将会对所选择的路径特性加以记忆，以备后面再次选择路径时使用。

宏观层次交通分配的结果导致路段交通流密度发生变化，此处以路段行驶时间作为驾驶员路径选择的指标，因此需要得到路段车辆行驶平均速度。车速和密度之间的模型有多种，常用的是线性模型(格林希尔茨速度—密度模型):

其中vf为自由行进车速，ρj为阻塞密度。

在得到车速的前提下，3条路段上的行驶时间分别为 ti=Li/vsi，i=1，2，3。

车辆路径选择过程是一个自适应、自组织逐渐演变的过程，遗传算法很好地模拟了生物的自适应过程，因此，借鉴遗传算法［4-5］中的一些做法，并进行以下定义。

(1)车辆可选路径的适应度，共分为3种。

①初始适应度:

初始适应度为以同样速度分别在3条路径上行驶，在该路径上行驶花费时间的倒数与3条路径行驶时间倒数和之比。

②历史适应度:如果3条路径均选择过，则:

历史适应度为分别以各自历史平均速度在各路径上行驶，在该路径上行驶花费时间的倒数与3条路径行驶时间倒数和之比。

如果只选择过其中2条路径，则未被选择的路径适应度为初始适应度，被选择过的2条路径适应度为:

③最近适应度:假如某条路径最近一次行驶时间分别小于另两条路径的历史平均行驶时间，则对应该条路径的最近适应度C3=1，否则C3=0。

(2)车辆路径选择行为的概率:实际交通系统中，由于驾驶员具有个人偏好及喜欢走固定路径特征，并非每次出行都要进行路径历史适应度的比较，因此与遗传算法中的变异概率相类似，此处规定车辆每时间步进行路径选择时，存在一个执行通过历史适应度对比选择本次所走路径行为的概率，即车辆是否进行路径选择的概率m。

2 车辆路径选择规则

随着时间的推移，每个车辆都会有一个对各条路径认识的过程，而这一过程也是不断积累的。本文中，通过设定表示时间推移的时间步，在每个时间步中，各车辆将完成一次路径选择。通过时间步的设定，实现从最初驾驶员只清楚各条路径除长度而对交通状态一无所知的状态，到最后通过在各条路径行走具备路径历史经验整个过程的模拟。采用重复时间步的模拟方式是为了获得各车辆及各路径的历史属性变化，在实际的交通仿真实现中，可以在本文分析的基础上，直接对车辆设定其历史属性，从而实现具有一定路径选择历史知识的车辆模型。

本文中，对每个车辆关于路径选择所具有的属性定义如下:

(1)上次所在的路径号LastLJ;

(2)上次所在路径时的行驶速度LastSpeed;

(3)路径1所经过的次数LJ1Num;

(4)在路径1上行驶的平均速度LJ1Speed;

(5)路径2所经过的次数LJ2Num;

(6)在路径2上行驶的平均速度LJ2Speed;

(7)路径3所经过的次数LJ3Num;

(8)在路径3上行驶的平均速度LJ3Speed。

每辆车在选择路径时算法如下:

Step1 如果是第一次选择路径，则按初始适应度C1来选择所行驶路径。

Step2 如果曾经选择过其中2条路径，则按历史适应度C'2来选择所行驶路径。

Step3 如果曾经选择过3条路径，则按以下步骤选择:

Step3.1 上一次所选路径上行驶时间是否小于另外两条路径各自历史平均行驶时间。

Step3.2 假如小于的话，则按最近适应度C3来选择所行驶路径。

Step3.3 假如不小于的话，则按历史适应度C2来选择所行驶路径。

由于在本文中主要是探讨车辆在不同路径上的分配过程，其实质是一个宏观过程，因此，文中不涉及车辆在行驶过程中如跟车过程的描述，即不考虑车辆在路径上分配时的车间距等问题，而应用格林希尔茨速度-密度模型来描述车辆的速度-密度关系，认为每条路径上车辆分配数(密度)确定后，车辆的行驶速度相同并得到确定。

在每个时间步，各车辆执行完路径选择过程后，其属性值将有所变化，变化过程如图4所示。

图4 车辆属性值的变化流程

3 仿真结果及分析

设定各条路段长度分别为L1=1000，L2=1500，L3=2000，各条路段自由行驶速度为100，各条路段阻塞密度为 ρ1=200，ρ2=300，ρ3=400，演变步数设为10000次。

图5 车辆总数为300时仿真结果图

首先改变路段车辆总数，设n=300，为避免路径选择行为概率太大而导致路径选择波动过大，本文中对路径选择行为概率进行了一定的限制，设m=0.1的概率下，根据路径历史适应度来重新选择路径，观察仿真结果如图5中(a)、(b)、(c)所示。图5中(a)、(b)、(c)分别表示路径 L1、L2、L3上随着演变次数增加，车辆数的变化过程，图中横坐标为演变次数，纵坐标为路径车辆数。从图中可以看出，随着演变步数的增加，各条路径上的车辆数会有所波动，路径L1上车辆数在120上下波动，路径L2上的车辆数在110上下波动，路径L3上的车辆数在70上下波动。但每条路径平均分配车辆数变化不大，基本限制在20之内，这与实际交通流状态相对比较接近。此外，以趋势线为准，计算每条路径的行驶时间分别如下:

由此可见，车辆路径选择后的交通分配使这3条路径的行驶费用几乎相等，这正好符合Wardrop第一准则，在仿真过程中通过改变车辆总数及改变路径选择行为概率进行多次实验，结果与上述结论基本一致，说明了本文路径选择规则在这里是有效的。

图6 车辆总数为30时仿真结果图

改变路段车辆总数，设n=30，观察结果如图6中(a)、(b)、(c)所示，为了更清楚地看到演变的主要部分，图中截取了前30个时间步的结果。图6中(a)、(b)、(c)分别表示路径 L1、L2、L3上随着演变次数增加车辆数的变化过程，图中横坐标为演变次数，纵坐标为路径车辆数。从图中可以看出，随着演变步数的增加，路径L1上车辆数在经过波动后稳定在30上，而路径L2、L3上的车辆数在经过波动后稳定在0上。路径L2的波动时间相对路径L3来说要长。通过结果可以看出，当车辆总数小于一定数量时，也即车辆数目不足以影响路径行驶时间对比时，车辆一般不再分配在各个路径上，而是集中在行驶时间最短的路径上。

4 结束语

本文针对车辆的路径选择问题，从影响车辆路径选择的路径历史经验和路径最近经验入手，参照遗传算法中的适应度概念，分别定义了车辆的初始适应度、历史适应度和最近适应度，并以此为基础给出了车辆路径选择规则和车辆记忆属性。仿真结果表明，本文给出的路径选择规则虽然相对较简单，但能够较好地模拟车辆路径选择行为，为交通仿真中车辆路径选择模型提供了一种新的思路。

［1］Janson B N.Dynamic traffic assignment for urban road networks［J］.Transportation Research Part B:Methodological，1991，25(2-3):143-161.

［2］Ran B，Boyce D E，LeBlanc L J.A new class of instantaneous dynamic user-optimal traffic assignment models［J］.Operations Research，1993，41(1):192-202.

［3］Heydecker B G，Addison J D.Analysis of traffic models for dynamic equilibrium traffic assignment［M］//Transportation Networks:Recent Methodological Advance.1998:35-49.

［4］Ben-Akiva M，De Palma A，Kaysi I.Dynamic networkmodels and driver information systems［J］.Transportation Research Part A:General，1991，25(5):251-266.

［5］周溪召.驾驶员实时动态路径选择行为组合模型［J］.上海理工大学学报，2002，24(2):109-112.

［6］赵凛，张星巨.基于“前景理论”的路径选择行为建模及实例分析［J］.土木工程学报，2007，40(7):82-86.

［7］韦增欣，陈进来，罗朝晖.基于驾驶员偏好的最优路径选择［J］.交通运输系统工程与信息，2010，10(6):141-144.

［8］贺国光，李宇，马寿峰.基于数学模型的短时交通流预测方法探讨［J］.系统工程理论与实践，2000，20(12):51-56.

［9］Smith B L，Demetsky M J.Traffic flow forecasting:Comparison of modeling approaches［J］.Journal of Transportation Engineering，1997，123(4):261-266.

［10］杨芳明，朱顺应.基于小波的短时交通流预测［J］.重庆交通学院学报，2006，25(3):99-102.

［11］玄光男，程润伟.遗传算法与工程优化［M］.北京:清华大学出版社，2004.

［12］冷亮，杜庆东.基于遗传算法解决车辆最优路径诱导问题［J］.信息通信，2012(2):14-15.

［13］郭海锋，方良君，俞立.基于模糊卡尔曼滤波的短时交通流量预测方法［J］.浙江工业大学学报，2013，41(2):218-221.

［14］曹高明，赵文吉，邓磊.基于ArcGIS Server的最优路径分析方法研究［J］.测绘科学，2012，37(2):138-140.

［15］姜代红.改进的遗传算法在多目标物流配送路径中的应用［J］.科学技术与工程，2013，13(3):762-765.