基于群智的出租车智能拼车方法

1.一种基于群智的出租车智能拼车方法，其特征在于，包括如下步骤：
步骤A：出租车客户端收集车辆行驶数据并上传服务器；
步骤B：服务器为各路段保存路况信息，并建立道路信息数据库；
步骤1：多个乘客客户端获取自身位置信息及目的地信息并上传服务器,服务器建立允许拼车乘客列表APL和希望拼车乘客列表WPL；
步骤2：服务器寻找拼车组合并匹配合适的用户；
步骤3：服务器向被匹配的出租车客户端及多个乘客客户端发送匹配消息；
步骤4：多个乘客客户端确认匹配结果；若确认，则进入步骤5；否则拼车失败，并将拼车失败后的用户信息根据类型分配至允许拼车乘客列表APL和希望拼车乘客列表WPL，准备重新进行用户匹配；
步骤5：乘客完成拼车过程后，出租车客户端上报服务器；
所述步骤A和步骤B持续发生；
所述步骤B包括如下步骤：
步骤B.1：服务器所记录的路况信息为各个路段上的行车平均时间值，服务器建立道路信息数据库，为每个路段建立保存一个平均行车时间值的列表，同时保存该路段的长度；
步骤B.2：服务器接收到出租车客户端上传的定位数据后，检查该出租车客户端上传的前一个定位数据，根据定位位置确定该出租车经过的路段，并根据时间数据计算通过该路段所用的时间；
步骤B.3：为步骤B.2中计算得到的时间值设立一个生存时间，并保存至该路段的平均行车时间值列表；计算平均行车时间值列表中所有生存时间没有到期的时间值的平均值，保存为该路段的行车平均时间值。
2.根据权利要求1所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤A包括如下步骤：
步骤A.1：服务器为每一个出租车司机分配一个ID，并记录于数据库中；
步骤A.2：出租车客户端以2秒为间隔不断通过GPS获取自身定位信息；
步骤A.3：出租车客户端内存储有本地地图，在地图上，以每个路口为中心制定一圆形范围，半径为50米；当出租车客户端检测到GPS定位位置进入该范围时，将当前的GPS定位信息以及当前时间上传至服务器。
3.根据权利要求1所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤1包括如下步骤：
步骤1.1：当乘客希望使用拼车服务时，使用乘客客户端向服务器申请拼车，并上传相关数据，包括：用户当前的GPS定位位置、用户的目的地位置、用户目前是否已在出租车上；
若乘客已经在车上，则同时上传出租车司机的客户端ID；
步骤1.2：服务器收到拼车请求后，保存该乘客的信息；若该乘客已经上车，将其加入允许拼车乘客列表APL；若该用户仍未上车，将其加入希望拼车乘客列表WPL。
4.根据权利要求1所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤2包括如下步骤：
步骤2.1：对于允许拼车乘客列表APL以及希望拼车乘客列表WPL，服务器以一定时间间隔Ts执行以下算法：
从APL中取出一个用户A，设该用户目前的位置为PA，目的地为DA，对于该用户，遍历WPL；
从WPL中取出用户B，其位置为PB，目的地为DB，进行以下判断:
根据步骤B中建立的道路信息数据库，计算得到PA到PB之间的行车距离以及行车时间，分别记为x1，tx1；计算得到PB到DA之间的行车距离以及行车时间，分别记为x2，tx2；计算得到DA到DB之间的行车距离以及行车时间，分别记为x3，tx3；计算得到PA到DA之间的行车距离以及行车时间，分别记为y1，ty1；计算得到PB到DB之间的行车距离以及行车时间，分别记为y2，ty2；
记路程增益为：
Gd＝y1+y2-(x1+x2+x3)
G′d＝y1-(x1+x3)
其中，Gd为行车路线为PA PB DA DB时的路程增益，G′d为行车路线为PA PB DB DA时的路程增益；
考虑行车时间的综合代价为：
其中，Gtd为行车路线为PA PB DA DB时的综合代价；G′td为行车路线为PA PB DB DA时的综合代价；
若条件 或 之一满足，则用户A与用户B的匹配成立；其中， 为常数
阈值；
具体为，若 成立，则拼车路线为PA PB DA DB，对用户A和用户B的建议拼车价格RA、RB为：
若 成立，则拼车路线为PA PB DB DA，对用户A和用户B的建议拼车价格R′A、R′B为：
对WPL中的所有用户遍历后，若满足条件的用户数量不止一个，则选择Gtd或G′td最小的用户与用户A进行匹配；
对APL中的所有乘客依此算法遍历后，该轮匹配结束，将所有已经匹配的乘客从WPL、APL中删除；下一轮匹配将在时间间隔Ts后进行。
5.根据权利要求4所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤3包括如下步骤：
步骤3.1：对于步骤2.1中匹配成功的用户，将相应的拼车线路及建议价格发送至出租车及乘客的客户端，即，若用户A和用户B成功匹配，则服务器向用户A和用户B的乘客客户端以及用户A所在出租车司机的出租车客户端发送建议路线以及对应的建议价格；
当Gtd当G′td6.根据权利要求1所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤4包括如下步骤：
步骤4.1：若多名乘客均同意该匹配结果，则通过乘客客户端向服务器发送同意拼车的消息；若有任何一名乘客不同意该匹配结果，则通过乘客客户端向服务器发送不同意拼车的消息，服务器此时会将多名乘客重新添加进允许拼车乘客列表APL和希望拼车乘客列表WPL。
7.根据权利要求1所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤5包括如下步骤：
步骤5.1：当出租车按照建议线路将两名乘客送抵目的地后，出租车司机通过出租车客户端向服务器上传本次拼车成功的消息。
8.根据权利要求4所述的基于群智的出租车智能拼车方法，其特征在于，所述步骤2.1中，根据步骤B中建立的道路信息数据库计算得到PA到PB之间的行车距离以及行车时间是通过将从PA到PB之间最短路径上的路段长度及路段行车平均时间分别进行累加得到的。

