基于矢量匹配的人口稀疏区域乘车出行算法研究

张 凯,张 强,庄 梁

(南京信息工程大学信息与控制学院,南京210044)

基于矢量匹配的人口稀疏区域乘车出行算法研究

张 凯*,张 强,庄 梁

(南京信息工程大学信息与控制学院,南京210044)

郊区及新建市区等人口稀疏区域的人们乘车出行多有不便,为消除这类区域乘车出行的缺陷,进行了出行算法研究.本文提出了矢量匹配算法和接载路径算法.首先,对出行者请求的出发地和目的地位置信息与服务区域道路网主路线进行方向匹配;其次,对所有匹配成功的请求位置信息进行全局最优路径规划;最后,根据路网模型并结合出行算法给出实验数据分析和结论.研究结果表明:本文提出的出行算法具有常规公交车所不具备的人性化的点到点服务特征,服务品质高,乘车费用较出租车费用实惠,平均每位出行者的乘车时间在可接受范围内,乘客满意度较高,可以很好地满足人们出行方便快捷的意愿.

城市交通;出行算法;矢量匹配;稀疏区域;小型公交车;接载路径规划

1 引 言

近几十年,我国政府制定了一系列相关政策,明确以公共交通为主的城市交通发展策略.当前,尽管我国城市公共交通网络覆盖面越来越广,但依然存在亟待解决和完善的问题[1-4],最明显的地域是在郊区、新建市区等人口稀疏区域.长期以来,由于这些地区公交车班次少,路线稀疏,发车时间长,缺乏灵活性等原因,常常给依靠公交车出行的人们带来不便与困扰,人口虽相对稀疏,但仍需要一个良好运营的公交系统或全新的公交运营模式.如何有效地改变此类区域当前交通出行落后的现状,提升公交出行服务品质,是城市相关部门需要深入研究的实际问题,也是相关学者值得探究的问题之一.

目前研究人口稀疏区域乘车出行的文献并不多见.Cortes和Jayakrishnan在2002年提出高覆盖点到点公交系统[5].Khattak和Yim在2004年对旧金山港湾面向消费者需求个性化的响应服务(PersonalizedDemand-ResponsiveTransit,简称PDRT)进行了调查[6],大约60%被调查的人乐意选择PDRT,大多数人愿意为调度灵活的PDRT服务支付额外费用.许多文献调查显示,将固定路线公交服务改进为不固定公交服务时,公交车的载客量稳定增长,如在威斯康星洲美林市Merrill-Go-Round的公交示例[7]以及在汉普顿、纽波特纽斯和约克郡的半岛公交[8].遗憾地是,以上相关文献只是研究区别于普遍意义下公交服务的一些变化和改进,并没有具体研究人口稀疏区域下的行车服务.

本文针对性地以郊区、新建市区为研究区域,依靠小型公交车,对出行者请求的出发地和目的地两点位置信息和区域主行驶路线进行算法匹配分析,研究是否满足前去接载的要求.最后,对所有满足接载要求的位置点进行全局最优接载路径规划,用得到的算法结果来指导小型公交车的行驶.通过算法研究,实现了一种方便可行的乘车出行接载服务方法,很好地满足人们在此类区域普通多样化的出行需求.

2 出行算法研究

研究基础设定:小型公交车在服务区域中单向往返运行；服务区域中所有道路干线比较规范,不存在形状不规则干线；服务区域有一条主行驶参考路线；研究的出行者请求位置点都在行车位置前方,行车位置后方的不予考虑；对于所有符合接载条件的请求者允许小型公交车偏离参考路线去进行接载服务.

此外,由于地图中道路网错综复杂,所以综合各种人口稀疏道路情况考虑,最终选择了算法更具普遍意义的服务区域为矩形、主行驶参考路线为直线或近似直线的路网模型.

2.1 矢量匹配算法研究

关于矢量匹配算法研究:出行者的两点位置信息在服务区域内与服务车辆的主行驶参考路线进行矢量匹配判断,主要是起止经纬度构成的矢量与主行驶参考路线方向矢量的匹配.若结果在匹配的接载范围内,则断定其符合接载要求,予以接载服务.

如图1,w和w′分别表示请求的位置点和请求到达的目标位置点,mdd为车主行驶参考路线直线化后的矢量方向,mddp为车主行驶参考路线直线化后矢量方向的垂线方向,β为的夹角.

β可表示为和

式中 ww′lat=w′lat-wlat,ww′long=w′long-wlong；

wlat,wlong——出行者当前位置点的经度和纬度；

w′lat,w′long——出行者目的地位置点的经度和纬度；

mddx,mddy矢量mdd方向的两个方向值.

