CN110326311A - 一种用于提供运输服务的系统和方法 - Google Patents

Abstract

本申请的实施例提供了一种提供运输服务的系统和方法。所述方法可以包括通过通信接口接收区域内的运输任务。所述方法可以进一步包括由处理器将所述运输任务聚类成多个群组，以及由所述处理器搜索用于所述多个群组的运输能力。所述方法还可以包括通过所述通信接口将所述运输能力分配给每个群组。

Description

一种用于提供运输服务的系统和方法

技术领域

本申请涉及运输服务，尤其涉及提供运输服务的系统和方法。

背景技术

拼车成为了一种新兴的运输方式。通过拼车，允许同一路线的乘客共用一辆车可以提高车辆的使用。例如，拼车平台(例如，嘀嘀打车)可以指派车辆在路线上的不同位置接载乘客并按要求让所述乘客下车。然而，随着更多乘客请求运输服务，所述拼车平台可能必须生成多条路线并将多个车辆分配给所述路线。因此，有效地分配运输能力是很重要的。

本申请的实施例提供用于提供运输服务的系统和方法，以提高提供运输服务的效率。

发明内容

本申请的实施例提供了一种计算机可实施的提供运输服务的方法。所述方法可以包括通过通信接口接收区域内的运输任务。所述方法可以进一步包括由处理器将所述运输任务聚类成多个群组，以及由所述处理器搜索用于所述多个群组的运输能力。所述方法还可以包括通过所述通信接口将所述运输能力分配给每个群组。

本申请的实施例进一步提供了一种提供运输服务的系统。所述系统可以包括：通信接口，被配置为接收区域内的运输任务；存储器；以及耦合至所述通信接口和所述存储器的处理器。所述处理器可以配置为：将所述运输任务聚类成多个群组，搜索用于所述多个群组的运输能力，以及将所述运输能力分配给每个群组。

本申请的实施例进一步提供了一种存储一组指令的非暂时性计算机可读介质，当所述组指令由电子设备的至少一个处理器执行时，使所述电子设备执行提供运输服务的方法。所述方法可以包括接收区域内的运输任务，将所述运输任务聚类成多个群组，搜索用于所述多个群组的运输能力，以及将所述运输能力分配给每个群组。

应当理解的是，前面的一般描述和下面的详细描述都仅是示例性和说明性的，并不构成对本申请的限定。

附图说明

图1是根据本申请的实施例所示的提供运输服务的示例性系统的框图。

图2是根据本申请的实施例所示的分布在区域中的示例性运输任务的示意图。

图3是根据本申请的实施例所示的示例性任务群组的示意图。

图4是根据本申请的实施例所示的示例性有序群组的示意图。

图5是根据本申请的一些实施例所示的提供运输服务的示例性方法的流程图。

图6是根据本申请的实施例所示的用于将群组划分为两个子群组的示例性方法的流程图。

图7是根据本申请的实施例所示的用于将运输任务分配给各个车辆的示例性方法的流程图。

具体实施方式

本申请通过示例性实施例进行详细描述，这些示例性实施例将通过图示进行详细描述。任何可能的情况下，图中同一参考数字表示相同的部分。

根据本申请的实施例所示的系统和方法可以将运输任务分成多个群组并动态调整每个群组内运输能力的分布以提高运输效率。

图1是根据本申请的实施例所示的提供运输服务的示例性系统100的框图。

系统100可以是通用服务器或专用设备。在一些实施例中，如图1所示，系统100可以包括通信接口102、处理器104和存储器114。处理器104进一步可以包括多个功能模块，例如任务聚类单元106、群组排序单元108、车辆搜索单元110、车辆分配单元112等。这些模块(以及任何相应的子模块或子单元)可以是处理器104的功能硬件单元(例如，集成电路的部分)，这些硬件单元被设计与其他组件或程序的一部分一起使用。所述程序可以被存储在计算机可读介质上，当其被处理器104执行时，所述程序可以执行一个或多个功能。尽管图1示出的单元106-112全部在处理器104内，但可以预期的是，这些单元可以分布在多个处理器中，这些处理器彼此位置邻近或彼此远离。在一些实施例中，系统100可以在云中或在单独的计算机/服务器上实施。

