CN113393026B - 一种无人出租车换乘及路径匹配方法 - Google Patents

Abstract

本发明公开了一种无人出租车换乘及路径匹配方法，包括以下步骤：后台服务器收集乘客P_i在共乘app上输入的基本需求信息；根据乘客P_i所提交的起始地和目的地，搜寻请求区域内所有未绑定乘客P_j，进行初次绑定；对初次绑定的乘客组的路径进行规划，并计算规划后的路线是否符合时间约束条件，若符合，则最终绑定乘客组，反之则将乘客加入未绑定的集合中；将最终绑定的乘客组与无人出租车候选集W_c中的无人出租车进行司乘匹配；在下一时间间隔内，更新未绑定集合W和无人出租车候选集W_c，对新加入和未绑定的集合中的乘客循环判断换乘条件，直到所有的乘客被分配至目的地或者没有新乘客为止。本发明具有提高无人出租车的合乘率、降低城市交通拥挤率等优点。

Description

一种无人出租车换乘及路径匹配方法

技术领域

本发明涉及智能交通的技术领域，尤其涉及一种无人出租车换乘及路径匹配方法。

背景技术

随着交通行业的自动驾驶技术迅速发展以及大数据分析的广泛应用，未来人们出行的主要方式将以无人驾驶为主。然而，现有的网约车平台只能一次性给乘客分配出租车，不能实时性地根据路网上地情况智能分配，不足以满足未来无人驾驶的需求。为了提出一种更有效的匹配算法，本专利提出无人出租车换乘的定义。无人出租车换乘是指乘客在一定范围内搭乘无人出租车出行时，为了节约时间和出租车费用，增加其与他人共享的距离，采取的一种在乘坐过程中搭乘多辆无人出租车的方式。乘客在传统的出租车出行时，有时会遇到当前时间段无空闲车辆或无与其有顺路的车辆而等待时间过长的情况，通过无人出租车换乘方式，能减少乘客的等待时间，加快无人出租车的运行效率，进一步能降低城市的交通拥挤率，具有十分重要的意义。

发明内容

本发明所要解决的技术问题在于，提供一种无人出租车换乘及路径匹配方法，能有效解决乘客二次换乘问题并减少等待时间，实质性地再次提高车辆的合乘率，降低城市交通拥挤率。

为了解决上述技术问题，本发明提供了一种无人出租车换乘及路径匹配方法，包括以下步骤：

S1、后台服务器收集乘客P_i在共乘app上输入的基本需求信息，包括起始地O_i、目的地D_j、出发时间T₀、预期到达时间T_t、允许延误时间T_d；

S2、根据乘客P_i提交的起始地O_i和目的地D_j，搜寻请求区域内所有未绑定乘客P_j，即未绑定集合W中的乘客，通过对比乘客P_i的基本需求信息和未绑定乘客P_j的信息，依据初始换乘条件，筛选出满足换乘条件的乘客组，并对其进行初次绑定，然后进入步骤S3；如果没有与乘客P_i匹配的未绑定乘客P_j，则直接将乘客P_i加入未绑定集合W中，匹配结束，在下一时间间隔再次进行匹配；

S3、使用改进后的路径算法，对初次绑定的乘客组的路径进行规划，并计算规划后的路线是否符合时间约束条件，若符合，则最终绑定乘客组，且乘客组中乘客P_j脱离未绑定集合W后，进入步骤S4；反之则将P_i加入未绑定集合W中，匹配结束；

S4、将最终绑定的乘客组与无人出租车候选集W_c中的无人出租车进行司乘匹配；

S5、在下一时间间隔内，更新未绑定集合W和无人出租车候选集W_c，并对新加入和未绑定的集合中的乘客循环判断换乘条件，直到所有的乘客被分配至目的地或者没有新乘客为止。

进一步地，依据初始换乘条件筛选出满足换乘条件的乘客组的具体过程如下：

A1、确立中心点；

提取乘客P_i的起始地O_i和目的地D_j坐标以及其他在乘客P_i请求区域内上的未绑定乘客P_j的位置坐标点，并判断得到包含所有乘客的最小范围，即由max{X_i,X_j}、min{X_i,X_j}、max{Y_i,Y_j}、min{Y_i,Y_j}围成的矩形框，然后以：

