翻译以.原文和在同一文件中前

本文为出租车和需要乘车的乘客提供一个合理的推荐，基于的知识包括：1）2车GPS中。一方面，我们给出租车提供可选的一些停车地点（以及到达这些地点的路径，朝这些地点行驶的过程中（包括在停车地点和前往目的地的过程中，更有可能遇到（及和他们之间的距离，使他们更有可能遇到空载的出租车。本文提出了一种停车地点发现算法，并且通过交通轨迹获取上述需要的信息（用概率表示；随后，将这些信息输入到一个概模型中该模型基某个所在的地点以当时的间估计每停车11012000：出租车，推荐系统，停背景简 技术综 知识预 研究动 模型描 出租车推荐系 载到下一个乘客的可能 载到下一位乘客之前经过的时 下次行程的行驶距离和行驶时 乘客推荐系 线下数据挖 停车地点的侦 候选停车地点侦 过滤候选停车地 停车地点集 时间相关的概率计 路段相关的概 停车地点相关的概率计 线上推荐系 数据验 数据设 停车地点挖掘算法的 推荐系统实验总 参考文 示，41%的对象每周都会乘出租车出行，而每天都乘坐出租车的受访者占总人数的25%。然而，为了方便人们的出行，纽约、东京、伦敦以及这样的大城市则拥有相GPS理位置和出租车寻找乘客的请求的时间，我们给出租车一个推荐的地点，使他 便于公司指挥也更加安全。一般来说，这些出租车会以一个固定的频率，比如2分钟一次，比如，收入高的通常去哪拉客？他们如何快速找到需要乘车的乘客？通过这两方面信息，我们就可以给推荐载客地点，给乘客提供更容易打到车的地点，并且预测的利用大量出租车的GPS轨迹准确地发掘“停车地点”。这些停车地点是租车经常等乘客的地点。从这些地，我们可以计算如果朝着一个地点行驶，他能够载到客人的几率（也包括往停车地点的载到的客人从用一个庞大的出租车GPS轨迹历史数据（12000辆出租车110天的数据）评估我定义2R路线是指一个路段序列，如Rr1→r2r𝑛r𝑘+1s=𝑟𝑘e(1≤k<𝑛)。一条路线的起点和终点可以表示为Rs=𝑟1s,Re=𝑟𝑛e，，停车P详见Table1。在后两个状态中，出租车都是没有载人的。上文停车状态中，在等待载客，比如在某地排队等待乘客乘车。这个状态在机场、馆、购中心等比较常。们把这些经出现出车待载定义4Figure2.注意一辆出租车在两个停与其他公共交通比如车、地铁不同的是，出租车每天并不按照固定路线行驶，们将所有分为3组，前10%为高收益组，后10%为低收益组，余下的是中间组。的是，时期，出租车非常容易找到乘客，也就是说，此时出租车往往高收入组、低收入组和所有平均的载客率。在图中可以非常明显地看出，上午10经验丰富的通常知道什么时候某架飞机，某趟火车到达，以及影院何时散场， 事实上，经验老道的本地不是到处随便转寻找客人的，一个乘客下车后，他们往往是有目的地去某个地方寻找新的乘客。Figure4是一个信息密度分散图，展待乘客可能有更大的几率载到乘客。正确的做法是像图中热点左上角的那样，验，这些往往不会随意巡航寻找乘客，而是更愿意在更可能载到乘客的地点等待。出租车推荐系统目的在于给们提供最好的停车地点和行驶路线。但是我们应如何定义“好”停车地点呢在𝑇时间车的上一个乘客车，们望的是尽快找到下个乘客，且下一乘客要地方越远越，这样就可以取PRP𝑟1𝑟2𝑟𝑛。我们定最长时间是𝑡𝑚𝑎𝑥那 采取了行动Λ𝑅𝑃。在这一部分 如 采取了行动Λ𝑅𝑃，那么他需要多久才能载到客 𝑆̅S=⋃客。𝑡𝑖=∑𝑖𝑟𝑗.𝑡指从起点行驶到𝑟𝑖经过的时间。则在𝑇0+𝑡𝑖在路段𝑟𝑖载到客人的概𝑝𝑖=Pr(𝐶→𝑂|𝑟𝑖,𝑇0+ 𝑝∗=Pr(𝑃→𝑂|𝑟𝑖,𝑇0+

𝑖=Pr(𝑆𝑖)

𝑝1∏(1−𝑝𝑗) 𝑖=2,3,…, 𝑝∗∏(1−𝑝𝑗) 𝑖=𝑛+ 上述公式中的 (1−𝑝𝑗)是沿着路径R行驶而没有载到客人的概率。我们那么我们是否应该给推荐那条Pr(̅𝑆̅𝑅̅)最小的路线呢？这显然是不合理的，因为如果这样很可能沿着所有路网行驶一圈。在实际应用中，我们可以推荐一条最快捷的路线或者使Pr̅𝑆̅𝑅̅最小，但是行驶距离又不超过一个阈值。这可以由一个简单的最短路径如 采取行动Λ，随量T表示从现在的时间𝑇

T=𝑇𝑅+ 注意𝑇𝑅和𝑇𝑃并非相对独立的，实际{𝑇𝑃= if𝑇𝑅≤𝑡𝑛,𝑇𝑃= if𝑇𝑃>Pr(𝑇=𝑡|S)=

=𝑡𝑖,S

Pr(S) 𝑖=1,2,…,𝑛−1, Pr(S𝑛)+

𝑖=

|𝑆-=∑=𝑡|𝑆)= (∑𝑡Pr(𝑆)+𝑡Pr(𝑆

Pr(W)=∏(1−

𝑗=1再次调用公式(3)，我们得到𝑝∗= 𝑗=1

Pr(𝑇𝑝=𝑡∗|S)

(1−Pr(W))

𝑗=

因此，𝑇𝑝的条件期望

∗ 1≤𝑗≤{E[𝑇|S]

Pr(𝑊)∑𝑝𝑗 ∗Figure7(b)E[T]的值，它们是随着时间缓慢变化的。注意停车地点P1的巡航时间是最短的，但是它载到客人的概率Pr(S)却是最小的。下次行程的行驶距离和行驶时间，在事件S发生的前提下，随量是当出租车采取行动Λ时下一段行程 𝑑𝑗的概𝑞𝑗=Pr(𝑑𝑗−∆𝑑 ≤𝑑𝑗+∆𝑑|𝑆𝑖,𝑇0+ 𝑚𝑎𝑥是第一段路程的最大值。则，得到的条件概率分布如𝑛+1Pr(𝑆) =𝑑|S)= 𝑖

我的路段。这个问题远比推荐系统中遇到的问题简单。r(C;r|t)指在时间t路段r，乘（围Ω以内、r(r|)最高的路段r=argmaxPr(C; Figure9显示了候选停车地点的侦测过程，𝑝1→𝑝2→„→𝑝7是一段空载的出租车figure9（b）所示，由于𝑝1,𝑝2之间的距离超过了阈值δ，继续到下一点，并且把𝑝2标记为枢纽点，继续计算发现，dist(𝑝2,𝑝3δ,dist(𝑝2𝑝4δ,但是𝑝2,𝑝5之则这三个点形成了一个小的集群，代表一个可能的候选停车地点。然后，我们把点p3当做枢纽点，并继续这个过程，检查后面的点。最后，如figure9（D）所示，我们发现(𝑝2,𝑝3,𝑝4,𝑝5,𝑝6)是一个候选的停车地点，因为这个集群无法继续拓展了。上述算法的伪代码入Algorithm1所示.空间-时间特点1）MBR，figure10(A),B))可以看出，MBR网边界所在的区域栅格（Rr）GPS在的区域栅格（R）的面2)figure10（C）所示3）中心距离，R中心点与路网中心点的距离4)停车5)停车地铁站、院、购物中心附近（如figure10C）。我们用倒文档频度法POI<1,2𝑘>，𝑖是第itf-idf=

‖*𝑃∈ 其中ni是属于第i种类的POI的数量，N是在候选停车地点附近的POI总数量。Idf值是用拥有第i个POI种类的停车地点的数量除以候选点的总数协作特征对于一个真正的停车地点，通常是一直都有许多在此处等待载客。因此我们用过去7天候选点50米范围内的数据作为协作数据来加强OPTICS图11所示，左边的图形显示了西站附近所有的候选停车地点，右边的图是经过过 实际上，我们假设在时间区间,tt+∆t-内，概率都是稳定的，其中∆t是固定的一个𝐼𝑘=,(𝑘−1)𝜏,𝑘𝜏-,𝑘=1,2,…, 们重新计算属于区间[t,t+∆t]的相关区间，然后用重新计算的区间计算出的静态数据 𝑠≠ { 𝑟≠

来对路段分类，这些特征是由路的结构和POI数据得到的。在这个集合中展开线下的静态计算。假设r波浪线是路段r所在的路，R波浪线是集群的集合，#k(C;r波浪线)是在每一天的某个时刻，出租车空载经过这个路段的次数，那么t，r假设#(𝐶→𝑂;𝑟)是在路段 接乘客次数，那么其中𝑑𝑚𝑎𝑥是行程经过的最长距离对于每个停车地点的，我们都有一组与之对应的轨迹，但是到达时间和离开时从停车地点P开始的行程的数目。那么在到达P时，等待𝑇𝑝时间的概率可以由下面的公在出租车推荐系统方面，我们首先根据出租车所在的位置生成一个队列，然后一个拥有最小Pr̅S̅̅R̅R。然后，根据时间队列计算Pr(SR)和条件期望E,T|S-,E,|S-,E,𝑇|S-。最后，通过如下三个策略对所有的候选停车地点进行排序，然后实时推荐给前k的停车地点。其中的一些阈值(𝑃𝜃,𝜃,𝐹𝜃)可以通过进一步对数Topkmax*E,|S-E,T+𝑇|S-Pr(S)>𝑃𝜃,+.这个策略中，候选停车地点的Pr(SR)值必须大于阈值θkTopkmin*E,T|S- Pr(S)>𝑃𝜃, 𝜃+k短Topkmax*Pr(S)E,|S-E,T+𝑇|S->𝐹𝜃+.这个策略找出的停车地点，司路网：我们用市路网对我们的方法进行验证，包含106579个路点和141380个路轨迹：这部分数据集包括12000辆出租车在110天以内的GPS轨迹数据，总里程超过200,000,000公里总点数达到5.77亿个经过分割后的行程数达到20,000,000个，其中46%的数据是载客时的数据，53%是空载的数据。我们随机选取了70天的数据构建我们的系统，并且用余下的40天数据对系统进行评估。我们首先进试的是候选停车地点过滤器的效率，也就是我们的系统能否分辨交1000系统准确率达到了91%。，我们统计出了超过70个停车地点，都分布在市城区。然后我们用这些标注前往的停车地点。我们用三个策略对算法的性能进试，还设计了两个用来测试个标准来这些方法的性能：采用率是租车按照推荐系统的推荐行动的比率。在第k个位置的规范化衡量搜索引擎质量指标(nDCGk)。n𝐶𝑘 𝐶𝑘= 应的路径。假设(𝑅∗,𝑃∗)是实际选择的路线以及在载到下一位乘客之前的乘 3T∗− 通过对高收入出租车的行为和乘客的流动模式进行分析，我们构建了一个针对大的出租车GPS轨迹数据对我们的方法进行了验证。结果证明我们的方法可以高效低为出租车提供收益较高的乘车地点。通过对和乘客的移动研究，我们的系统在某种M.Ankerst,M.M.Breunig,H.-P.Kriegel,andJ.Sander.Optics:Orderingpointstoidentifytheclusteringstructure.InSIGMOD1999,pages49–60.ACMPress,1999.L.Breiman.Baggingpredictors.Machinelearning,Y.Ge,H.Xiong,A.Tuzhilin,K.Xiao,M.Gruteser,andM.Pazzani.Anenergy-efficient mendersystem.InProc.KDD2010,pages899–908.K.J¨arvelinandJ.Kek¨al¨ainen.Cumulatedgain-basedevaluationofirtechniques.ACMTransactionsonInformationSystems(TOIS),20(4):422–446,2002.D.Lee,H.Wang,R.Cheu,andS.Teo.Taxidispatchsystembasedoncurrentdemandsandreal-timetrafficconditions.TransportationResearchRecord:JournaloftheTransportationResearchBoard,1882(-1):193–200,2004.B.Li,D.Zhang,L.Sun,C.Chen,S.Li,G.Qi,andQ.Yang.Huntingorwaiting?discoveringpassenger-findingstrategiesfromalarge-scalereal-worldtaxidataset.InPervasiveComputingandCommunicationsWorkshops( Workshops),2011IEEEInternationalConferenceon,pages63–68,march2011.NewYorkCityTaxiandLimousineCommission.TaxiofTomorrowSurveyResults,FebS.Phithakkitnukoon,M.Veloso,C.Bento,A.Biderman,andC.Ratti.Taxi-awaremap:Identifyingandpredictingvacanttaxisinthecity.InProc.AMI2010,page86.J.Powell,Y.Huang,F.Bastani,andM.Ji.Towardsreducingtaxicabcruisingtimeusingspatio-temporalprofitabilitymaps.InProceedingsofthe12thInternationalSymposiumonAdvancesinSpatialandemporalDatabases,SSTD’11,2011.H.Wu,R.Luk,K.Wong,andK.Kwok.InterpretingTF-IDFtermeightsasmakingrelevancedecisions.ACMTransactionsonnformationSystems(TOIS),26(3):1–37,[11]K.Yamamoto,K.Uesugi,andT.Watanabe.Adaptiveroutingofruisingtaxisbyexchangeofpathways.InKnowledge-BasednligentInformationandEngineeringSystems,pages559–566.pringer,2010.J.Yuan,Y.Zheng,C.Zhang,W.Xie,X.Xie,G.Sun,andY.Huang.-drive:drivingdirectionsbasedontaxitrajectories.InProceedingsofhe18thSIGSPATIALInternationalConferenceonAdvancesineographicInformationSystems,GIS’10,pages99–108,NewYork,NY,USA,2010.ACM.J.Yuan,Y.Zheng,C.Zhang,X.Xie,andG.Sun.Aninteractive-votingbasedmapmatchingalgorithm.InProc.MDM2010,pages43–52.M.Ziegelmann.ConstrainedShortestPathsandRelatedProblems.PhDthesis,Universit¨atdesSaarlandes,2001.WheretoFindMyNextJingYuan1,2,YuZheng2,LiuhangZhang1,2,XingXie2andGuangzhongSun11UniversityofScienceandTechnologyofChina Research ,Wepresenta menderfortaxidriversandpeopleex-pectingtotakeataxi,usingtheknowledgeof1)passen-iorslearnedfromtheGPStrajectoriesoftaxicabs.First,thismenderprovidestaxidriverswithsomelocations(andtheroutestotheselocations),towardswhichtheyaremorelikelytopickuppassengersquickly(duringtheroutesorattheparkingplaces)andizetheprofit.Second,it mendspeoplewithsomelocations(withinawalkingdis-tance)wheretheycaneasilyfindvacanttaxis.Inourmethod,weproposeaparkingplacedetectionalgorithmandlearntheaboveknowledge(representedbyprobabilities)fromtra-jectories.Then,wefeedtheknowledgeintoaprobabilisticmodelwhichestimatestheprofitofaparkingplaceforapar-ticulardriverbasedonwhereandwhenthedriverrequestsfor mendation.Wevalidate menderingtrajectoriesgeneratedby12,000taxisin110 mender,parkingACMH.2.8DatabaseManagement:datamining,spatialdatabasesandGIS.Algorithms,Design,Experimentation,Taxicabsplayanimportantroleinpeople’scommutebe-tweenpublicandprivatetransports.Asignificantnumberworld.Accordingtoarecentsurveyaboutthetaxiserviceonehand,tofacilitatepeople’stravel,majorcities,likeNewYork,Tokyo,London,andBeijing,haveahugenumberoftaxistraversinginurbanareas.ThevacanttaxiscruisingonroadsnotonlywastegasandtimeofataxidriverbutalsoPermissiontomakedigitalorhardcopiesofallorpartofthisworkforalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarebearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,orrepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.p’11,September17–21,2011,Beijing,China.Copyright2011ACM978-1-4503-0630-

generateadditionaltrafficinacity.Thus,howtoimprovetheeffectivelyposesanurgentchallenge.Ontheotherhand,manypeoplefeelfrustratedandanxiouswhentheyareun-abletofindataxicabafterwaitingforalongtime.Toaddressthisissue,weproposea menderforbothtaxidriversandpassengersusingahugenumberofhistori-calGPStrajectoriesoftaxis.Specifically,ononehand,givens,wesuggestthetaxidriverwithalocation,towardswhichhe/sheismostlikelytopickupapassengerassoonaspos-edinFigure1A).This mendationhelpstoreducethecruising(withoutafare)timeofataxithussavesenergycon-sumptionandeasestheexhaustpollutionaswellashelpsthedriverstomakemoreprofit.Ontheotherhand,weprovidepeopleexpectingtotakeataxiwiththelocations(withinawalkingdistance)wheretheyaremostlikelytofindavacanttaxicab,asshowninFigure1B).Usingour mender,ataxiwillfindpassengersmorequicklyandpeoplewilltakeataximoreeasily;therefore,reducestheabove-mentionedproblemtosomeextent.PPPPPA) B) mendationRecently,inmanybigcities,likeNewYork,BeijingandSingapore,taxicabsareequippedwithGPSsensorsfordis-presentlocationstoadatacenterinacertainfrequency,e.g.,2minutes[12].Besidesageo-positionandtimestamp,theweightsensororbyconnectingataximeterwiththeembed-dedGPSdevice).ThereforealargenumberofsuchGPStrajectorieswithoccupancyinformationarebeinggeneratedeveryday.Intuitively,thesetaxitrajectoriescontaintwoas-pectsofknowledge.Oneispassengers’mobility,i.e.,whereandwhenpassengersgetonandoffataxi.Theotheristaxis’pick-upbehaviors.Forexample,wherethehigh-profittaxidriversusuallygoandhowtheycanfindpassengersquick-ly.Withthesetwoaspectsofknowledge,we 1locationswithhigh-probabilitytopickupapassengertothetaxidriverandsuggestlocationswhereapassengeriseasytofindavacanttaxi.Themajorcontributionofthisworkliesinthefollowingas-Weproposeanapproachforaccuraydetectingpark-ingplacesfromtheGPStrajectoriesofalargenumberoftaxis.Theseparkingplacesstandforthelocationswheretaxidriversusuallywaitforpassengerswiththeirtaxiparked.Fromtheseparkingplaces,wecancalculatetheprobabil-ityofpickingupapassengerifthedrivergoestowardsaparkingplace(includingthesituationthatthedriverpicksupapassengerwhencruising),hence,enablethe menderfortaxidrivers.Wedeviseaprobabilisticmodeltoformulatethetime-dependenttaxibehaviors(pick-up/drop-off/cruising/parking),bothonroadsegmentsandinparkingplaces,basedonwhich,webuildthe mendationsolutionfortaxidriver-sandpassengers.Wedeviseapartition-and-groupframe-worktolearnthecitywidestatisticalknowledgesoastoprovidejust-in-time mendationswithtimevaryinginformationlearnedfromthehistoricaldata.Weevaluateourmethodusingalargenumber(12,000taxisduring110days)ofhistoricalGPStrajectoriesgen-eratedbytaxicabs.Theevaluationresultsvalidatethatourmethodcaneffectivelysuggestthetaxidriverswithloca-tionstowardswhichthedrivercanmakemoreprofitandsavecruisingtime.DEFINITION1(ROADSEGMENT).Aroadsegmentrisadirectededgethatisassociatedwithadirectionsymbolr.e,roadlevelr.level,aswellasthetraveltimer.t.DEFINITION2 (ROUTE).ArouteRisasequenceofcon-nectedroadsegments,i.e.,R:r1→r2→···→rn,wherek1s=rk.e,(1≤k<n).ThestartpointandendpointofaroutecanberepresentedasR.s=r1.sandR.e=DEFINITION3(STATE).Weconsiderthreestatesforaworkingtaxi:occupied(O),cruising(C)andparking(P),ingandparkingstates.