通信接口102可以被配置为接收区域内的运输任务。所述运输任务可以由至少一个乘客120请求。通信接口102可以是提供数据通信连接的综合业务数字网络(ISDN)卡、电缆调制解调器、卫星调制解调器或提供数据通信连接的调制解调器。又例如，通信接口102可以是局域网(LAN)卡，该局域网卡向兼容局域网提供数据通信连接。无线链路也可以被通信接口102实施。在任何这样的实施中，通信接口102可以经由网络发送和接收电信号、电磁信号、或光信号，这些信号负载着代表各种类型的信息的数字数据流(未示出)。所述网络通常包括蜂窝通信网络、无线局域网(WLAN)、广域网(WAN)等。

至少一个乘客120可以向拼车平台(例如，嘀嘀在线平台)发送指示运输任务的任务信息的请求。在一些实施例中，所述任务信息可以包括所述运输任务的请求者身份(例如，乘客120)、行程的起点、行程的目的地、行程的出发时间等。

在一些实施例中，乘客120可以使用移动应用程序(例如，嘀嘀应用程序)在移动设备(例如，智能电话、平板电脑、智能手表等)上发出请求。所述移动应用程序可以调用所述移动设备的定位模块(例如，GPS模块)定位所述乘客，并且将所述乘客的当前位置设置为，例如，行程的起点，并将所请求的目的地作为目的地。乘客120还可以识别除所述当前位置之外的位置为起点。在一些实施例中，所述乘客还可以通过网站向拼车平台发送请求，指示任务信息。可以设想，所述任务信息还可以包括任何必要的信息，例如车辆的要求、该运输任务中的乘客数量等。

通信接口102可以进一步被配置为从至少一个运输服务提供者103(例如，私人汽车所有者、出租车司机、运输服务公司等)接收运输能力信息。所述运输能力信息可以包括例如驾驶员的身份、车辆的乘客容量、车辆型号、车辆的位置等。

所接收的运输任务和所述运输能力信息可以由处理器104进一步处理。例如，任务聚类单元106可以被配置为将运输任务聚类成多个群组。图2是根据本申请的实施例所示的分布在区域200中的示例性运输任务的示意图。

区域200可以是，例如六边形，并且所述运输任务可以分布在区域200内。如上所述，运输任务可以包括行程的起点、目的地和出发时间。运输任务是否分布在区域200内可以根据行程的起点、目的地和出发时间确定。

如图2所示，运输任务201-209和一些其他任务被确定分布在区域200内。任务聚类单元106可以根据包括乘客120的身份、行程的起点、行程的目的地、行程的出发时间的任务信息对所述运输任务进行聚类。也就是说，任务聚类单元106可以根据地理位置(例如，所述起点和所述目的地)和时间角度(例如，所述出发时间)聚类所述运输任务。可以设想，在聚类之前，任务聚类单元106还可以对所接收的运输任务进行过滤以移除异常任务。例如，可以过滤掉有太多乘客(例如，超过十名乘客)的运输任务。

可以将区域200映射到坐标系以使用坐标定位任务。在一些示例性实施例中，被聚类至一群组中的任务可以具有相同或相似的起点、目的地和出发时间。例如，任务201的起点为(0.35，7.3)，出发时间为上午6:50，任务203的起点为(-0.35，7.04)，出发时间为上午6:45，任务205的起点为(0.35，6.76)，出发时间为上午6:55，任务207的起点为(1.71，5.25)，出发时间为上午7:15，任务209的起点为(2.31，3.57)，出发时间为上午7:35。任务聚类单元106可以识别任务201、203和205的起点之间的距离均小于预设距离(例如，所述坐标系中的1个单位)。运输任务的目的地的处理可以类似于所述起点的处理，这里省略描述。

任务聚类单元106可以进一步确定这些任务201、203和205的所述出发时间是否足够接近以聚类到同一群组中。例如，任务聚类单元106可以在任务201、203和205中确定最早出发时间是上午6:45，最晚出发时间是上午6:55，所述最早出发时间和所述最晚出发时间之间的时间差小于预设范围(例如，15分钟)。因此，任务聚类单元106可以将任务201、203和205聚类为第一群组。在图2中，任务207的起点是(1.7，5.3)，出发时间是上午7:30。任务207与所述第一群组中的任何任务之间的距离大于预设距离(例如，所述坐标系中的1个单位)，并且任务207与所述第一群组中的任何任务之间的所述时间差大于所述预设范围(例如，15分钟)。因此，任务聚类单元106可以将任务207排除在所述第一群组中。