图1 矢量匹配分析Fig.1 Vector matching analysis

此外,令

式中 α——区域车辆的服务阀值.

服务阀值α的大小决定车服务接载率的高低,影响出行者请求接载成功率的高低,对整个系统的运作很重要.α越大,接受服务请求的人数越多,车服务接载率就越高.

式(2)中,d的正负决定出行者的请求服务是否会被接受,矢量匹配的成功与否.当d＞0时,β在服务阀值α之内,车接受出行者的请求服务,匹配成功；当d＜0时,β超越服务阀值α,意味着放弃此出行者的请求,车辆不会接受出行者的请求服务,匹配失败.此时,出行者可以向其它车辆提出请求服务,每辆车的服务都是相互独立的.

一般来讲,具体服务阀值的大小需根据具体稀疏区域加以设定.

2.2 接载路径描述

由于本文的研究地区是人口稀疏区域,所以不涉及道路堵塞问题,整个研究的区域道路时刻畅通.总体接载行车路径[9]如图2所示.

图2 总体接载行车路径Fig.2 Overall pick-up driving path

图2中,两相邻位置点间路径条数可表示为

式中 path(n-1→n)——位置点n-1与n间的路径；

t(n-1)——位置点n-1与n间路径数目.

总体行车接载路径为

式中 Path(1→n)min——从位置点1开始,途经位置点2,3,…,n-2,n-1并到达位置点n的最短路径.

2.3 接载路径算法研究

引入步步逼近路径[10]概念:从车辆当前位置沿着路径向目标点移动的过程中不会出现距离“倒退”现象,车辆位置和目标点总在不断逼近中,直至抵达目标点,由此产生的当前路径即为步步逼近路径.公式为

式中 Dpn(x)t——车在位置点n-1和n间某一条路径x上行驶在t时刻与位置点n的距离；

Dpn(x)(t+1)——车在位置点n-1和n间某一条路径x上行驶在t+1时刻与位置点n的距离；

Dpn(x)——车在位置点n-1和n之间某一条路径x上行驶与位置点n的距离；

Tn——到达位置点n的时刻.

图3 算法搜索区Fig.3 Algorithm search area

算法基本步骤如下:

第1步限制算法搜索区.

利用起点和目标点的位置信息,将搜索过程限定在起止点方向上,并把搜索区域缩减为一个椭圆,在小范围内进行搜索[11,12].构建限制搜索区的方法为

Li+e(i,d)≤E(o,d)(7)

式中 Li——车位置点o到当前节点i的最短路径的长度；

e(i,d)——节点i到目标位置点d的路径长度估计；

E(o,d)——车位置点o到目标位置点d的最短路径长度上界的估计.

如图3虚线椭圆所示,在车位置点▲和目标位置点1间构建了一个椭圆的限制搜索区域,从而大大提高了算法效率.

第2步确定相邻位置点间的步步逼近路径,若无步步逼近路径,确定普通路径.

在位置点▲和位置点1间共有7条路径,其中步步逼近路径有4条,如图4左侧图所示,右侧图所示为3条普通路径.

第3步

(1)对确定的步步逼近路径逐一进行路径求距,通过最后的分析比较确定最优路径.

图4中,通过对交叉节点位置信息的提取,计算出各个节点间的距长(最短距长定为1,其它的距长均以最短的距长1为参照标准),从而计算出4条步步逼近路径的距长.

通过比较确定,最优路径为路径2.

(2)若相邻位置点间步步逼近路径不存在,则从普通路径中寻求最优路径.

如图4右侧图所示的3条路径则为位置点▲和位置点1间的普通路径,如果前4条路径不存在,则从路径5,路径6和路径7中确定最优路径.

第4步位置点加1,重复上面三步,直到最后一个位置点,最终求解出全局最优路径.