frequentlywaitforpassengersasparkingplaces.Notetheparkingplaceheredoesnotmerelyimplyaparkinglotforprivatevehicles(whichisthetypicaldefinitionfor“parkingDEFINITION4(TRAJECTORYandTRIP).Ataxitrajec-toryisasequenceofGPSpointsloggedforaworkingtaxi,whereeachpointphasthefollowingfields:timestampp.t,latitudep.lat,longitudep.lon,locatedroadsegment(pro-videdbymapmatchingalgorithms[13])p.r,statep.s(TherawGPStrajectoryonlyindicateswhetherapointisoccu-piedornon-occupied).Ataxitripisasub-trajectorywhichhasasinglestate,eithercruising(needtobeinferred)oroc-cupied.RefertoFigure2foranexample.Notethatataxicouldgeneratemultipletripsbetweentwoparkingplaces.PParking P P Trip1 Trip2 Trip3 Trip4 Ataxi Figure2.TaxitrajectoryandtaxiDifferentfromotherpublictransportslikebusesorsubwayswhichfollowthefixedrouteseveryday,taxidriversplantheirownroutesoncetheydropoffapassenger.Thisisthemainreasonthatdifferentdriversgetdiscrepant es.Figuredays.AsshowninFigure3(a),theprofitofataxidrivercanbemeasuredbythefare(occupied)distanceperunitwork-ingtime,basedonwhich,wedividethetaxidriversinto3groups,thetop10%areregardedashigh-profitdrivers,thebottom10%areconsideredasthelow-profitdriversandtherestsaremediumpart.Thereisnodoubtthatatpeakhours,thetaxicabsareeasytofindpassengers.i.e.,thetaxisareofteninshortsupply.However,atoff-peakhours,thegapbetweenthehigh-profitdriversandthelow-profitdrivers esobvious.Figuretientbetweentheoccupieddistanceandthewholedistance)pertainingtothehigh/low-profittaxidriversaswellastheoveralloccupiedratiochangingduringaday.It’sclearthatfrom10amto3pm,thegapbetweenthehigh-profitdriversandlow-profitdriversismoresignificant.Thecriticalfactordeterminingtheprofitofataxidriverdependsontwofolds.Oneisthatthedrivershouldknowtheplaceswherehe/she Occupied(O) Ataxiisoccupiedbyapassenger.Cruising(C) Ataxiistravelingwithoutapassenger.Parking(P) Ataxiiswaitingforapassenger.Table1.ThestatesofaNotethatthe“parking”stateproposedinthispaperisthestatusthattaxidriverswaitsomewhereforbusiness,i.e.,