任务207可以与具有相似起点、目的地和出发时间的其他任务一起聚类成一个群组。群组内任务的目的地可能相同，也可能不同。当所述目的地不相同时，同一群组内的任务仍然可以具有大致相同的方向。因此，这里将省略这些任务的示例性目的地。系统100可以为具有相同方向的任务设计路线，以在必要时让乘客下车。可以设想，目的地越类似，所述系统可提供运输服务的效率越高。

在一些实施例中，任务聚类单元106还可以使用聚类模型聚类运输任务。所述聚类模型可以分析运输任务的特征元素(例如，起点、目的地和出发时间)，并将相似的运输任务聚类成群组。所述聚类模型可以具有用于聚类运输任务的颗粒，所述颗粒可以包括，例如任务的起点(或目的地)之间的预设距离、任务之间的时间差的预设范围等。如果所述颗粒太细，则较少任务可以聚类到一个群组中，如果颗粒太粗糙，则群组中可能包括太多任务。因此，可以调整所述颗粒以确保可以将适当数量的任务聚类到一个群组中。任务聚类单元106所用的特征元素不受上述例子的限制。

图3是根据本申请的实施例所示的示例性任务群组的示意图。如图3所示，任务201-205被聚类至群组301、任务207和一些其他任务被聚类至群组307、任务209被单独聚类至群组309、其他任务被聚类至群组303和305。

任务聚类单元106可以进一步基于群组中的运输任务的出发时间确定每个群组的会合时间，其中每个群组的会合时间是各自群组中的运输任务的平均出发时间。例如，群组301的会合时间可以是出发时间上午6:50、6:45、6:55的平均出发时间。也就是说，群组301的会合时间可以确定为上午6:50。会合时间将是车辆接载所述群组中乘客的时间。

类似地，任务聚类单元106可以基于每个群组中的运输任务的起点和目的地来确定会合位置和到达位置。在一些实施例中，各个群组的会合位置可以是各个群组中的运输任务的起点的平均位置。例如，群组301中的任务201-205的起点是(0.35，7.3)、(-0.35，7.04)和(0.35，6.76)，因此平均位置可以是(0.11，7.03)。在一些实施例中，可以基于所述平均位置根据地图信息进一步调整所述会合位置。例如，可以将所述会合位置确定为所述平均位置附近的十字路口。所述到达位置可以是最后一位乘客的目的地，也可以是该群组中目的地的平均位置。

任务聚类单元106可以进一步估计每个群组的结束时间。群组的结束时间可以由导航服务(例如，嘀嘀打车)生成。例如，可以将所述群组的会合位置、到达位置和会合时间发送给所述导航服务提供者以设计所述群组的行程以及行程的估计结束时间。可以设想，所述导航服务可以是由系统100或与系统100分离的系统提供的功能。

因此，任务聚类单元106可以将运输任务聚类成多个群组，并生成所述群组的运输服务的会合位置、到达位置、会合时间和结束时间。

群组排序单元108可以被配置为根据与各个群组相关联的会合时间对所述多个群组进行排序。在一些实施例中，通常，对于目标群组，可以将具有早于所述目标群组的会合时间的第一群组确定为前群组可以将具有晚于所述目标群组的会合时间的第二群组确定为后群组。但是，群组可能没有前群组，在这种情况下，所述群组可以确定为父群组。

运输服务提供者只有在当前群组的当前任务已完成，才可以接受下一群组的另一任务。因此，可以将所述下一群组的会合时间设置在当前群组的结束时间之后。在一些实施例中，所述下一群组的会合时间与所述当前群组的结束时间之间的时间差可以与所述下一群组的会合位置与所述当前群组的到达位置之间的距离相关联。例如，所述导航服务可以估计运输服务提供者在两群组之间行进上述距离所需时间。当所述估计时间小于所述时间差时，可以将所述下一群组确定为后群组。可以将下一群组的会合位置与当前群组的到达位置之间的距离确定为所述当前群组与所述下一群组之间的距离。

