合乘出行信息检索算法研究

合乘出行信息检索算法研究

0基于编码匹配的出行信息表达合乘此外，还有“公共汽车”和“乘客”的子词，指许多乘客乘坐公共汽车。John认为合乘方式可减少10%～15%的小汽车出行量,可以有效地提高运输效率、节省出行费用、缓解交通压力和减少能源消耗。早在20年前,合乘就成为欧美国家一项非常普及地减少交通拥堵的措施,近几年来随着生活水平的提高和私家车的大量普及,这种交通方式也在国内许多大城市中流行起来。对于合乘组织(carpoolformation)问题国外已经进行了大量研究,在合乘问题中,出行信息的交流是关键性的环节。目前,北京、上海、广州、青岛等城市已经出现了专业的中介公司提供收费的合乘信息服务,也有很多专业网站发布和检索合乘出行信息。以Internet作为媒介交流出行信息是组织合乘出行的发展方向。但用户以网页浏览的方式从海量的信息中获取所需信息是相当繁琐的,虽然有部分网站提供关键字检索服务,但这种以字符串匹配方式进行的检索只能获取与相应的起点、终点或是某些关键经过点的地名相关的出行信息,对从起始点的邻近点到目的点的邻近点的出行信息则不能进行有效检索。Dailey提出了一种算法,可以检索以用户起始点和目的点为中心的2个矩形区域之间的所有出行信息。但这种方法只考虑起迄点的平面位置关系,没有考虑山川阻隔等原因造成的各点之间的空间距离和平面位置的差别,也无法对检索出来的两区域之间的出行信息进行优选。针对此,笔者引入了图的概念,提出了一种基于抽象的道路交通网络的合乘信息检索算法。1问题描述1.1距离ls本文使用带权图G=(V,E,w)来抽象地表示交通网络。式中:V为结点的集合;E为边的集合;w为边的权重的集合。权重w(i,j)表示从结点i到结点j的出行费用,它可以是行程时间、行驶距离、拥挤程度和道路属性等因素的折衷,为了便于叙述和理解,我们用距离来指代权重。s,d∈V分别表示需要匹配路径的源点和目的点,S,D⊂V分别表示与s和d距离相近的点的集合,称其为团,其中S为源团,D为目的团。团实质上就是G的一个顶点子集,在这个子集中,距中心点(s或d)距离最大的结点同中心点的距离r称为团的半径。s′∈S称为源邻点,d′∈D称为目的邻点,若存在n条起迄点分别为s′和d′的登记信息,则称s′和d′之间存在n条通路,通路记作<s′,d′>。1.2出行路径匹配度的计算分别从给定的源点s和目的点d出发,依次搜索G中尚未加入团的距离s(或d)最近的结点s′(或d′),直至团的半径r大于规定值。将s′(或d′)加入相应的团中,并将其作为当前分析点,逐个考察其与另一个团中各个结点间是否存在通路。如果存在通路<s′,d′>,则检索相应的登记信息并计算这条通路与s和d之间路径的匹配度。f=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪(lsd+ls′d′)/(lss′+ls′d′+ld′d)(lsd+ls′d′)/(ls′s+lsd+ldd′)(lsd+ls′d′)/(ls′s+lsd+ldd′)(lsd+ls′d′)/(ls′s+lsd′+ld′d)(lsd+ls′d′)/(lss′+ls′d+ldd′)(lsd+ls′d′)/(lss′+ls′d′+ld′d)t=1t=2t=3‚lsd=min(lsd,lsd′,ls′d,ls′d′)t=3‚lsd′=min(lsd,lsd′,ls′d,ls′d′)t=3‚ls′d=min(lsd,lsd′,ls′d,ls′d′)t=3‚ls′d′=min(lsd,lsd′,ls′d,ls′d′)f={(lsd+ls´d´)/(lss´+ls´d´+ld´d)t=1(lsd+ls´d´)/(ls´s+lsd+ldd´)t=2(lsd+ls´d´)/(ls´s+lsd+ldd´)t=3‚lsd=min(lsd,lsd´,ls´d,ls´d´)(lsd+ls´d´)/(ls´s+lsd´+ld´d)t=3‚lsd´=min(lsd,lsd´,ls´d,ls´d´)(lsd+ls´d´)/(lss´+ls´d+ldd´)t=3‚ls´d=min(lsd,lsd´,ls´d,ls´d´)(lsd+ls´d´)/(lss´+ls´d´+ld´d)t=3‚ls´d´=min(lsd,lsd´,ls´d,ls´d´)式中:lij(i,j∈{s,s′,d,d′})为从点i到点j的距离,t为匹配的类型。t=1代表用户是车主寻找搭车人,其出行特点是从用户出行起始点出发,到搭车人的出行起始点接载搭车人,然后到搭车人的目的地,搭车人下车后用户再到自己的目的地;t=2代表用户是搭车者,其出行路线与t=1时相反,从车主出行的起始点出发,到用户的起始点,再到用户的目的地,最后到车主的目的地;t=3是用户寻找同伴合乘出租车,其目标是乘坐出租车的距离最短。显然,通常情况下用来联接{s,s′}和{d,d′}的路径的长度对整个出行路线长度的影响最大,所以其出行路线由lsd,lsd′,ls′d,ls′d′中最小的那个决定。匹配度f用来描述出行路径的匹配程度,其倒数1/f表示的意义就是合乘出行的费用与独自出行费用之和的比值,1/f的最小值为0.5,表示两条出行路径完全吻合,合乘出行能使出行费用降低1/2。匹配度的计算结束后,算法还将生成出行的最小费用路径序列,将其附加在检索到的起迄点分别为s′和d′的每一条信息上。在整个搜索过程结束后,对所有检索到的信息按照其与用户出行路径的匹配度进行排序,并按顺序输出检索结果。1.3floyd算法1)adj[i][j]←w(i,j),i,j∈V(构造邻接矩阵adj)。2)cor[i][j]←结点i,j作为出行的起迄点被注册的次数(构造通路矩阵cor)。3)利用Floyd算法由邻接矩阵adj求解所有点对之间最短距离矩阵dist[i][j]和路径矩阵path[i][j]。4)sortp[i][j]←j(初始化要排序的点对点矩阵sortp)5)利用快速排序法以dist[i][sortp[i][j]]为权,对矩阵sortp逐行进行排序。排序结束后,矩阵sortp的第i行,按照距结点i从近到远的顺序存放V中所有结点(在实际应用中,为节省空间,对于矩阵sortpn×m,m可以远小于n)。1.4mass[n]2步骤1n←0;m←0;s—mass←ue001φ;d—mass←ue001φ(分别将源团s—mass和目的团d—mass置空,n和m分别表示源团和目的团中结点的数量);步骤2若dist[s][sortp[s][n+1]]>dist[d][sortp[d][m+1]],则转步骤6,否则(s,d是要进行匹配的起迄点):步骤3n←n+1;s—mass[n]←sortp[s][n];步骤4对k从1到m,若有cor[s—mass[n]][d—mass[k]]>0,则调用过程corexist(s—mass[n],[d—mass[k]]);步骤5转步骤8;步骤6m←m+1;d—mass[m]←sortp[d][m];步骤7对k从1到n,若有cor[s—mass[k]][d—mass[m]]>0,则调用过程corexist(s—mass[k],[d—mass[m]]);步骤8若dist[s][sortp[s][n+1]]<mradius或dist[d][sortp[d][m+1]]<mradius,则返回步骤2,否则(mradius是团半径的上限):步骤9pindex[i]←i(初始化待输出信息索引数组pindex);步骤10利用快速排序法,以pbuffer[pindex[i]].factor为权,对数组pindex按降序进行排序(为待输出的信息按照从小到大的顺序建立索引);步骤11按照索引顺序输出pbuffer中的信息。1.5路径一定面求取路径因子vj步骤1length←0;advpath←ue001φ;置零路径长度length,清空建议合乘路径数组advpath;步骤2若type≠1,type是算法思想中所提及的t,则转步骤4,否则:步骤3v1←s;v2←sadj;v3←dadj;v4←d;转步骤8;步骤4若type≠2,则转步骤6,否则:步骤5v1←sadj;v2←s;v3←d;v4←dadj;转步骤8;步骤6确定v2∈{s,sadj},v3∈{d,dadj},使得dist[v2][v3]=min(dist[s][d],dist[s][dadj],dist[sadj][d],dist[sadj][dadj]);步骤7v1∈{s,sadj}-v2;v4∈{d,dadj}-v3;步骤8length←length+dist[v1][v2];advpath←advpath∪findpath(v1,v2)(过程findpath(vi,vj)返回从vi到vj的最短路径经过的所有结点,采用递归的方法由矩阵path求得);步骤9length←length+dist[v2][v3];advpath←advpath∪findpath(v2,v3);步骤10length←length+dist[v3][v4];advpath←advpath∪findpath(v3,v4);步骤11factor←(dist[s][d]+dist[sadj][dadj])/length;(factor表示路径匹配度)步骤12按照type的值检索所有起迄点分别为s′和d′的登记信息,为提高检索效率,可将搭车、找人、合乘出租3类不同的信息分类存放;步骤13将检索到的每一条信息附加上述求得的匹配度factor和建议合乘路径advpath,存入待输出的结构体数组pbuffer中。2出行检索部分的渐进时间复杂度用n表示图中结点个数,m表示团的结点个数,t表示所有登记信息的条数。显然整个算法的渐进空间复杂度为O(n2)。对于算法的路网信息建立部分,由于Floyd算法的渐进时间复杂度为O(n3),快速排序算法为O(nlog2n),其他矩阵赋值运算为O(n2),所以建立路网信息的渐进时间复杂度为O(n3)。算法的路网信息建立部分测试运行时间如表1所列。对于算法的出行信息检索部分,最坏的情况为源团和目的团中的结点数量均为m/2,而且连接2个团的任意结点对之间都存在通路,在这种情况下,过程corexist共需执行m2/4次。在corexist过程中,需要检索全部登记信息,所以corexist过程的渐进时间复杂度为O(t)。综上可以得出检索出行信息的渐进时间复杂度为O(m2t)。其出行信息检索部分测试运行时间如表2所列。在实际应用中,用户可以接受的搜索半径是有限的,也就是说m可以认为有上界,m2可以被近似地看作一个常数,所以检索出行信息的渐进时间复杂度也可以近似地认为是O(t)。在整个路径匹配算法中,路网信息建立的时间渐进复杂度O(n3)无疑是比较高的,但是实际应用对路网信息的建立没有实时性要求,有实时要求的出行信息检索的近似渐进时间复杂度为O(t),完全可以满足实际应用的要求。由此可以得出结论,本文提出的算法不仅是正确的,而且是可行的。3合乘出行推荐路线笔者使用VisualC++6.0对算法进行了实现,运行结果如图1所示,该仿真实例中用到的抽象的交通路网如图2所示,并假设图中的任意结点对之间都已存在一条通路。其中,“自身出行距离”表示使用检索的用户出行起迄点之间的最短距离;“同伴出行距离”表示该被检索到信息起迄点之间的最短距离;“合乘费率”就是匹配度的倒数,表示合乘总费用与2个人分别出行所用费用之和的比值;选中“检索同时发布信息”单选钮,表示用户同意在检索搭车人信息的同时把自己输入的出行信息加入车主数据库内以供其他搭车人进行检索。“参考路径”一栏显示的是与当前选中信息的用户的合乘出行推荐路线,在该例中用户李先生单独出行的最短路径是7—8—13—14—19—25,而与第8条信息的登记人高先生进行合乘的推荐路线是李先生驾车从7出发,到11接高先生上车,经7—8—13—15到20送其下车,然后再到达目的地25,合乘出行能使2人的出行费用降低到两人分别出行的71.1%。当然,李先生完全可以从检索到的信息中以算法的计算结果为参考挑选多人进行合乘,从而使出行费用进一