作为中心点；

A2、路线变换；

将每位乘客的路径按照下面的方式进行连接：

Y_j)→(X_j，Y_j)

A3、判断乘客的路径重合：

若存在两位乘客P_i、P_j的路径从某一个节点开始路径重合，即至少有两个节点一致，且节点连线而成的矢量方向一致，则初步绑定两位乘客P_i、P_j，得到乘客组；若存在多位乘客P_j与乘客P_i同时重合，则按重合的节点的时间先后依次两两绑定；若某位乘客P_i与其他乘客P_j从起始地O_i到目的地D_j的路径均没有重合，则将该名乘客P_i加入未绑定集合W中。

进一步地，步骤S3使用改进后的路径算法，对初次绑定的乘客组的路径进行规划，并确定是否最终进行绑定的具体过程如下：

B1、利用Dijakstra算法分别算出已最终绑定的两位乘客P_i、P_j的最短路径，并计算其相应的到达时间T_t；

B2、使用DFS算法分别排列出乘客P_i、P_j从起始地O_i到目的地D_j所有可行的路径；

B3、计算路径相似度，将相似度高的两条路径进行整合，确认乘客P_i、P_j的最终路径轨迹；

B4、计算乘客P_i、P_j最终路径轨迹所需时间，判断其是否在时间约束内[T₀,T_t+T_d]；若两位乘客P_i、P_j均在时间约束范围内到达其各自目的地，则可最终确认绑定，并分别确定乘客P_i、P_j路径轨迹；若至少一位乘客没有在时间约束范围内，则不确认最终绑定，将乘客P_i送至未绑定集合W。

进一步地，进行司乘匹配的具体过程如下：

C1、判断当前无人出租车载客数L_n是否等于2；若是，则说明无人出租车已满载，不可再载乘客；若L_n小于2，则将该无人出租车加入无人出租车候选集W_c中；

C2、为绑定乘客组分配车辆；

若无人出租车候选集W_c中存在载客数L_n为0的无人出租车，则根据无人出租车与乘客P_i之间距离，曼哈顿距离近的即进行匹配；若无人出租车候选集W_c中没有载客数L_n为0的无人出租车，则在无人出租车候选集W_c中，从未绑定集合W中的乘客P_j所乘坐的无人出租车中选择车辆；根据乘客P_j所乘坐的无人出租车的当前所在位置S_p、预计下一时间间隔所到达的位置N_s和当前时刻的最终的目的地T_j，依次对比绑定乘客的信息，如果乘客P_i的起始地O_i与无人出租车的当前所在位置S_p或者下一时间间隔所到达的位置N_s或者最终的目的地T_j中任一位置一致或曼哈顿距离相近，那么绑定乘客P_i和无人出租车信息；若此时乘客P_i仍无匹配无人出租车，则等待下一时间段无人出租车的匹配；一旦无人出租车与乘客P_i绑定，即从无人出租车候选集W_c中移除该无人出租车，无论该无人出租车载客数L_n是否为2。

与现有技术相比，本方案原理及优点如下：

1.通过使用共乘app上传乘客需求信息，由后台服务器将新乘客信息与其他未绑定乘客信息进行汇总处理，并以最多合乘次数为目标。本方案利用实时的路网信息，再使用换乘判断的方法进行匹配，提高了车辆的合乘率，进而大大提高了车辆的利用率。

2.允许乘客中途更换无人出租车，直到到达目的地。由于有的乘客没有与他路径相同的乘客，系统判断为不能合乘，只能单独前行，可能会导致乘客的车费过高，而本发明通过允许乘客多次换乘，能有效解决乘客问题，大幅度减少乘客成本。

附图说明

图1为本发明一种无人出租车换乘及路径匹配方法的原理流程图；

图2为模拟路网示意图；

图3为路程对比图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。仅此声明，本发明在文中出现或即将出现的上、下、左、右、前、后、内、外等方位用词，仅以本发明的附图为基准，其并不是对本发明的具体限定。