在一些实施例中，对于目标群组，不止一个候选群组可以满足上述条件。群组排序单元108可以使用贪心算法选择一个所述候选群组作为后群组。所述贪心算法总能选择能提供明显优势的后群组。例如，所述贪心算法可以选择与所述目标群组具有最短距离的后群组。

图4是根据本申请的实施例所示的示例性有序群组的示意图。如图4所示，群组402-414中的每一群组与会合位置(例如，O1、O2等)、到达时间(例如，D1、D2等)、会合时间(例如，7:00、8:00等)和乘客数量(例如，20、10等)相关联。如上所述，这些群组已经由群组排序单元108排序。

在一些实施例中，当车辆完成当前群组的拼车服务时，所述车辆可以继续向后群组提供所述拼车服务。然而，所述后群组可能需要比所述当前群组可用运输能力更多的运输能力用于运输任务。在这种情况下，群组排序单元108可以进一步确定需要从第一群组调动到第二群组的能力。例如，如图4所示，群组排序单元108可以确定在搜索拼车服务的十名乘客中，只有五名乘客的运输能力可以从群组404调动到群组406。也就是说，五个乘客无法通过可用的运输能力得到适当的服务。

然后，当调动能力小于原始群组406所需的运输能力时，群组排序单元108可以将群组406划分为第一子群组406′和第二子群组408。群组排序单元108可以进一步将所述调动能力(例如，五个乘客)分配给第一子群组406′，并将第二子群组408指定为父群组。系统100可以将新的运输能力分配给父群组。例如，可以将新的运输能力分配给群组408，其可以用于满足群组408中的五个人的对运输能力需求。关于向群组408分配新能力的更多细节可以参考以下描述。

在一些实施例中，若当前群组具有足够的运输能力用于其后群组时，在完成所述当前群组的运输任务之后，所述运输能力将被分配给所述后群组。例如，群组404需要15个乘客的运输能力，群组410需要三个乘客的运输能力，因此所述三个乘客的运输能力将被分配给群组410。此外，可以将12名乘客的额外运输能力分配给另一群组(例如，群组412)。

在一些实施例中，若当前群组没有足够的运输能力用于其后群组时，所述后群组可以从另一个前群组获得更多的运输能力。例如，群组406可以提供5个乘客的运输能力，但群组414需要10个乘客的运输能力。因此，群组414可以从在群组408之前的另一群组获取其他5个乘客的运输能力。也就是说，可以从一个以上的前群组为一个后群组分配能力。

车辆搜索单元110可以被配置为所述搜索运输能力。通常，运输服务提供者可以提供的运输能力与所述车辆相关联。例如，由于驾驶员必须占用一个座位，因此五乘客车辆最多可以为四名乘客提供服务。大多数车辆可以为2-6名乘客提供服务。由于父群组没有前群组而位于链的顶部，可以在拼车服务中对父群组执行车辆搜索。例如，车辆搜索单元110可以为父群组402和408中的每个群组搜索可用车辆。如上所述，服务提供者130可以向系统100发送运输能力信息，指示他/她的车辆的运输能力和位置。基于所述获取的运输能力信息，可以通过车辆搜索单元110找到可用车辆。

例如，参考图4，作为父群组的群组402包括20名搜索拼车服务的乘客，并且群组402附近邻域中的至少一辆车可以被定位用于提供运输能力。如果发现运输能力不够，可以扩大所述邻域。

车辆分配单元112可以将所述运输能力分配给每个群组。在一些实施例中，车辆分配单元112可以根据每个车辆的运输能力和所述群组中的运输任务生成车辆群组合，并确定所述群组的车辆群组合。例如，群组402包括20名乘客，所述车辆群组合可以是四辆3乘客车辆和两辆4乘客车辆。也就是说，可以向群组402提供六辆车的群组合以接载20名乘客。可以设想，当可用车辆共同提供大于所需能力的运输能力时，可以产生一种以上的车辆群组合。

为了提高所述拼车服务的效率，一辆车中对于每个乘客的运输任务可以具有相同或相似的起点、目的地、出发时间和到达时间。也就是说，分配给一个车辆的运输任务可以相同或相似，以提高效率。

