基于带偏好自适应评价的公交线路选择问题研究

摘要:在智能交通系统中公汽线路选择是一个重要的问题。该文首先利用公汽的行驶线路进行深度优先搜索,得到从开始站点到结束站点所有可能的乘车线路。然后分别考虑乘车时间Time和乘车价格Price来评价这些乘车线路优劣,最终得到题目要求的最佳线路。为了能够综合考虑Time和Price,通过引入用户期望度ρ,提出了一种带偏好的自适应评价函数来对基于Time和Price的评价方法进行进一步的改进,这个带偏好的自适应评价函数合理表达了查询者的主观意向、乘车线路差异,从而可以满足不同查询者的不同需求。最后通过仿真实验对该文方法进行了有效性验证。

关键词:智能交通系统;轨迹深度优先搜索;自适应评价函数;偏好系数;Logistic函数

中图分类号:TP18文献标识码:A文章编号:1009-3044(2010)02-382-03

Research of Bus Lines Selection with Favorite and Self-Parameters

LU HUI-ling

(Department of Comp., Shanxi University of Technology, Hanzhong 723000, China)

Abstract: Bus lines selection is an important problem in Intelligent Transportation System. Firstly. Using bus lines to do Depth-first search, and all probable lines are obtained from start_station to End_station. Secondly, we use Time and Price to evaluate these lines and get best one. In order to Integrated Time and Price, User expectation degree, that is a evaluation function with favorite and self-parameters, is proposed to realize this idea. This function expresses Subjective Intention and lines difference of inquirer. At last, simulation experiment validate this algorithm and experiment result reach our previous result.

Key words: intelligent transportation system; depth-first search; self-evaluation function; favorite parameters; logistic function

2007年全国大学生数学建模竞赛甲组B题是“乘公交,看奥运”[1]。公汽线路选择问题是一个智能交通系统[2](Intelligent Transportation System)中先进出行信息服务系统(ATIS)的一个重要组成部分。两个站点之间的最佳线路选择问题实际上就是基于最短路径查询的公交乘车路线问题,首先求出从起始点到目标点的距离最优路径,获得构成这条最优路径的站点;将这些站点作为搜索的中转站点,根据这些站点及通过这些站点的公交线路,获得可行的换乘矩阵。对于复杂的公交网络来说,乘车方案的选择不仅依赖于用户的实际取向,所涉及的因素很多,与交通拥挤状况、公交车发车频率、换乘车行走距离、交通费用等有关,除此之外,还应考虑多因素对用户选择乘车方案的影响,明确寻优目标,判断各种条件下乘客的路径选择的原则,提出通用模型和算法,以满足用户各种形式的需求。

文献[2]提出了基于最少换乘的公交最优路径理论,在此基础上设计了公交最少换乘的算法,文献[3]提出了基于自组织理论的路线选择的模型,研究了存在实时交通信息条件下司机线选择行为的演化规律,讨论了模型参数,分析了模型的稳定性;文献[4]从节约存储空间、提高速度要出发,结合最短路径换乘算法给出了一种高效的换乘算法数据模型,并设计了基于站点优先级的公交换乘算法。除此之外还有经典的Dijkstra算法、Floyd算法、贪心算法、A*算法、爬山法等。上述算法在问题规模变得很大的时候,其效率就会呈指数降低。但更为重要的是这些算法都不能体现查询者的主观意向。本文针对这个问题,提出了一种基于带偏好自适应评价的公交线路选择算法,较好的体现了查询者对乘车时间和乘车价格两个因素的考虑。对公交线路的评判较强的依赖于查询者对这两个因素的主观接受程度。

1 问题分析

“乘公交,看奥运”题目中,给出了详细的公交线路及其站点情况,通过仿真计算和推理,我们得到关于这个问题中关于公汽站点和线路的一些基本信息如下:

公汽站点总数(Sation):3957 从S0001~S3957

总公汽线路数(Line):520 从L001~L520

最长公汽线路:L207 长度为86;

最短公汽线路:L93, L234, L471共三条 长度为7;

平均公汽线路长度:29

公汽线路类型:共有三种(上、下行线相同的公汽线路,上、下行不同的公汽线路,环形公汽线路)。其数目分别是:

上、下行线相同的公汽线路数:89; 上、下行不同的公汽线路数:409;

环形公汽线路数:22;

公汽线路票价类型:单一票制、分段计价,其数目分别是:

单一票制的公汽线路数目:283;分段计价的公汽线路数目:237;

2 基于带偏好自适应评价的公交线路选择算法

2.1 算法思想

对于这个问题而言,建立的模型应该考虑三种情况:1) 只考虑时间因素的模型;2) 只考虑价格因素的模型;3) 时间和价格都考虑得模型。对于前两种模型而言,只要分情况讨论换乘站数就可以很容易的得到,所以本文就不仔细阐述这几个模型了,感兴趣的读者可以自己来总结。第三种模型是在前两个模型的基础上进行的,并且要综合考虑时间Time和价格Price两个因素,通常的做法是首先通过归一化消除量纲,其次用加固定权组合得到最后的结果。其缺点在于:

1) 查询者在不同情况下,对换乘次数和乘车站数的忍耐程度是不一样的。换句话说,用固定权值组合得到最后结果与实际情况不符;

2) 查询者在不同情况下,对乘车时间和乘车价格的优先考虑程度是不一样的。换句话说,即使是同一个乘客,有的时候,他会优先考虑时间,有的时候,他会优先考虑价格。而前面的方法无法反映这个情况。

针对上述缺点,本文提出了一种基于带偏好自适应评价的公交线路选择算法,利用自适应调节的时间评判系数来解决第一个缺点,利用偏好系数来解决第二个缺点。

首先我们引入用户期望度ρ:

其中:0≤a,B≤1,α为时间偏好系数,β为价格偏好系数,ω1+ω2=1,0≤ω1,ω2≤1,ω1为时间评判系数,ω2为价格评判系数,ω1满足Logistic增长曲线:

其中:t为任意两个站点之间公交站数,k表示换乘次数,在我们这个实际问题中,k=0,1,2,a, b为函数参数。其函数曲线在a=0.2,b=0.3时的曲线如图1所示。可以看到这是一个S型函数。

模型中的时间评判系数ω1随着换乘系数k的增大而减小,而随着站数t的增大而增大的,在现实生活中换乘次数依据人的心里承受的能力数值是很小的,所以换乘次数一般控制在一到两次,这样站数的多少则客观的决定着时间评判系数ω1的大小。当站数t增幅不大时,时间评判系数ω1的增幅不大;当站数t增幅不大时,时间评判系数ω1的增幅急剧增大;当站数t增大到一定程度时,时间评判系数ω1的增幅又变缓。这种变化与人的心理感觉是一致的。当人乘坐公交时,在站数不是很多的情况下,在心理上会过多考虑的是价格较优;在站数变得越来越多的时候,此时价格的比重开始慢慢下降,人在心理上更多倾向于更多考虑时间,并且随着站数的增加,这种感觉就越强烈,时间被作为首先考虑的因素,其比重增长的很快;当站数很多时,尽管我们对时间仍然十分关注,但其增幅变得缓慢了。所以本文提出了自适应评价函数,函数中的时间评判系数ω1和价格评判系数ω2直观的给出了对这种现象的模拟,从而具有一定的合理性,采用这个函数来计算每条可行线路的用户期望度ρ比单纯考虑Time和Price具有很强的优势。在后面的仿真实验中,我们可以清晰的看到这一点。

模型中的时间偏好系数α和价格偏好系数β是为了描述在实际生活中,不同的查询者由于客观因素或者是一些主观情绪的影响,希望对时间或价格的决定程度进行一定程度的修改,模型中通过对定义一对偏好系数α,β的修正来完成这个事情。当查询者对时间的需求变得很强烈时,可以通过增大时间偏好系数α来改变时间的比重;当查询者对价格的需求变得很强烈时,可以通过增大价格偏好系数β来改变价格所占的比重;在查询者没有上述需求的时候,α,β的取值一般情况下为1。由此我们不难看到,这对参数能较好的满足查询者的一些特殊需求,具有较大的实际意义。

2.2 基于带偏好自适应评价的公交线路选择算法

算法思想:

换乘0次(同一线路)。start的换线行与end的换线行的交集,交集非空表示可以换乘0次,交集为空表示不能换乘0次。

换乘1次。start的m条过站线并集(各过站线上站点集合之并集),与end的n条过站线并集的交集为换乘站集,因为此交集(若非空)的元素(站点)既在start的某一过站线上又在end的某一过站线上,交集即为换乘1次的换乘站集。

换乘2次。start的m条过站线上各站点(可能的换乘站)的换线行并集与end的n条过站线上各站点(可能的换乘站)的换线行并集的交集为换乘站集,因为此交集(若非空)的元素(线路)既通过start的某条过站线上某站点又通过end的某站线上某站点,相应的两站点是换乘两次的换乘站。

算法名称: Self_Favoriate_ShortestPath

算法输入:

Station,Line, Start_Station, End_Station,α,β

算法输出:

从起始站点到终点站,在k次换乘下满足用户需求的可行路线Possible_Line。

Notation:

Station:公交站点数; Line:公交线路数;

Start_Station:起始站;End_Station: 终点站;

Start_set: 包含起始站的所有线路集合;

End_Set: 包含终点占的所有线路集合;

Change_Station:换乘站;α,β:时间偏好系数和价格偏好系数;k: 换乘次数

算法步骤

Begin

% 0 次换乘

for i=1 to line

if L=location (start_station, Line_station)%判断start_station,Line_station是否同时在一条线路L上

begin

Possible_Line_0=add(Possible_Line_0,L,k time(L),price(L), ρ(L));

%对线路L进行时间、价格和用户期望度进行评判,并添加到0次换乘可行解中;

End;End;

for i=1 to line % 1次换乘

begin

(Start_set,End_set)=first_dfs(Line,Station,Start_station,End_station);