0

occupiedoccupied

timeofdayand/orqueueforawhilewiththeintentiontogetapassengeron-board.Thisstatusisfrequentlyfoundatairports,ho

(a)Distributionof (b)Occupiedratioduringashopcenters,etc.Wecalltheseplaceswherethe Figure3.Statisticsontheprofitdistributionandoccupied2r=r= KnowledgeofparkingKnowledgeofroadProbabilisticMap-ParkingParkingOfflineStatistic cruisingdistance/unittime210 faredistance/unittimeFigure4.Densityscatterofcruisingdistance/unittimew.r.t.canpickuppassengersquicklygivenaparticulartimeofday.Theotheristhelengthofthetypicaltripsthatoriginatefromcentersandhosallgeneratedemandfortaxiservice.Aprofessionaltaxidriverusuallyknowswhencertainplanesandtrainsarrive,whenthemovieisoveratalocaltheaterevenwhattimeshiftschangeatcertain

Figure5.SystemTypically,foranexperiencedlocaldriver,insteadofrandomtopickupnewpassengersafterhe/shedropsoffapassen-ger.Figure4presentsaninformativedensityscatteroftheisonly0.0874accordingtotheplotteddata.Thecolorindi-catesthedensityofapoint.Thisfigureshowsusthatcruisingmoredoesnotmeanearningmore.Instead,waitingatsomerightplacesmaybringmorechancetopickupapassenger.Asshowninthefigure,quiteafewdriverscruisemorethanthemajority(thepointsontheupperleftcornerofthehotkernel),however,theirprofitislower.Therightbottomparts(ofthehotkernel)arethedriverswhoearnmorebutcruiselessthanthemajority.Wealsoconductasurveyamongmorethan10localtaxidrivers.Accordingtotheiranswers,aftertheydropoffapassenger,8ofthemoftenhaveaninten-tionallynearbydestination(theparkingplacewedefined)togo,especiallyatoff-peakhours.Basedontheirexperience,ratherthanwastinggaswhenrandomcruising,theyprefertowaitataparkingplacewithmorechancetogetapassenger.TheframeworkisillustratedinFigure5.Wedevelopanap-proachtodetecttheparkingplacesfromGPStrajectoriesandsegmenttheGPStrajectoriesaccordingtoDefinition4,thenmap-matchtheGPStrajectoriestoroadnetworksusingtheIVMMalgorithm[13],whichoutperformsotherapproach-esforlow-sampling-rateGPStrajectories.Later,weutilizethedetectedparkingplacesandthemappedtrajectoriestolearnthetime-dependenttaxibehaviors.Theseprocessesareperformedofflineandwillberepeatedonlywhenthetrajec-sults,weformulateaprobabilisticmodeltointegratethetaxibehaviorsoneachroadsegmentandparkingplaceaswellasthemobilitypatternsofpassengers.Basedonthismod-el,weperformreal-time mendationstoizetheprofitofataxidriver,andthepossibilitytogetavacanttaxiforpeoplerespectively,giventhelocationandtimeofataxi