前三步是以车当前位置点▲和位置点1为相邻的两个位置点加以讨论.根据前三步,对位置点1和2,位置点2和3(图5中的1'),…,位置点n -1和n进行相同的操作,得到各自最优路径,全局最优路径则是它们的集合,最优路线[13]如图5所示.

在系统运行中,当有新请求来临并得到接受时,假设新请求两个位置点为q和q′,根据其在整个路网中所处的位置与相邻的位置点间重新进行最优路径计算,计算得到的最优路径将取代这一计算中用到的原有位置点间的路径并插入整合到当前总体行驶路径中,达到每当有新的接载服务时总能够实时地更新最优路径.

图4 位置点间的行车路径Fig.4 Driving path between points

图5 最优路线Fig.5 The optimal route

3 实验结果

3.1 实验前提

前提一:实验支持.

出行者通过手机客户端将当前出发地位置和目的地位置发往公交公司后台中心；后台中心对数据进行匹配处理；匹配成功的信息添加整合到区域中最合适的公交车；后台中心对该公交车进行动态最新路径规划,并将规划结果通过无线发送给对应的公交车.

前提二:实验假设.

(1)小型公交车所在服务区域为矩形区域,主行驶路线为直线或近似直线；请求的出行者随机分布在服务区域中,随机地提出服务请求；出行者提出的服务请求是一种正向请求,非与主行车方向相反,以服务阀值α=90°为上限.

(2)小型公交车座位数为15个,综合油耗为12升/百公里,汽油价格取7元/升,服务区域的横向跨度为10 km,服务区域纵向跨度为横向主行驶参考路线两侧各1.5 km,平均行驶速度为30 km/h.

3.2 实验结果分析

实验从小型公交车服务接载率,单向总体运行时间,出行者付出的接载费用,以及乘客(出行者)满意度四个方面对出行算法进行了比较和分析.实验结果图6所示.

图6 服务阀值为30°、60°和90°时车服务接载率Fig.6 Pick-up rate of small bus service in the service threshold of 30°、60°and 90°respectively

图6为实验中具体地一组服务阀值和车服务接载率的关系图,图中折线表明:在同一个服务区域,随着服务阀值的增大,车服务接载率也将随之增大.

为了满足高品质服务的特点,小型公交车的总体接载人数需动态维持在满座15人以内,以确保人人有座,因此,服务阀值大小的确定成了实验最关键的问题.实验中的小型公交车位于区域的正向起始端,实验过程中,当预设区域均匀随机地动态布置20个有出行需求的出行者时,为让公交车上下车人数动态地维持在15人,实验中服务阀值需设为50°；当预设区域均匀随机地动态布置15个有出行需求的出行者时,为让公交车上下车人数动态地维持在10人,实验中服务阀值需设为45°.显而易见,在正常情况下,服务阀值决定了车服务接载的人数,阀值的大小影响了服务接载率的高低.

图7 服务阀值60°时运行时间、接载费用和乘客满意度在不同请求接载人数下的比较Fig.7 Comparison about running time,pick up fee and passenger satisfaction under different number of requesting to pick-up in the service threshold of 60°

图8 服务阀值90°时运行时间、接载费用和乘客满意度在不同请求接载人数下的比较Fig.8 Comparison about running time,pick up fee and passenger satisfaction under different number of requesting to pick-up in the service threshold of 90°

服务阀值取60°和90°两种情况.通过实验,分别给出请求接载人数在5、10、15、20四种情况下,出行者付出的接载费用、单向总体运行时间、乘客满意度的比较图7、图8所示.

图7和图8表明:

(1)请求接载人数相同的情况下,服务阀值越大,运行时间越长,但接载费用会降低.

(2)随着请求接载人数的不断增大,接载费用随之降低,但运行时间会不断加长.

(3)当请求接载人数在由10变为15后,乘客满意度由上升趋势变成下降趋势,说明在请求接载人数超过15人后,随着服务阀值的加大,小型公交车已不能完全保证人人有座,且此时总体的运行时间过长,虽然接载费用降下来了,但依然影响了乘客满意度的提升.

(4)服务阀值60°下请求接载人数为10时,乘客满意度最高,为95.4%.

根据以上实验结果分析得出:服务阀值的设定尤为重要.服务阀值太小,会导致服务接载率降低,接载费用增加,且在请求人数较多时,会导致部分出行者二次请求的麻烦；服务阀值太大,整体运行时间就会太长,尤其在请求接载人数超过15人的情况下,无法再满足快捷出行的特点.

此外,若要赢得最佳乘客满意度,保证整个系统的健康运作.需根据具体的稀疏区域类型合理地设计矢量匹配算法中的服务阀值α,在保证公交运营收益良好的前提下,使服务阀值、总体运行时间、接载费用间达到综合最优,从而确保系统高品质个性化服务的顺利进行.

4 研究结论

本文针对人口稀疏区域,提出了基于矢量匹配的乘车出行算法.作为一种全新的公交出行方式,它改变了以往常规公交的运营模式和服务理念,通过对矢量匹配算法和矢量匹配下接载路径规划算法的研究,得到了更符合人口稀疏区域下的乘车出行方法,丰富了现有的公共交通出行方式.研究所依靠的小型公交车具有常规公交车所不具备的点到点服务的特征,人性化十足,服务品质高.根据实验结果显示,区域中乘客搭载小型公交车的费用要比日常的出租车费用更加合理实惠,接近于普通公交车的乘车费用,平均每位出行者的乘车时间也在可接受范围内,总体乘客满意度较高.

本文的研究基础是服务区域为矩形,主行驶路线为直线或近似直线的人口稀疏区域,由于实际的人口稀疏区域类型较多,且服务区域中道路干线形状各异,因此对于其它类型的人口稀疏区域的乘车出行算法研究将是后续进一步研究的课题.另外,后续研究中,在本文研究的基础上还可以加入更多细微的贴心服务,适当增加小型公交车接载费用,从而更好地优化提升公交车服务品质,这对于公交出行的人们来讲,必然是最佳选择.

[1] 蔡敬艳.加快新郊区公共交通发展的建议[J].上海公路,2006(3):59-62.[CAI J Y.Suggestion on fastening development of public transit system in new suburb[J].Shanghai Highways,2006(3):59-62.]

[2] 陆磊,李霞飞,周俊红.上海市郊区公共交通发展问题研究[J].城市公用事业,2007,21(4):3-5.[LU L,LI X F,ZHOU J H.Research on suburb public transportdevelopmentinShanghai[J].Public Utilities,2007,21(4):3-5.]

[3] Cervero R,Day J.中国城市的郊区化与公交导向开发[J].上海城市规划,2010,4(93):50-59.[Cervero R,DayJ.Suburbanizationandtransitoriented development in China[J].Shanghai Urban Planning Review,2010,4(93):50-59.]

[4] 杨明,杨涛,凌小静,等.交通引领下的南京城市规划编制探讨[J].规划师,2012,28(8):38-42.[ YANG M,YANG T,LING X J,et al.Transportationled Nanjing urban planning compilation[J].Planner, 2012,28(8):38-42.]

[5] Cortes C E,Jayakrishnan R.Design and operational conceptsofahigh-coveragepoint-to-pointtransit system[J].Transportation Research Record,2007, 1783(2002):178-187.

[6] Khattak A J,Yim Y.Traveler response to innovative personalized demand-responsive transit in the San Fran-ciscoBayArea[J].UrbanPlanningand Development,2004,130(1):42-45.

[7] Durvasula P K,Smith B L,Turochy R E,et al.Peninsula transportation district commission route deviation feasibility study[M].Virginia Transportation Research Council,FHWA/VTRC 99-R11,Charlottesvile,1998.

[8] Durvalula M,Priya K.A gis-based support tool for route deviation transit scheduling and servicedesign [M].Charlottesvile:University of Virginia,1999.

[9] Rahmani M,Koutsopoulos H N.Path inference from sparse floating car data for urban networks[J]. TransportationResearchPartC:Emerging Technologies,2013,30:41-45.

[10] Li Q Q,Zeng Z,Zhang T,et al.Path-finding through flexible hierarchical road networks:An experiential approach using taxi trajectory data[J].International JournalofAppliedEarthObservationand Geoinformation,2011,13:110-119.

[11] Fu L,Sun D,Rilett L R.Heuristic shortest path algorithms for transportation applications:State of the art[J].Computers&Operations Research,2006,33: 3324-3343.

[12] Liu B.Route finding by using knowledge about the road network[J].IEEE Transactions on Systems,Man,and Cybernetics-part A:Systems and Humans,1997,27 (4):436-448.

[13] Quadrifoglio L,Hall R W,Dessouky M M.Performance anddesignofmobilityallowanceshuttletransit services:bounds on the maximum longitudinal velocity[J].Transportation Science,2006,40(3): 351-363.

Bus Travel Algorithm Based on Vector Matching in Sparsely Populated Areas

ZHANG Kai,ZHANG Qiang,ZHUANG Liang
(School of Information and Control,Nanjing University of Information Science&Technology,Nanjing 210044,China)

People in sparsely populated areas such as suburbs and new cities traveling by bus have much inconvenience.To eliminate the defect of bus travel in these areas,a travel algorithm research is conducted. This paper proposes two algorithms,vector matching and pick-up path.Firstly,to match the direction between traveler's departure and destination location information and main road network route of service area. Secondly,a global optimal path planning is conducted for all successful matched request location information. Finally,experimental data analysis and conclusion are given based on the road network model and travel algorithm.The result shows that travel algorithm have the characteristic of humanized and point-to-point services to be different form regular bus,service quality is high,and travel cost is cheaper compared with taxi fee.In addition,average traveler's journey time is also within acceptable range,passenger satisfaction is higher,and the algorithm can well satisfy the wishes of people to travel conveniently and quickly.

urban traffic；travel algorithm；vector matching；sparsely populated areas；small bus；pickup path planning

U492.4

A

U492.4

A

1009-6744(2013)06-0127-07

2013-06-06

2013-07-15录用日期:2013-08-14

张凯(1965-),男,山东泰安人,教授,博士.

*通讯作者:zkark@163.com