基于群智的出租车智能拼车方法\n技术领域\n[0001] 本发明涉及交通及通信技术领域，具体地，涉及一种基于群智的出租车智能拼车方法。\n背景技术\n[0002] 随着现代交通运输业的飞速发展，出租车行业已经成为人们日常生活的重要组成部分。但是，传统的出租车扬招方式存在乘客很难在高峰时段的街道或偏僻街道搭乘到出租车，耗费大量等待时间的问题。为了解决该问题，目前已经提出了很多基于拼车的出租车共享系统。\n[0003] 经过对现有技术文献的检索发现，雅典大学的Petros Lalos等人于2009年在Computation World：Future Computing，Service Computation，Cognitive，Adaptive，Content，Patterns上发表的“A Framework for dynamic car and taxi pools with the use of Positioning Systems”中提出了基于定位位置的出租车共享系统；台湾清华大学的Po-Yu Chen等人于2010年在IEEE72nd Vehicular Technology Conference Fall(VTC2010-Fall)上发表的“A Fuel-Saving and Pollution-Reducing Dynamic Taxi-Sharing Protocol in VANETs”中提出了基于智能交通系统的出租车共享系统；波尔图大学的Pedro M.d’Orey等人于2012年在15th International IEEE Conference on Intelligent Transportation Systems上发表的“Empirical Evaluation of a Dynamic and Distributed Taxi-Sharing System”中提出了考虑出租车乘客实际距离的出租车拼车系统。\n[0004] 然而，大部分现有的出租车拼车系统大多具有以下缺点：拼车算法是基于出租车与乘客之间的距离的，从而无法考虑因交通拥堵造成的车辆到达时间延长的问题。一般仅允许出发点及目的地相近的乘客拼车，从而拼车机会很小。以上问题损害了拼车系统的实用性，限制了其应用范围。\n发明内容\n[0005] 针对现有技术中的缺陷，本发明的目的是提供一种基于群智的出租车智能拼车方法，通过使用出租车司机所持智能手机上安装的客户端，采集路况信息；乘客可以使用其智能手机向服务器发出出租车拼车申请，由服务器根据采集到的路况信息对乘客进行匹配，给出建议线路以及建议价格，从而有效缩短乘客等待时间及打车费用，同时延长出租车有效载客路程。\n[0006] 本发明是通过以下技术方案实现的。\n[0007] 一种基于群智的出租车智能拼车方法，包括如下步骤：\n[0008] 步骤A：出租车客户端收集车辆行驶数据并上传服务器；\n[0009] 步骤B：服务器为各路段保存路况信息，并建立道路信息数据库；\n[0010] 步骤1：多个乘客客户端获取自身位置信息及目的地信息并上传服务器，服务器建立允许拼车乘客列表APL和希望拼车乘客列表WPL；\n[0011] 步骤2：服务器寻找拼车组合并匹配合适的用户；\n[0012] 步骤3：服务器向被匹配的出租车客户端及多个乘客客户端发送匹配消息；\n[0013] 步骤4：多个乘客客户端确认匹配结果；若确认，则进入步骤5；否则拼车失败，并将拼车失败后的用户信息根据类型分配至允许拼车乘客列表APL和希望拼车乘客列表WPL，准备重新进行用户匹配；\n[0014] 步骤5：乘客完成拼车过程后，出租车客户端上报服务器；\n[0015] 所述步骤A和步骤B持续发生。\n[0016] 优选地，所述步骤A包括如下步骤：\n[0017] 步骤A.1：服务器为每一个出租车司机分配一个ID，并记录于数据库中；\n[0018] 步骤A.2：出租车客户端以2秒为间隔不断通过GPS获取自身定位信息；\n[0019] 步骤A.3：出租车客户端内存储有本地地图，在地图上，以每个路口为中心制定一圆形范围，半径为50米；当出租车客户端检测到GPS定位位置进入该范围时，将当前的GPS定位信息以及当前时间上传至服务器。\n[0020] 优选地，所述步骤B包括如下步骤：\n[0021] 步骤B.1：服务器所记录的路况信息为各个路段上的行车平均时间值，服务器建立道路信息数据库，为每个路段建立保存一个平均行车时间值的列表，同时保存该路段的长度；\n[0022] 步骤B.2：服务器接收到出租车客户端上传的定位数据后，检查该出租车客户端上传的前一个定位数据，根据定位位置确定该出租车经过的路段，并根据时间数据计算通过该路段所用的时间；\n[0023] 步骤B.3：为步骤B.2中计算得到的时间值设立一个生存时间，并保存至该路段的平均行车时间值列表；计算平均行车时间值列表中所有生存时间没有到期的时间值的平均值，保存为该路段的行车平均时间值。\n[0024] 优选地，所述步骤1包括如下步骤：\n[0025] 步骤1.1：当乘客希望使用拼车服务时，使用乘客客户端向服务器申请拼车，并上传相关数据，包括：用户当前的GPS定位位置、用户的目的地位置、用户目前是否已在出租车上；若乘客已经在车上，则同时上传出租车司机的客户端ID；\n[0026] 步骤1.2：服务器收到拼车请求后，保存该乘客的信息；若该乘客已经上车，将其加入允许拼车乘客列表APL；若该用户仍未上车，将其加入希望拼车乘客列表WPL。\n[0027] 优选地，所述步骤2包括如下步骤：\n[0028] 步骤2.1：对于允许拼车乘客列表APL以及希望拼车乘客列表WPL，服务器以一定时间间隔Ts执行以下算法：\n[0029] 从APL中取出一个用户A，设该用户目前的位置为PA，目的地为DA，对于该用户，遍历WPL；从WPL中取出用户B，其位置为PB，目的地为DB，进行以下判断：\n[0030] 根据步骤B中建立的道路信息数据库，计算得到PA到PB之间的行车距离以及行车时间，分别记为x1，tx1；计算得到PB到DA之间的行车距离以及行车时间，分别记为x2，tx2；计算得到DA到DB之间的行车距离以及行车时间，分别记为x3，tx3；计算得到PA到DA之间的行车距离以及行车时间，分别记为y1，ty1；计算得到PB到DB之间的行车距离以及行车时间，分别记为y2，ty2；\n[0031] 记路程增益为：\n[0032] Gd＝y1+y2-(x1+x2+x3)\n[0033] G′d＝y1-(x1+x3)\n[0034] 其中，Gd为行车路线为PA PB DA DB时的路程增益，G′d为行车路线为PA PB DB DA时的路程增益；\n[0035] 考虑行车时间的综合代价为：\n[0036]\n[0037]\n[0038] 其中，Gtd为行车路线为PA PB DA DB时的综合代价；G′td为行车路线为PA PB DB DA时的综合代价；\n[0039] 若条件 或 之一满足，则用户A与用户B的匹配成立；其中， 为常\n数阈值；\n[0040] 具体为，若 成立，则拼车路线为PA PB DA DB，对用户A与用户B的建议拼车价格RA、RB为：\n[0041]\n[0042] 若 成立，则拼车路线为PA PB DB DA，对用户A和用户B的建议拼车价格R′A、R′B为：\n[0043]\n[0044] 对W P L中的所有用户遍历后，若满足条件的用户数量不止一个，则选择Gtd或G′td最小的用户与用户A进行匹配；\n[0045] 对A P L中的所有乘客依此算法遍历后，该轮匹配结束，将所有已经匹配的乘客从W P L、A P L中删除；下一轮匹配将在时间间隔Ts后进行。\n[0046] 优选地，所述步骤3包括如下步骤：\n[0047] 步骤3.1：对于步骤2.1中匹配成功的用户，将相应的拼车线路及建议价格发送至出租车及乘客的客户端，即，若用户A和用户B成功匹配，则服务器向用户A和用户B的乘客客户端以及用户A所在出租车司机的出租车客户端发送建议路线以及对应的建议价格；\n[0048] 当Gtd＜G′td时，建议路线为PA PB DA DB，对应的用户A和用户B的建议价格分别为RA和RB；\n[0049] 当G′td＜Gtd时，建议路线为PA PB DB DA，对应的用户A和用户B的建议价格分别为R′A和R′B。\n[0050] 优选地，所述步骤4包括如下步骤：\n[0051] 步骤4.1：若多名乘客均同意该匹配结果，则通过乘客客户端向服务器发送同意拼车的消息；若有任何一名乘客不同意该匹配结果，则通过乘客客户端向服务器发送不同意拼车的消息，服务器此时会将多名乘客重新添加进允许拼车乘客列表APL和希望拼车乘客列表WPL。\n[0052] 优选地，所述步骤5包括如下步骤：\n[0053] 步骤5.1：当出租车按照建议线路将两名乘客送抵目的地后，出租车司机通过出租车客户端向服务器上传本次拼车成功的消息。\n[0054] 所述步骤2.1中，根据步骤B中建立的道路信息数据库计算得到PA到PB之间的行车距离以及行车时间是通过将从PA到PB之间最短路径上的路段长度及路段行车平均时间分别进行累加得到的。\n[0055] 在本发明中，步骤A和步骤B持续重复进行；当有乘客客户端开始向服务器发送自身信息时，开始执行步骤1至步骤5。\n[0056] 本发明提供的基于群智的出租车智能拼车系统，采用群智技术，通过出租车司机的客户端收集车辆位置等信息，从而由服务器统计得到各个路段的交通状况，实现系统对交通实时变化的动态适应；采用的算法允许出发点目的地非互相临近的乘客之间实现拼车，从而有效扩大用户的可拼车范围，提高用户的拼车成功几率。\n[0057] 与现有技术相比，本发明具有如下的有益效果：\n[0058] 本发明使用群智方法进行路况信息的数据采集，从而可以根据道路拥堵情况进行拼车匹配。本发明允许起点与终点均不重合的两名乘客进行拼车，同时保证乘客的车费得到节省。对于乘客，本发明能够有效缩短等待出租车的时间，同时减少车费消耗；对于出租车司机，本发明能够延长其单次运营中的载客总路程，提高其收益；\n[0059] 本发明可以在上车前后通过使用其手机客户端，向服务器发出要求拼车服务的申请。服务器会根据用户上传的资料，自动实现用户间的匹配，同时保障用户的打车费用费用获得节省。此外，系统还能够为乘客和司机给出建议路线和价格，进一步方便拼车的实现。\n使用本系统能够有效减少乘客搭乘出租车时的等待时间，减少打车费用，并延长出租车的有效载客路程，保障乘客和司机的双方利益。\n附图说明\n[0060] 通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显：\n[0061] 图1为本发明的步骤流程图；\n[0062] 图2为本发明的执行结构示意图；\n[0063] 图中：1为服务器，201为第一出租车客户端，202为第二出租车客户端，301为乘客A的乘客客户端，302为乘客B的乘客客户端。\n具体实施方式\n[0064] 下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的技术人员进一步理解本发明，但不以任何形式限制本发明。应当指出的是，对本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进。这些都属于本发明的保护范围。\n[0065] 请同时参阅图1和图2。\n[0066] 本实施例提供了一种基于群智的出租车智能拼车方法。\n[0067] 在本实施例中一共有三种用户角色。一是出租车司机，主要任务是在行车过程中上传车辆行驶信息，包括车辆GPS定位位置，到达路口的时间。当出租车上的乘客拼车匹配成功后，出租车司机的客户端会给出建议的接客、送客路线，以及对应于两名乘客的建议价格。最终送客结束后，司机客户端向服务器上报拼车结束的通知。二是允许拼车的乘客A。这种乘客已经坐在出租车上，且希望能够与其他乘客拼车。这类乘客可以随时使用客户端向服务器提出拼车申请，服务器匹配成功后会向该乘客发送拼车路线以及建议价格。若该乘客同意，则拼车成功，等待出租车接送与其拼车成功的另一乘客。三是希望拼车的乘客B。该乘客在发起拼车申请时还没有上车，服务器将为其寻找合适的允许拼车的乘客A与其匹配。\n匹配成功后，该乘客会收到拼车路线以及建议价格。若该乘客同意，则在原地等待乘客A所乘出租车即可。对于以上三种角色本系统提供两种客户端，即司机客户端以及乘客客户端。\n出租车司机使用前者，乘客A及乘客B统一使用后者。\n[0068] 本实施例允许出发地与目的地均不相同的乘客之间进行拼车。传统的拼车方法一般仅允许出发地相近、目的地相近的乘客进行拼车，应用范围小，乘客获得拼车的机会不多。为了提高拼车机会，本实施例扩大了乘客的可拼车范围，在保证节省乘客车费的前提下可以搜索到更多的可拼车用户，可以使出发点、目的地均不相同的乘客获得拼车机会。\n[0069] 本实施例采用了群智的方法采集路况信息。传统的出租车调度方法一般采用基于路程的调度方案，即利用导航算法，计算出租车与乘客之间、乘客与乘客之间的行车距离，根据路程为出租车找出最短的行车路线。这种方法没有考虑因交通拥堵造成的部分路段行车时间超长的情况。本实施例利用出租车司机携带的智能手机，采集车辆的位置信息，测量车辆在各个路段的平均行驶时间。服务器根据该时间得到出租车到乘客间的行驶时间，并使用该时间量替代传统的路程量，从而考虑了交通拥堵等因素，避免了因交通拥堵造成的用户等待时间超长的问题。\n[0070] 虽然出租车拼车可以减少乘客打车费用，但会不可避免地导致乘客的乘车时间延长。为了均衡乘客的车费节省量与额外的乘车时间量，我们在拼车匹配算法中考虑了费用与时间的折中关系，并使用阈值进行控制。当该阈值较小时，乘客的乘车时间优先缩短，减少拼车成功的几率；当该阈值较大时，乘客以更长乘车时间的代价获得更多的拼车机会，即有更多减少车费消耗。系统管理者能够通过调控该阈值实现乘客乘车时间与拼车机会的均衡。\n[0071] 本实施例同时可以在乘客匹配过程中为乘客选择车费最省、乘车时间最短的拼车路线。例如，若一辆出租车上已经坐有拼车乘客A和B，则司机面临先送乘客A到其目的地还是先送乘客B到其目的地的问题。本实施例提出的方法能够根据A、B乘客的上车地点以及路途拥堵情况，自动为司机选择出最优的送客顺序。\n[0072] 下面结合附图对本实施例做进一步描述。\n[0073] 如图1所示，本实施例是通过以下技术方案实现的，本实施例包括如下步骤：\n[0074] 步骤A：出租车客户端收集车辆行驶数据并上传服务器，该步骤在系统运行的全程不断持续；\n[0075] 步骤B：服务器为各路段保存路况信息，并建立道路信息数据库，该步骤在系统运行的全程不断持续；\n[0076] 步骤1：多个乘客客户端获取自身位置信息及目的地信息并上传服务器，服务器建立允许拼车乘客列表APL和希望拼车乘客列表WPL；\n[0077] 步骤2：服务器寻找拼车组合并匹配合适的用户；\n[0078] 步骤3：服务器向被匹配的出租车客户端及多个乘客客户端发送匹配消息；\n[0079] 步骤4：多个乘客客户端确认匹配结果；若确认，则进入步骤5；否则拼车失败，并将拼车失败后的用户信息根据类型分配至允许拼车乘客列表APL和希望拼车乘客列表WPL，准备重新进行用户匹配；\n[0080] 步骤5：乘客完成拼车过程后，出租车客户端上报服务器；\n[0081] 其中：\n[0082] 步骤A：系统运行前，服务器为每一个出租车司机分配一个ID，并记录于数据库中。\n出租车司机通过其客户端以ID登陆服务器，其后可以在路上正常行驶。出租车客户端以2秒为间隔不断通过全球定位系统(GPS)获取自身定位信息。出租车客户内存储有本地地图。在地图上，以每个路口为中心制定一圆形范围，半径为50米。当出租车检测到GPS定位位置进入该范围时，将当前的GPS定位信息以及当前时间上传至服务器。该过程在系统运行的过程中是全程持续的。\n[0083] 步骤B：服务器建立道路信息数据库，为每个路段保存行车平均时间值以及该路段的长度，同时建立一个平均行车时间值的列表。服务器接收到出租车客户端上传的定位数据后，检查该客户端上传的前一个定位数据，根据定位位置确定该出租车经过的路段，并根据时间数据计算通过该出租车经过该路段所用的时间。此外，为此时间值设立一个生存时间，并保存至该路段的平均行车时间值列表。计算列表中所有生存时间没有到期的时间值的平均值，保存为该路段的行车平均时间值。该过程在系统运行的过程中是全程持续的。\n[0084] 步骤1：当乘客希望使用拼车服务时，可以使用手机客户端向服务器申请拼车，并上传相关数据，具体包括：用户当前的GPS定位位置、用户的目的地位置、用户目前是否已在出租车上。若乘客已经在车上，则同时上传出租车司机的ID。其中，GPS定位位置由客户端自动检测获得，目的地位置、目前是否已在出租车上、车司机的ID由乘客自己选择填写。车司机的ID由乘客询问司机得到。服务器收到拼车请求后，保存该乘客的信息。若该乘客已经上车，将其加入允许拼车乘客列表(APL)；若该用户仍未上车，将其加入希望拼车乘客列表(WPL)。对于新添加的乘客，首先置于列表末端。\n[0085] 步骤2：服务器端对于用户列表APL以及WPL，以一定时间间隔Ts执行以下算法：\n[0086] 从APL中取出一个用户A，设该用户目前的位置为PA，目的地为DA。对于该用户，遍历WPL。例如，从WPL中取出用户B，其位置为PB，目的地为DB。进行以下判断：\n[0087] 根据步骤B中建立的道路信息数据库，计算得到PA到PB之间的行车距离以及行车时间(将从PA到PB之间最短路径上的路段长度及路段行车平均时间分别进行累加)，分别记为x1，tx1；计算得到PB到DA之间的行车距离以及行车时间，分别记为x2，tx2；计算得到DA到DB之间的行车距离以及行车时间，分别记为x3，tx3；计算得到PA到DA之间的行车距离以及行车时间，分别记为y1，ty1；计算得到PB到DB之间的行车距离以及行车时间，分别记为y2，ty2。\n[0088] 记路程增益为\n[0089] Gd＝y1+y2-(x1+x2+x3)\n[0090] G′d＝y1-(x1+x3)\n[0091] 考虑行车时间的综合代价为\n[0092]\n[0093]\n[0094] 若条件 或 之一满足，则乘客A与乘客B的匹配成立。其中， 为常\n数阈值。\n[0095] 具体地，若 成立，则拼车路线为PA PB DA DB，对乘客A、B的建议拼车价格RA、RB为\n[0096]\n[0097] 若 成立，则拼车路线为PA PB DB DA，对乘客A、B的建议拼车价格R′A、R′B为[0098]\n[0099] 对WPL中的所有用户遍历后，若满足条件的用户数量不止一个，则选择Gtd或Gtd最小的用户与乘客A进行匹配。\n[0100] 对APL中的所有乘客依此算法遍历后，该轮匹配结束，将所有已经匹配的乘客从WPL、APL中删除。下一轮匹配将在时间间隔Ts后进行。\n[0101] 注意，WPL与APL的遍历是从表头依次进行的，即排列在靠前位置的乘客有优先的匹配机会。\n[0102] 步骤3：对于步骤2.1中匹配成功的用户，将相应的拼车线路及建议价格发送至出租车及乘客的客户端。以在出租车上的乘客A及仍在等待的乘客B为例，若乘客A、B成功匹配，则服务器向乘客A、B的客户端以及乘客A所在出租车司机的客户端发送建议路线(若Gtd＜G′td，建议路线为PA PB DA DB，反之则为PA PB DB DA)以及对应的建议价格(若Gtd＜G′td，建议价格为RA、RB，反之则为R′A、R′B)。\n[0103] 步骤4：若两名乘客均同意步骤3中的匹配结果，则通过客户端向服务器发送同意拼车的消息。若有任何一名乘客不同意该匹配结果，则通过客户端向服务器发送不同意拼车的消息，服务器此时会将这两名乘客分别重新添加进APL、WPL。对于不同意匹配结果的乘客，添加进APL或WPL的末尾；对于同意匹配结果的乘客，若另一名乘客不同意匹配结果，则将其添加进APL或WPL的开头。若两名乘客均同意匹配结果，则执行下一步骤。\n[0104] 步骤5：出租车按照建议线路将两名乘客送抵目的地。其后，出租车司机通过其客户端向服务器上传本次拼车成功的消息。\n[0105] 如图2所示，在本系统中所有司机客户端在使用过程中会不断采集车辆的GPS定位信息，检测车辆是否已经到达路口，并将检测相关结果上传至服务器。已经乘坐在出租车上的乘客A可以通过其乘客客户端向服务器提出拼车申请。仍未搭乘出租车的乘客B也可以通过其手机客户端向服务器发起拼车申请。服务器接收到乘客的申请后，以一定时间间隔进行匹配。若乘客A与乘客B成功匹配，则服务器向两位乘客以及乘客A乘坐的出租车发送匹配成功的消息，同时包含建议路线以及建议价格。若两位乘客均同意本次匹配，则司机可遵照建议接客及送客次序将用户依次送至目的地。最后，司机客户端向服务器上传拼车成功的消息。\n[0106] 本实施例的环境参数为：\n[0107] 移动终端设备：三部Android智能手机，都是Nexus4，每部智能手机都配置有\n1.5GHz Snapdragon APQ8064CPU和2G RAM三部智能手机的操作系统都是Android Jelly Bean(4.2)。这三部智能手机使用的都是中国联通的WCDMA3G蜂窝网络，他们可以通过该网络接入因特网。三部智能手机中一部作为司机客户端，两部作为乘客客户端。\n[0108] 服务器：宏基4930G笔记本电脑，酷睿双核处理器，2G的内存，2G的主频。\n[0109] 本实施例包括如下具体步骤：\n[0110] 步骤A：服务器为出租车司机分配一个ID，并记录于数据库中。本例中，司机的ID＝\n001。出租车司机通过其客户端以ID＝001登陆服务器，其后在路上正常行驶。出租车客户端以2秒为间隔不断通过全球定位系统(GPS)获取自身定位信息。出租车客户内存储有本地地图。在地图上，以每个路口为中心制定一圆形范围，半径为50米。当出租车检测到GPS定位位置进入该范围时，将当前的GPS定位信息以及当前时间上传至服务器。例如，在12:00该车GPS定位位置处于路口N附近50米内。此时客户端将该车在12:00到达路口N的信息发送至服务器。该过程在系统运行的过程中是全程持续的。\n[0111] 步骤B：服务器建立道路信息数据库，为每个路段保存行车平均时间值以及该路段的长度，同时建立一个平均行车时间值的列表。服务器接收到出租车客户端上传的定位数据后，检查到该客户端上传的前一个定位数据为11:50经过路口M，而路口M与路口N同属路段P。由此，计算出该车辆通过路段P所需的时间为10分钟。该数据的生存时间设为1小时，即在一小时内该数据有效，并存在此期间内保存至路段P的平均行车时间值列表。同时，将该列表内所有有效数据进行平均。例如，列表内此时的数据为7分钟，8分钟，8分钟，10分钟，13分钟，则该路段的平均行车时间约为9分钟。服务器将该时间保存为路段P的平均行车时间。\n该过程在系统运行的过程中是全程持续的。\n[0112] 步骤1：假设乘客A已经坐上出租车，司机为Q。当其希望使用拼车服务时，使用手机客户端向服务器申请拼车，并上传相关数据，具体包括：用户当前的GPS定位位置、用户的目的地位置、用户已经上车的标识，以及出租车司机的ID。其中，GPS定位位置由客户端自动检测获得，目的地位置、目前是否已在出租车上、车司机的ID由乘客A自己选择填写。车司机的ID由乘客A询问司机Q得到。\n[0113] 假设乘客B仍未坐上出租车，希望能与别的乘客一起拼车，则使用手机客户端向服务器申请拼车，并上传相关数据，具体包括：用户当前的GPS定位位置、用户的目的地位置、用户尚未上车的标识。\n[0114] 服务器收到来自于乘客A、B的拼车请求后，保存乘客的信息。将乘客A加入允许拼车乘客列表(APL)；将乘客B加入希望拼车乘客列表(WPL)。首先将两位乘客分别置于列表末端。\n[0115] 步骤2：服务器端对于用户列表APL以及WPL，以时间间隔Ts＝30秒执行以下算法：\n[0116] 从APL中取出一个用户，以取出了用户A为例，设该用户目前的位置为PA，目的地为DA。对于用户A，遍历WPL。例如，从WPL中取出用户B，其位置为PB，目的地为DB。进行以下判断：\n[0117] 根据步骤B中建立的道路信息数据库，计算得到PA到PB之间的行车距离以及行车时间(将从PA到PB之间最短路径上的路段长度及路段行车平均时间分别进行累加)，分别为x1＝5公里，tx1＝4分钟；计算得到PB到DA之间的行车距离以及行车时间，分别为x2＝120公里，tx2＝110分钟；计算得到DA到DB之间的行车距离以及行车时间，分别为x3＝2公里，tx3＝3分钟；计算得到PA到DA之间的行车距离以及行车时间，分别为y1＝100公里，ty1＝90分钟；计算得到PB到DB之间的行车距离以及行车时间，分别为y2＝150公里，ty2＝120分钟。\n[0118] 路程增益为\n[0119] Gd＝y1+y2-(x1+x2+x3)＝100+150-(5+120+2)＝123\n[0120] G′d＝y1-(x1+x3)＝100-(5+2)＝93\n[0121] 考虑行车时间的综合代价为\n[0122]\n[0123]\n[0124] 设 则此时条件 及 均满足，乘客A与乘客B的匹配成立。由于\nGtd＜G′td，拼车路线为PA PB DA DB，即将乘客B接上车后，先将乘客A送达其目的地，再将乘客B送达其目的地。对乘客A、B的建议拼车价格(假设单价为1公里1元)RA、RB为\n[0125]\n[0126] 假设对WPL中的所有用户遍历后，所有满足条件的用户中，乘客B的Gtd仍最小，故选择乘客B作为乘客A的匹配对象。\n[0127] 对APL中的所有乘客依此算法遍历后，该轮匹配结束，将包含乘客A、B在内的所有已经匹配的乘客从WPL、APL中删除。下一轮匹配将在时间间隔Ts＝30秒后进行。\n[0128] 步骤3：服务器将拼车线路PA PB DA DB及建议价格RA、RB发送至出租车司机Q及乘客A、B的客户端。\n[0129] 步骤4：假设乘客A、B均同意步骤3中的匹配结果，则通过客户端向服务器发送同意拼车的消息。\n[0130] 步骤5：出租车按照建议线路将两名乘客送抵目的地。其后，出租车司机Q通过其客户端向服务器上传本次拼车成功的消息。\n[0131] 以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变形或修改，这并不影响本发明的实质内容。