MODEL Thetaxi menderaimstoprovidethetaxidriverswiththebestparkingplacesandtheroutestotheseparkingplaces.Buthowtodefinea“good”parkingplace?AfterataxidropsoffapassengerattimeT0,whatthedriverhopesistofindanewpassengerassoonaspossible.Itwouldbebestthatthenexttripisaslongaspossible,thusthedrivercanearnmoremoneyfromthenexttrip.Soagoodparkingplaceshouldbringahighprobabilitytogetapassenger,ashortwaitingtimeandalongdistanceofthenexttrip.AssumePisacertainparkingplaceandR:r1→r2...→rnisaroutetoP.WesaythedrivertakesactionΛRPifhe/shedrivesalongRuntilfindinganewpassengerandwaitsatPforatmosttmaxtimeifhe/shedoesnotpickupapassengeralongR.Inthissubsection,weanswerthefollowingquestions:Howlikelywillthedriverpickupapassengerifhe/shetakestheactionΛRP?IfthedrivertakesactionΛRPandsucceedsinfindinganewpassenger,whatistheexpecteddurationfromT0tothebeginningofthenexttrip?IfthedrivertakesactionΛRPandsucceedsinfindinganewpassenger,howlongistheexpecteddistance/traveltimeofthenexttrip?p2(1-r2Pr(W)(1-Figure6. mendation3TheProbabilityofPickinguptheNextLetSbetheeventthatthedriversucceedsinpickingupthenextpassengerifhe/shetakestheactionΛRPandSbetheoppositesituation(failstogetthenextpassenger).Thenwe

S whereSifori=1,2,...,nistheeventthatthedriver

timeofday

timeofdayE[Tupapassengeratroadsegmentri,andn1istheeventthedriverpicksupapassengerattheparkingplace.NotethatbothSandSiarewithrespecttothecurrenttimeT0.

Figure7.Pr(S)andE[T|S]changingoverLetrandomvariableTbethedurationfromcurrenttimeLetti rj.t,i.e.,thetraveltimefromthestart tothebeginningofthenexttrip,giventhatthetaxitori.DenotetheprobabilitythatacruisingtaxipicksupapassengeratroadsegmentriandattimeT0+tibypi=Pr(CO|ri,T0+

takestheactionΛRP.ThenTisasummationoftworandomvariables:thecruisingtimealongR,denotedasTRandthewaitingtimeatP,termedasTP,i.e.,T=TR+TP

NotethatTRandTParenotindependent.betheprobabilitythatataxisucceedsinpickingupapas-sengeratparkingplacePandwaitingtimeTP∈(0,tmax]ifthedriverreachesPatT0+tn.Then

TP=0, TR= ifTP>Theprobabilitymassfunctionisgiven

i=

Pr(TR=Pr(S)

j

(1−j i=2,3,..., =Pr(TR=ti,S)/n ⎩p∗=1nNowtheanswerofquestion1is

⎨Pr(Si)/ i=1,2,...,n−=⎩Pr(Sn)+n1) i=thustheconditionalexpectationofTRn

Pr(S)=1−Pr(S)=1− n=1−(1− (1−j

1

tiPr(TR=n = tPr(S)+t ).S SPr(

Thefactorn(1−p)inEquation5istheprobability LetWbetheeventthatthedriverwaitsatP,we thedriverfailstofindapassengeralongR.WedenotethiseventbySR.NotetheroutefromthecurrentpositionofthedrivertoPisnotunique.ShouldwesuggestthedriverwiththeroutethathastheminimumPr(SR)?It’sobviouslyab-surdsincethedrivercantraversealltheroadnetworkinthat

Pr(W) (1−j Tolearnthedistribution,webreaktheinterval(0,tmax]t⎨mbuckets.Specifically,t⎨case.Inpractice,wecanprovidethefastestrouteoraroutewiththeminimumPr(SR)conditionedbythatthe

=doesnotexceedathreshold.Thiscanbeimplementedbysimplegeneralizationoftheconstrainedshortestpathprob-lem[14].

t∗=j⎩t∗=(2j−1)t∗,j=1,2,...,j

Figure7(a)plotsthePr(S)ofthreenearbyparkingplacesaroundRearSea(abardistrictofBeijing).It’scleartheprobabilityfluctuateswithtimesignificantly.Atpeakhours(8-9am,5-6pm)theprobabilityisrelativelyhigherthanother

wheret∗istheaveragewaitingtimeforthej-thbucket.De-passengerandthewaitingtimeTPbelongstothej-thbuck-etby(t∗−t∗,t∗+timeintervalsforalltheseparking j=Pr(Pj−−−−−j−−−O|T>0,T+t ∗ ∗ Actually,recallEquation3,wehavep∗

j40 timeofdayE[TN

5321 timeofdayE[DN|S]/E[T+TN

forj=1,2,...,s.Thus,theconditionalexpecteddistanceofthenexttripisssE[DN|S]1iqi⎞=1s⎝j.Theconditional⎧⎨(1−Pr(W)),j=

NotethattheconditionalexpectedtraveltimeofthenexttripE[TN|S]iscomputedinexactlythesamewayasE[DN|S],thusweomitthedetail.Figure8plotstheexpecteddurationanddistanceofthenexttrip,w.r.t.timeofday.AswestatedjPr(Tp=t∗|S)j

⎪ ∗ 1≤j≤

above,thisareaisthebardistrict.Peoplemainlycometothisareaatnightandstayuntilthedawnofthenextday.Mostly,peoplewhogotothisplacelivenotsoclosetothisarea,thusboththeexpecteddurationanddistanceofthenexttripatTherefore,theconditionalexpectationofTP pre-dawnperiodishigherthanothertimeofE[T|S]

mj Then,theconditionalexpectationofT

E[E[TTRS]+E[TP tiPr(Si)+tn(1)+Pr(Wpj=∗.

Differentfromthetaxis,thepassengersdonotwanttowalktoolongforhailingataxi.Ifapassengerisclosetoatleastoneparkingplace,wesuggesthimtogotothenearestpark-ingplace.Otherwise,wesuggestthepassengerwiththemostpossibleroadsegmentsnearbyonwhichtheycanfindava-canttaxi.Thisismucheasierthanthetaxi tionproblem.LetPr(C;r|t)betheprobabilitythatthereisavacanttaxionroadsegmentrattimet,giventheger’scurrentposition,wesuggesttheroadsegmentswhichhavethehighestPr(C;r|t)amongareachableregionΩofthepassenger,i.e.,ingplaces(usingthesamequerypointasFigure7(a))aredepicted,changingovertimesmoothly.Notethatthepark-ingplaceP1hastheshortestexpectedduration,yethasthelowestPr(S),i.e.,itisnotsolikelytopickupapassenger.Distance/TravelTimeoftheNextTripDN,LetrandomvariableDNbethedistanceofthenexttripifthedrivertakestheactionΛRPconditionedbythatShappens.Letqbetheprobabilitythatthedistanceofthefirsttripsatisfiiesd<DN≤j,whenSihappens(notethetimeatthatmomentisT0+ti),i.e.,∀i=1,2,...,n+1iq=rd−d<DN≤d+d|Si,T0+ti). i⎨⎧d=⎨ p4 p4 δp2

r=argmaxPr(C; Later,wediscussindetailhowtolearntheneededprobabil-itiesproposedinthissection.Thissectiondetailstheprocessfordetectingparkingstatusfromanon-occupiedtripandaccordinglyfindingouttheparkingplacesintheurbanareaofacitybasedonacol-lectionoftaxitrajectories.Figure9demonstratestheparkingcandidatedetectionap-proach,givenanon-occupiedtripp→p→···→7We⎩d=(2j− j=1,2,...,wheredmaxistheumdistanceofthefirsttrip.Then,theconditionalprobabilitydistributionisgivenby:Pr(DN=jS Siqj

5Algorithm1: Input:AroadnetworkG,atrajectoryTr,distancethresholdδ,timethresholdτOutput:AsetofparkingcandidatesP={P1i←0,M←Tr,P←∅,P←whilei<(M−1)j←i+1;flagwhilej<Mdist←Distanceipifdist<δthenj←j+1;flagelseifj.t−p.>τandflag=trueforeachpointp∈Tr[i,j)andp∈/P

MBRAGPSpointA A)RealparkingAB)TrafficAC)Figure10.Parkingcandidates portanceofaPOItoaparkingplace.Specifically,foragivenparkingplace,weformulateaPOIvector,v1,...,vkwhereviisthetf-idfvalueofthei-thPOIcatego-ry,givenby:P.Add(p);/*builda ifi=j−1

v=ni× P.Add(MB(P));P← {P∈P|thei-thPOIcategory∈Pinto /*addtheminimumboundingboxofP whereniisthenumberofPOIsbelongingtotheinto i←i+ return

egory,NisthenumberofPOIslyingaroundtheparkingcandidate.Theidfitemiscalculatedusingthequotientofthenumberofparkingcandidatesdividedbythenumberofparkingcandidateswhichhavethei-thPOIcategory,firstkeeponcheckingthedistancebetweenthecurrentpointandthelatterpointuntilthedistanceissmallerthanathresh-old.AsdepictedinFigure9B),sincedist(p1,p2)exceedsthedistancethresholdδ,wemovenext,fixingp2asthe“piv-ot”pointandfindthatdist(p2,p3)<δ,dist(p2,p4)<δwhiledist(p2,p5)>δ(Figure9C).Ifthetimeintervalbe-tweenp2.tandp4.tislargerthanthetimethresholdτ,thethreepointsformasmallclusterrepresentapossibleparkingcandidate.Next,wefixp3asthepivotpointandkeepontheproceduretochecklatterpoints.Finally,asshowninFigure9D),wedetect(p2,p3,p4,p5,p6)asaparkingcandidatebe-causewecannotexpandthisgroupanyfurther,i.e.,allthepointsinthisgrouphaveadistancefartherthanδtop7.ThepseudocodeisprovidedinAlgorithm1.Essentially,thecandidatedetectionalgorithmfindsoutthelocationswheretheGPSpointsofataxiaredenselyclus-tered,withspatialandtemporalconstraints.However,apark-ingcandidatecouldsometimesbegeneratedbytaxisstuckinofarealparking.Toreducesuchfalseselections,wedesignasupervisedmodelforpickingoutthetrueparkingstatusfromthecandidatesets,usingthefollowingfeatures:ingRatio(MBR).AsshowninFigure10(A),B)),MBRisthearearatiobetweentheboundingboxoftheroadseg-ment(MBRr)andtheboundingboxoftheGPSpoints(MBRc)inthecandidateset.2)AverageDistance.Theaveragedistancedcbetweenpointsinthecandidatesetandtheirnearestroadsegments,asshowninFigure10C).3)CenterDistance.ThedistancebetweencenterpointinMBRcofthecandidatesetandtheroadsegments.4)Du-ration.Theparkingdurationofacandidate.5)LastSpeed.Thespeedofthelastpointleavingaparkingcandidate.POIfeature.Asweknow,aparkingplaceishighlyrel-evantwiththepointsofinterests(POI)aroundit,e.g.,subwayexits,theaters,shopmallswithin50meter-s,showninFigure10C).Weemploytheterm

andthentakingthelogarithmofthatCollaborativefeature.Forarealparkingplace,otherd