本发明提供了一种无人出租车换乘及路径匹配方法，包括以下步骤：

S1、后台服务器收集乘客P_i在共乘app上输入的基本需求信息，包括起始地O_i、目的地D_j、出发时间T₀、预期到达时间T_t、允许延误时间T_d；

S2、根据乘客P_i提交的起始地O_i和目的地D_j，搜寻请求区域内所有未绑定乘客P_j，即未绑定集合W中的乘客，通过对比乘客P_i的基本需求信息和未绑定乘客P_j的信息，依据初始换乘条件，筛选出满足换乘条件的乘客组，并对其进行初次绑定，然后进入步骤S3；如果没有与乘客P_i匹配的未绑定乘客P_j，则直接将乘客P_i加入未绑定集合W中，匹配结束，在下一时间间隔再次进行匹配；

依据初始换乘条件筛选出满足换乘条件的乘客组的具体过程如下：

A1、确立中心点；

提取乘客P_i的起始地O_i和目的地D_j坐标以及其他在乘客P_i请求区域内上的未绑定乘客P_j的位置坐标点，并判断得到包含所有乘客的最小范围，即由max{X_i,X_j}、min{X_i,X_j}、max{Y_i,Y_j}、min{Y_i,Y_j}围成的矩形框，然后以：

作为中心点；

A2、路线变换；

将每位乘客的路径按照下面的方式进行连接：

Y_j)→(X_j，Y_j)

A3、判断乘客的路径重合：

若存在两位乘客P_i、P_j的路径从某一个节点开始路径重合，即至少有两个节点一致，且节点连线而成的矢量方向一致，则初步绑定两位乘客P_i、P_j，得到乘客组；若存在多位乘客P_j与乘客P_i同时重合，则按重合的节点的时间先后依次两两绑定；若某位乘客P_i与其他乘客P_j从起始地O_i到目的地D_j的路径均没有重合，则将该名乘客P_i加入未绑定集合W中。

S3、使用改进后的路径算法，对初次绑定的乘客组的路径进行规划，并计算规划后的路线是否符合时间约束条件，若符合，则最终绑定乘客组，且乘客组中乘客P_j脱离未绑定集合W后，进入步骤S4；反之则将P_i加入未绑定集合W中，匹配结束；

具体过程如下：

B1、利用Dijakstra算法分别算出已最终绑定的两位乘客P_i、P_j的最短路径，并计算其相应的到达时间T_t；

B2、使用DFS算法分别排列出乘客P_i、P_j从起始地O_i到目的地D_j所有可行的路径；

B3、计算路径相似度，将相似度高的两条路径进行整合，确认乘客P_i、P_j的最终路径轨迹；

B4、计算乘客P_i、P_j最终路径轨迹所需时间，判断其是否在时间约束内[T₀,T_t+T_d]；若两位乘客P_i、P_j均在时间约束范围内到达其各自目的地，则可最终确认绑定，并分别确定乘客P_i、P_j路径轨迹；若至少一位乘客没有在时间约束范围内，则不确认最终绑定，将乘客P_i送至未绑定集合W。

S4、将最终绑定的乘客组与无人出租车候选集W_c中的无人出租车进行司乘匹配，过程如下：

C1、判断当前无人出租车载客数L_n是否等于2；若是，则说明无人出租车已满载，不可再载乘客；若L_n小于2，则将该无人出租车加入无人出租车候选集W_c中；

C2、为绑定乘客组分配车辆；

若无人出租车候选集W_c中存在载客数L_n为0的无人出租车，则根据无人出租车与乘客P_i之间距离，曼哈顿距离近的即进行匹配；若无人出租车候选集W_c中没有载客数L_n为0的无人出租车，则在无人出租车候选集W_c中，从未绑定集合W中的乘客P_j所乘坐的无人出租车中选择车辆；根据乘客P_j所乘坐的无人出租车的当前所在位置S_p、预计下一时间间隔所到达的位置N_s和当前时刻的最终的目的地T_j，依次对比绑定乘客的信息，如果乘客P_i的起始地O_i与无人出租车的当前所在位置S_p或者下一时间间隔所到达的位置N_s或者最终的目的地T_j中任一位置一致或曼哈顿距离相近，那么绑定乘客P_i和无人出租车信息；若此时乘客P_i仍无匹配无人出租车，则则等待下一时间段无人出租车的匹配；一旦无人出租车与乘客P_i绑定，即从无人出租车候选集W_c中移除该无人出租车，无论该无人出租车载客数L_n是否为2。