因此，在一些实施例中，车辆分配单元112可以进一步确定所述群组中的运输任务的相似性矩阵(例如，父群组402)，基于所述相似度矩阵确定特征元素，根据所述特征元素将所述运输任务聚类成预设数量的类，并基于所述多个类将所述运输任务分配给至少一个车辆中的每个车辆。

例如，可以利用相似性模型生成所述运输任务的相似性矩阵。所述相似性模型可以比较，例如，运输任务的起点、目的地、出发时间、到达时间和其他特征元素以生成所述相似性矩阵。可选地，可以将所述相似性矩阵转换为拉普拉斯矩阵，以为每个运输任务生成特征元素。所述运输任务可以聚类成预设数量的类。所述预设数量可以是由车辆分配单元112确定的所述群组的车辆数量。用于聚类的方法可以是K均值方法或基于密度的聚类方法(例如，最大密度方法)。可以设想，所述用于聚类的方法不受上述示例性方法的限制。在分类之后，可以将运输任务(例如，乘客)分别分配给车辆。在一些实施例中，所述聚类过程可以对用户端隐藏。也就是说，当乘客正在查看他/她的车辆选择时，只有分配给他/她的车辆才能显示给所述乘客。

可以设想，车辆分配单元112可以产生一个以上的车辆群组合。也就是说，车辆的数量(即，预设数量的类)可以改变，所述生成的类可以相应地改变。因此，车辆分配单元112可以为每个所述车辆群组合进行分类。例如，除了上面讨论的4辆3人车和2辆4人车的第一群组合之外，群组402可以具有2辆2人车、4辆3人车和1辆4人车的第二群组合。

可以设想，如果父群组的群组合改变，后群组的群组合也可以改变。例如，在开始时，所述第一群组合(即4辆3人车和2辆4人车)和所述第二群组合(即2辆2人车、4辆3人车和1辆4人车)均可用于群组402的乘客。如上所述例如，所述第一群组合中的3人车、所述第二群组合中的3人车和所述第二群组合中的4人车可以显示给乘客以供他/她选择。当所述乘客选择所述第二群组合中的4人车时，群组402中的其他乘客不能再选择所述第一群组合中的车辆。然而，如果所述乘客选择所述第二群组合中的3人车，则对于群组402中的其他乘客仍然可选择所述第一和第二群组合中的其他车辆用，因为所述第一和第二群组合都包含3人车。因此，车辆分配单元112可以提供多种车辆群组合供乘客选择。

车辆分配单元112可以对其他群组(包括另一父群组或后群组)执行上述过程，并通过通信接口102将车辆的分配发送给运输服务提供者。

因此，用于提供运输服务的系统100可以将运输任务聚类成多个群组并动态调整每个群组内的运输能力的分布以提高车辆的效率。

本申请的另一方面涉及一种提供运输服务的方法。图5是根据本申请的一些实施例所示的一种提供运输服务的示例性方法500的流程图。在一些实施例中，方法500可以由系统100实施，并且可以包括步骤S502-S510。

在步骤S502中，系统100可以接收区域内的运输任务。至少一名乘客可以请求所述运输任务。所述运输任务可以包括任务信息，所述任务信息包括乘客的身份、行程的起点、行程的目的地、行程的出发时间等。所述请求可以从移动设备或桌面设备发送。在一些实施例中，所述行程的起点可以是乘客的当前位置或乘客指定的另一位置。可以设想，所述任务信息还可以包括任何必要的信息，例如车辆的要求、该运输任务中的乘客数量等。

系统100可以进一步从至少一个运输服务提供者获取运输能力信息。所述运输能力信息可以包括，例如所述至少一个运输服务提供者的身份、车辆的乘客容量、车辆型号、车辆的位置等。

在步骤S504中，系统100可以根据所述任务信息将所述运输任务聚类成多个群组，所述任务信息包括乘客的身份、行程的起点、行程的目的地、行程的出发时间。可以设想，在所述聚类之前，可以过滤所述接收的运输任务以移除异常任务。

系统100可以确定运输任务的起点(或目的地)之间的每个距离是否小于预设距离。在一些实施例中，当所述距离小于所述预设距离时，所述运输任务可以被聚类成一个群组。系统100可以进一步确定这些任务的出发时间是否足够接近以被聚类到同一群组中。因此，同一群组中的运输任务包括相同或相似的起点、目的地和出发时间。