%在第一次深度搜索中,从所有线路Line中找出包含起始站Start_station的线路,记做Start_set,从所有线路Line中找出包含终点站的线路,记做End_station;

end;

for i=1 to line

(Change_Station,L)=Second_dfs(Line,Station,Start_set,End_set);

%在第二次深度搜索中,找到从Start_set中的任意一条线路是否与End_set中的任意一条线路是否相交,如果相交,找到换乘站Change_Station,并得到从Start_station经过Change_Station到End_station的线路L;

Possible_Line_1=add(Possible_Line_1,L,k time(L),price(L), ρ(L));

%对线路L进行时间、价格和用户期望度进行评判,并添加到1次换乘可行解中;

End;

for i=1 to line% 2次换乘

begin

(Start_set,End_set)=first_dfs(Line,Station,Start_station,End_station);

%在第一次深度搜索中,从所有线路Line中找出包含起始站Start_station的线路,记做Start_set,从所有线路Line中找出包含终点站的线路,记做End_station;

Second_Start_set=Second_dfs(Start_set,End_station);

%得到所有含有Start_station的线路Start_set中的所有站点所在的公交线路;

End;

for i=1 to line

(Change_Station,L)=Third_dfs(Line, Station, Second_Start_set,End_line);

%在第三次深度搜索中,找到从Second_Start_set中的任意一条线路是否与End_set中的任意一条线路是否相交,如果相交,找到二次换乘站Change_Station,并得到从Start_station经过Change_Station到End_station的线路L;

Possible_Line_2=add(Possible_Line_2,L,k time(L),price(L), ρ(L));

%对线路L进行时间、价格和用户期望度进行评判,并添加到1次转乘可行解中;

end;

Possible_Line=Possible_Line_0∩Possible_Line_1∩Possible_Line_2;

%把0次换乘,1次换乘和2次换乘的所有可能线路合并;

Sort(Possible_Line,time); %给出采用时间评价的所有线路排序;

Sort(Possible_Line,price); %给出采用价格评价的所有线路排序;

Sort(Possible_Line,ρ); %给出采用用户期望度ρ评价的所有线路排序;end;

3 实验结果

本实验采用Matlab6.0编程,利用我们提出的算法,对该问题进行求解,得到如下结论:

1)在0次转乘的条件下,在题目中指定的六对起始站―>终到站中,没有一条可以直接到达;

2)在1次转乘的条件下,从S1557―>S0481,S0148―>S0485是不可达的,其余4对起始站―>终到站全部可达;

3)在2次转乘的条件下,六对起始站―>终到站全部可达;

4)六对起始站―>终到站的具体路线情况如下(限于篇幅,此处只给出一组,如表1)。(下转第396页)

(上接第384页)

在所有可行换乘线路中,价格是相同的,所以价格在其中不起决定性作用。

在所有可行换乘线路中,经过的车站数不同,因此乘车用时差异较大,根据时间来评判,最优的换乘线路编号是:3,5;

根据用户期望度来评判,最优的换乘线路编号是:3,5;需要说明的是,此处的α,β均默认为1。

第3条换乘方案是从S3359乘坐L436公交,在L436的第51个站(S1784)下车,换乘L167,在第17个站下车,即到达终到站S1828。

最优换乘线路序列是:

S3359S2026S1132S2266S2263S3917S2303S2301S3233S0618S0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S0492S0903S1768S0955S0480S2703S2800S2192S2191S1829S3649S1784S1828

第5条换乘方案与第3条不同之处在于中转后乘坐了不同的公交。此处不再详细说明。

参考文献:

[1] /mcm07/Problems2007c.asp.

[2] 唐楚江,蔡忠亮,杜清运,等.基于最少换乘的公交最优路径算法的设计与实现[J].武汉大学学报:信息科学版,2006,31(10):904-907.

[3] 贺国光,冯蔚东.路线选择行为的分支模型[J].土木工程学报,2003,36(1):21-25.

[4] 徐兵,谢仕义.基于站点优先级的公交换乘算法实现[J].计算机时代,2005,7:16-17.

[3] 孙勇.基于宽度优先遍历树的公交线路换乘算法[J].深圳职业技术学院学报,2004,4:10-12.

[4] 周涛,张艳宁,袁和金,等.基于聚类分析和集成改进支持向量机的序列目标识别算法[J].计算机科学,2009,36(1):148-152.

[5] 周涛,张艳宁,袁和金,等.基于聚类分析和集成神经网络的序列目标识别算法[J].计算机科学,2009,36(3):215-219.

[6] 周涛,张艳宁,袁和金,等.粗糙核k-means聚类算法[J].系统仿真学报,2008,20(4):921-925.

[7] 周涛.ACDB中ECA规则调度的一个新算法[J].计算机工程与应用,2007,43(16):175-179.

[8] 周涛.基于线性相关思想的属性约简算法[J].广西师范大学学报,2007,25(4):44-47.

[9] 周涛.ACDB中ECA规则调度的一个新算法[J].计算机工程与应用,2007,43(16):175-179.