S5、在下一时间间隔内，更新未绑定集合W和无人出租车候选集W_c，并对新加入和未绑定的集合中的乘客循环判断换乘条件，直到所有的乘客被分配至目的地或者没有新乘客为止。

为了证明本实施例的有效性，下面采用模拟实验的方式对本实施例进行检验，其中需要模拟的对象有路网、乘客和无人出租车。实验采取的评价指标是在一定时间内所节省的总里程。具体的求解方法描述如下：

数据模拟方法介绍

路网如图2所示。该路网一共有20个节点，34条边。

对于乘客请求，一轮随机产生4位乘客，其每轮产生时间间隔为5分钟。每位乘客的起点和终点在路网中随机出现，且允许不同乘客的起点或终点相同。如表1所示，系统随机产生的两轮新乘客，共8位乘客，每位乘客的需求信息见表格。

表1

对于无人出租车信息，选取4辆无人出租车作为基本运行车辆，其初始位置以第一轮出现的乘客位置为准。

实验步骤

1)根据介绍的数据模拟方法，随机生成乘客的请求信息，并初始化4辆无人出租车。

2)以5分钟为一时间间隔更新路网上的乘客和无人出租车信息，使用本实施例说明的换乘方法对乘客需求进行分配，循环到无新乘客且所有乘客均送至目的地为止。

3)为了验证本方法的有效性，收集无人出租车完成三轮乘客所运行的路程数，乘客的路线信息如表2所示；对比乘客不合乘、不换乘的无人出租车运行里程数，计算减少路程的公里数，绘制路程对比图，见图3。

乘客	路线	乘客	路线
				a	7-11-8	e	8-11-7
b	10-11-8	f	12-11-10
				c	14-11-12	g	16-11-7
d	14-11-16	h	16-11-10

表2

实验结果和分析

本模拟实验的评价指标为无人出租车送完乘客后所节省的里程数。该实验的总共乘客数为8位。图3是无人出租车每送完一位乘客后的车辆运行路程公里数变化图。星号表示预计无人出租车运行总路程数，圆圈表示实际无人出租车运行总路程数，正五角星表示无人出租车运行中减少的路程数(在计算总路程的时候，不计无人出租车在前往乘客起始地的路程数)。从图中可知，随着乘客的增多，可换乘的几率越大，可节省的公里数就越多，节省路径长度可达总路程的48％。

尽管本公开的描述已经相当详尽且特别对几个所述实施例进行了描述，但其并非旨在局限于任何这些细节或实施例或任何特殊实施例，而是应当将其视作是通过参考所附权利要求考虑到现有技术为这些权利要求提供广义的可能性解释，从而有效地涵盖本公开的预定范围。此外，上文以发明人可预见的实施例对本公开进行描述，其目的是为了提供有用的描述，而那些目前尚未预见的对本公开的非实质性改动仍可代表本公开的等效改动。

Claims (2)

1.一种无人出租车换乘及路径匹配方法，其特征在于，包括以下步骤：

S1、后台服务器收集乘客P_i在共乘app上输入的基本需求信息，包括起始地O_i、目的地D_j、出发时间T₀、预期到达时间T_t、允许延误时间T_d；

S2、根据乘客P_i提交的起始地O_i和目的地D_j，搜寻请求区域内所有未绑定乘客P_j，即未绑定集合W中的乘客，通过对比乘客P_i的基本需求信息和未绑定乘客P_j的信息，依据初始换乘条件，筛选出满足换乘条件的乘客组，并对其进行初次绑定，然后进入步骤S3；如果没有与乘客P_i匹配的未绑定乘客P_j，则直接将乘客P_i加入未绑定集合W中，匹配结束，在下一时间间隔再次进行匹配；