系统100可以基于每个群组中的运输任务的出发时间确定会合时间，其中各个群组的会合时间是所述各个群组中的运输任务的平均出发时间。所述会合时间将是车辆接载所述群组中乘客的时间。

类似地，系统100可以基于每个群组中的运输任务的起点和目的地来确定会合位置和到达位置。各个群组的会合位置可以是各个群组中的运输任务的起点的平均位置。可以设想，可以基于所述平均位置根据地图信息进一步调整所述会合位置。例如，可以将所述会合位置确定为所述平均位置附近的十字路口。在一些实施例中，所述到达位置可以是最后一位乘客的目的地，也可以是所述群组中目的地的平均位置。系统100可以进一步估计每个群组的结束时间。群组的所述结束时间可以由导航服务(例如，嘀嘀打车)生成。

可以设想，系统100可以使用聚类模型对运输任务进行聚类。所述聚类模型可以分析运输任务的特征元素(例如，起点、目的地和出发时间)，并将类似的运输任务聚类成群组。所述特征元素不受上述例子的限制。

因此，系统100可以将所述运输任务聚类成多个群组，并生成所述群组的运输服务的会合位置、到达位置、会合时间和结束时间。

在步骤S506中，系统100可以根据与各个群组相关联的会合时间来对所述多个群组进行排序。在一些实施例中，通常，对于目标群组，可以将具有早于所述目标群组的会合时间的第一群组确定为所述目标群组的前群组，可以将具有晚于所述目标群组的会合时间的第二群组确定为所述目标群组的后群组。但是，群组可能没有前群组，在这种情况下，所述群组成为父群组。

运输服务提供者只有在当前群组的当前任务已完成，才可以接受下一群组的另一任务。因此，可以在当前群组的结束时间之后设置所述下一群组的会合时间。在一些实施例中，所述下一群组的会合时间与所述当前群组的结束时间之间的时间差可以与所述下一群组的会合位置与所述当前群组的到达位置之间的距离相关联。例如，所述导航服务可以估计运输服务提供者在两群组之间行进上述距离所需时间。当所述估计的时间段小于所述时间差时，可以将所述下一群组确定为后群组。

在一些实施例中，对于目标群组，不止一个候选群组可以满足关于会合时间和时间差的上述条件。群组排序单元108可以使用贪心算法选择一个所述候选群组作为后群组。所述贪心算法总能选择能提供明显优势的后群组。例如，所述贪心算法可以选择与所述目标群组具有最短距离的后群组。

在一些实施例中，步骤S506可以进一步包括将群组划分为两个子群组的方法。图6是根据本申请的实施例所示的用于将群组划分为两个子群组的示例性方法600的流程图。方法600可以包括步骤S602-S610。

在步骤S602中，系统100可以确定需要从第一群组调动到第二群组的能力。在步骤S604中，系统100可以确定所述调动能力是否小于所述第二群组所需的运输能力。如果所述调动能力不小于所述第二群组所需运输能力(S604：否)，则系统100返回到方法500。如果调动能力小于所述第二群组所需的运输能力(S604：是)，则系统100可以进行步骤S606。在步骤S606中，系统100可以将所述第二群组划分为第一子群组和第二子群组，其中所述第一子群组所需运输能力与所述调动能力相对应。在步骤S608中，系统100之后可以将所述调动能力分配给所述第一子群组，并将所述第一子群组指定为所述第一群组的后群组。系统100还可以将第二子群组指定为父群组，因为它没有前群组，并且为所述第二子群组分配它需要的运输能力。

在一些实施例中，若当前群组具有足够的运输能力用于其后群组时，在完成所述当前群组的运输任务之后，系统100可以将所述运输能力分配给所述后群组。在一些实施例中，若当前群组没有足够的运输能力用于其后群组时，系统100可以将另一个前群组的运输能力分配给所述后群组。也就是说，一个群组可以从多于一个前群组中接收运输能力。

参照图5，在步骤S508中，系统100可以搜索用于所述多个群组的运输能力。通常，运输服务提供者可以提供的运输能力取决于车辆。系统100可以自上而下搜索可用车辆，例如，首先从父群组开始。如上所述，系统100可以从所述运输服务提供者接收运输能力信息，表明他/她的车辆的能力和位置。基于所述获取的运输能力信息，系统100可以搜索邻域中的可用车辆。如果找不到与所述车辆相关联的足够的运输能力，则可以扩大邻域。