S3、使用改进后的路径算法，对初次绑定的乘客组的路径进行规划，并计算规划后的路线是否符合时间约束条件，若符合，则最终绑定乘客组，且乘客组中乘客P_j脱离未绑定集合W后，进入步骤S4；反之则将P_i加入未绑定集合W中，匹配结束；

S4、将最终绑定的乘客组与无人出租车候选集W_c中的无人出租车进行司乘匹配；

S5、在下一时间间隔内，更新未绑定集合W和无人出租车候选集W_c，并对新加入和未绑定的集合中的乘客循环判断换乘条件，直到所有的乘客被分配至目的地或者没有新乘客为止；

依据初始换乘条件筛选出满足换乘条件的乘客组的具体过程如下：

A1、确立中心点；

提取乘客P_i的起始地O_i和目的地D_j坐标以及其他在乘客P_i请求区域内的未绑定乘客P_j的位置坐标点，并判断得到包含所有乘客的最小范围，即由max{X_i,X_j}、min{X_i,X_j}、max{Y_i,Y_j}、min{Y_i,Y_j}围成的矩形框，然后以：

作为中心点；

A2、路线变换；

将每位乘客的路径按照下面的方式进行连接：

A3、判断乘客的路径重合：

若存在两位乘客P_i、P_j的路径从某一个节点开始路径重合，即至少有两个节点一致，且节点连线而成的矢量方向一致，则初步绑定两位乘客P_i、P_j，得到乘客组；若存在多位乘客P_j与乘客P_i同时重合，则按重合的节点的时间先后依次两两绑定；若某位乘客P_i与其他乘客P_j从起始地O_i到目的地D_j的路径均没有重合，则将该名乘客P_i加入未绑定集合W中；

步骤S3使用改进后的路径算法，对初次绑定的乘客组的路径进行规划，并确定是否最终进行绑定的具体过程如下：

B1、利用Dijakstra算法分别算出已最终绑定的两位乘客P_i、P_j的最短路径，并计算其相应的到达时间T_t；

B2、使用DFS算法分别排列出乘客P_i、P_j从起始地O_i到目的地D_j所有可行的路径；

B3、计算路径相似度，将相似度高的两条路径进行整合，确认乘客P_i、P_j的最终路径轨迹；

B4、计算乘客P_i、P_j最终路径轨迹所需时间，判断其是否在时间约束内[T₀,T_t+T_d]；若两位乘客P_i、P_j均在时间约束范围内到达其各自目的地，则可最终确认绑定，并分别确定乘客P_i、P_j路径轨迹；若至少一位乘客没有在时间约束范围内，则不确认最终绑定，将乘客P_i送至未绑定集合W。

2.根据权利要求1所述的一种无人出租车换乘及路径匹配方法，其特征在于，进行司乘匹配的具体过程如下：

C1、判断当前无人出租车载客数L_n是否等于2；若是，则说明无人出租车已满载，不可再载乘客；若L_n小于2，则将该无人出租车加入无人出租车候选集W_c中；

C2、为绑定乘客组分配车辆；

若无人出租车候选集W_c中存在载客数L_n为0的无人出租车，则根据无人出租车与乘客P_i之间距离，曼哈顿距离近的即进行匹配；若无人出租车候选集W_c中没有载客数L_n为0的无人出租车，则在无人出租车候选集W_c中，从未绑定集合W中的乘客P_j所乘坐的无人出租车中选择车辆；根据乘客P_j所乘坐的无人出租车的当前所在位置S_p、预计下一时间间隔所到达的位置N_s和当前时刻的最终的目的地T_j，依次对比绑定乘客的信息，如果乘客P_i的起始地O_i与无人出租车的当前所在位置S_p或者下一时间间隔所到达的位置N_s或者最终的目的地T_j中任一位置一致，那么绑定乘客P_i和无人出租车信息；若此时乘客P_i仍无匹配无人出租车，则等待下一时间段无人出租车的匹配；一旦无人出租车与乘客P_i绑定，即从无人出租车候选集W_c中移除该无人出租车，无论该无人出租车载客数L_n是否为2。

Images