系统100可以将所述运输能力分配至每个群组。在一些实施例中，系统100可以根据每个车辆的运输能力和所述群组中的运输任务生成车辆群组合，并确定所述群组的车辆群组合。例如，一群组可以包括20名乘客，所述车辆群组合可以是4辆3人车和2辆4人车。也就是说，可以向所述群组提供六辆车的群组合以接载20名乘客。可以设想，在给定足够的可用车辆的情况下，可以生成一种以上的车辆群组合。

为了提高所述拼车服务的效率，一辆车中对于每个乘客的运输任务优选地具有相同或相似的起点、目的地、出发时间和到达时间。也就是说，分配给一个车辆的运输任务优选地是类似的，以提高效率。因此，在一些实施例中，步骤S508可以进一步包括将运输任务分配给各个车辆的方法。

例如，图7是根据本申请的实施例所示的用于将运输任务分配给各个车辆的示例性方法的流程图。方法700可以包括如下的步骤S702-S708。

在步骤S702中，系统100可以确定群组中的运输任务的相似性矩阵。可以利用相似性模型生成运输任务的相似性矩阵。所述相似性模型可以比较，例如，运输任务的起点、目的地、出发时间、到达时间和其他特征以生成所述相似性矩阵。

在步骤S704中，系统100可以基于所述相似性矩阵确定特征元素。可以将所述相似性矩阵转换为拉普拉斯矩阵，以为每个运输任务生成特征元素。

在步骤S706中，系统100可以根据所述特征元素将所述运输任务聚类为预设数量的类。在一些实施例中，所述预设数量可以是在步骤S508中确定的所述群组的车辆数量。通常，具有相同或类似特征元素的运输任务将尽可能地聚类到相同的类(例如，相同的车辆)中。也就是说，在该步骤中可以建立运输任务和车辆之间的对应关系。用于聚类的方法可以是K均值方法或基于密度的聚类方法(例如，最大密度方法)。可以设想，所述用于聚类的方法不受上述示例性方法的限制。

在步骤S708中，系统100可以基于所述类将所述运输任务分配给每个车辆。因为已经建立了运输任务和车辆之间的对应关系，所以系统100可以分别将所述运输任务分配给车辆。

如步骤S508中所讨论的，可以生成一种以上的车辆群组合。并且对于每种群组合，根据上述方法700，可以将运输任务分配给不同于第二车辆的第一车辆，同一运输任务可以在另一群组合中分配给所述第二车辆。也就是说，提供步骤S508中确定的多于一种群组合，乘客可有多于一种的车辆选择。在一些实施例中，拼车平台可以允许乘客查看他/她的运输任务所分配到的车辆的选择。

可以设想，如果父群组的群组合改变，后群组的群组合也可以改变。

本申请的另一方面是涉及一种存储指令的非暂时性计算机可读介质，所述指令在被执行时使得一个或多个处理器执行如上所述的方法。所述计算机可读介质包括易失性或非易失性、磁性、半导体、磁带、光学、可擦除的、不可擦除或其他类型的计算机可读介质或计算机可读存储设备。例如，如所公开的，所述计算机可读介质可以存储有计算机指令的存储设备或存储器模块。在一些实施例中，所述计算机可读介质可以是存储有计算机指令的磁盘或闪存驱动器。

显而易见，本领域技术人员可以对所公开的系统和相关方法进行各种修改和变化。考虑到所公开的系统和相关方法的说明和实践，其他实施例对于本领域技术人员将是显而易见的。尽管以使用车辆向乘客提供拼车服务为例描述了实施例，但是所公开的系统和方法可以应用于任何运输服务。例如，所述运输任务可以与货物相关联，而不是与上述乘客相关联。并且本申请的实施例中的车辆可以是非机动车辆。

本申请中的说明书和示例的目的仅被认为是示例性的，真正的范围由以下权利要求及其等同物限定。

Claims (20)

1.一种计算机实施的提供运输服务的方法，包括：

通过通信接口接收区域内的运输任务；

由处理器将所述运输任务聚类成多个群组；

由所述处理器搜索用于所述多个群组的运输能力；以及

通过所述通信接口将所述运输能力分配给每个群组。

2.根据权利要求1所述的方法，其特征在于，根据每个运输任务的起点、目的地或出发时间中的至少一个聚类所述运输任务。

3.根据权利要求2所述的方法，其特征在于，进一步包括：

基于每个群组中的运输任务的出发时间确定会合时间，每个群组的会合时间是各个群组中的运输任务的平均出发时间；以及

根据与所述各个群组相关联的会合时间对所述多个群组进行排序。

4.根据权利要求3所述的方法，其特征在于，根据与所述各个群组相关联的会合时间对所述多个群组进行排序进一步包括：为每个群组确定前群组或后群组。

5.根据权利要求4所述的方法，进一步包括：当群组没有前群组时，将所述群组确定为父群组。

6.根据权利要求3所述的方法，进一步包括：

确定从第一群组调动到第二群组的能力；

当所述调动的能力小于所述第二群组的运输能力时，将所述第二群组划分为第一子群组和第二子群组；

将所述调动的能力分配给所述第一子群组；以及

将所述第二子群组指定为父群组。

7.根据权利要求1所述的方法，其特征在于，将所述运输能力分配给每个群组进一步包括：

确定所述群组中所述运输任务的相似性矩阵；

基于所述相似性矩阵确定特征元素；

根据所述特征元素将所述运输任务聚类成预设数量的类；以及

基于所述类将所述运输任务分配给至少一个车辆。

8.根据权利要求7所述的方法，其特征在于，将所述相似性矩阵变换为拉普拉斯矩阵以确定所述特征元素。

9.根据权利要求7所述方法，其特征在于，所述预设数量是所述车辆的数量。

10.根据权利要求4所述的方法，其特征在于，使用贪心算法基于所述群组的所述会合时间确定每个群组的所述前群组或所述后群组。

11.一种提供运输服务的系统，包括：

通信接口，被配置为接收区域内的运输任务；

存储器；以及

处理器，耦合至所述通信接口和所述存储器，被配置为：

将所述运输任务聚类成多个群组；

搜索用于所述多个群组的运输能力；以及

将所述运输能力分配给每个群组。

12.根据权利要求11所述的系统，其特征在于，根据每个运输任务的起点、目的地或出发时间中的至少一个聚类所述运输任务。

13.根据权利要求12所述的系统，其特征在于，所述处理器进一步被配置为

基于每个群组中的运输任务的出发时间确定会合时间，其中，每个群组的会合时间是各个群组中的运输任务的平均出发时间；以及

根据与各个群组相关联的所述会合时间对所述多个群组进行排序。

14.根据权利要求11所述的系统，其特征在于，所述处理器进一步被配置为每个群组确定前群组或后群组。

15.根据权利要求14所述的系统，其特征在于，所述处理器进一步被配置为当所述群组没有在前群组时，将所述群组确定为父群组。

16.根据权利要求13所述的系统，其特征在于，所述处理器进一步被配置为：

确定从第一群组调动到第二群组的能力；

当所述调动的能力小于所述第二群组的运输能力时，将所述第二群组划分为第一子群组和第二子群组；

将所述调动的能力分配给所述第一子群组；以及

将所述第二子群组指定为父群组。

17.根据权利要求11所述的系统，其特征在于，所述处理器进一步被配置为：

确定所述群组中所述运输任务的相似性矩阵；

基于所述相似性矩阵确定特征元素；

根据所述特征元素将所述运输任务聚类成预设数量的类；以及

基于所述类将运输任务分配给多个车辆。

18.根据权利要求17所述的系统，其特征在于，将所述相似性矩阵变换为拉普拉斯矩阵以确定所述特征元素。

19.根据权利要求17所述的系统，其特征在于，所述预设数量是所述车辆的数量。

20.一种存储一组指令的非暂时性计算机可读介质，所述一组指令在由电子设备的至少一个处理器执行时使所述电子设备执行提供运输服务的方法，所述方法包括：

接收区域内的运输任务；

将所述运输任务聚类成多个群组；

搜索用于所述多个群组的运输能力；以及

将所述运输能力分配给每个群组。