一种基于时间与费用约束的动态拼车匹配方法

摘要

本发明提出了一种较为通用的动态拼车匹配方法，解决了在乘客的拼车时间和拼车费用两个约束条件下，为乘客实时匹配满足条件的最优司机的问题。本发明中的动态拼车匹配方法共分为三个步骤，包括：步骤1，建立动态拼车匹配模型，包括时间、费用以及skyline关系模型；步骤2，建立动态拼车数据结构，包括Driver Table，Matching Table，Grid索引等；步骤3，动态拼车匹配，其核心思想是通过尽量减少或延后最短路径的计算来保证匹配的高效性；同时，通过设置司机的skyline约束，进一步减少匹配的计算量，而且保证了匹配到的司机与其他备选司机相比，时间或者费用方面是较优的。

主权项

一种基于时间与费用约束的动态拼车匹配方法，包括：步骤1，建立动态拼车匹配模型作为动态拼车仅有的两个参与角色，司机与乘客在匹配时均有各自的起始位置与终点位置,默认起点与终点间的路线为最短路径；为方便描述，使用d表示司机，r表示乘客，RiderTrip和DriverTrip分别对应司机与乘客在匹配前各自的路线，路线长度又可转换成相应的费用成本；在匹配过程中，乘客和司机拼车费用的计算方式决定了匹配方法的设计；考虑到司机可能需要偏离原计划路线，通过绕道去接乘客或送乘客到目的地，最终乘客应付给司机的费用中不仅包含拼车后走的路程，还要包含司机绕道所产生的成本，下面给出拼车费用的表示方式：Price(d,r)＝RiderTrip+Detour其中，Price(d,r)表示拼车费用；RiderTrip表示拼车后共同走的路程，即乘客的路线；Detour表示司机相对其原始路线多走的路程，即绕道路程，其计算方式如下：Detour(d,r)＝Pickup+RiderTrip+Return–DriverTrip其中，Pickup是司机起点与乘客起点间的路程，即司机去接乘客时的费用；Return表示司机目的地与乘客目的地间的路程距离，即司机在送完乘客时返回的费用；基于上述关系，可进一步得到计算拼车费用的如下公式：Price(d,r)＝Pickup+2*RiderTrip+Return–DriverTrip     (1)公式1中右边的计算单元均是拼车匹配模型中的基本费用单元，在随后的匹配方法设计当中将被使用；下面，从乘客角度出发，给出拼车匹配模型的定义；定义1.给定一个司机集合D和一个乘客r，动态拼车匹配旨在D中找到一个子集合D’，并且对于D‘中的任意一个司机，需要满足如下约束：·时间约束：Pickup(d,r)<r_{max_Time}·费用约束：Price(d,r)<r_{max_Price}·Skyline约束：D’需要经过对Pickup(d,r)与Price(d,r)的skyline处理定义1中，r_{max_Time}表示乘客的最大等待时间，r_{max_Price}表示乘客的最大拼车费用；步骤2，建立动态拼车数据结构在执行动态拼车匹配时需要涉及到相关数据的存储、排序等工作，因此需要根据定义1所述拼车问题模型设计合适的数据结构以支撑匹配过程的运算；Driver Table司机表.拼车匹配过程中需要维护每个司机的4个字段：(1)ID：司机d的唯一标识；(2)CurrentLocation：d的当前位置，由于匹配时司机可能处在移动状态，因此该值将会随着时间的不同而可能发生变化，且该变化可由特定的终端设备来捕获并更新，如GPS；(3)DestinationLocation：d的目的地位置；(4)DriverTrip：d的起点(即CurrentLocation)与目的地间的最短路径；Matching Table匹配表，该表为动态拼车匹配过程中用来匹配一个乘客与多个司机的主要依据；它包含了一对乘客r与司机d的6个字段内容：(1)ID：司机d的唯一标识；(2)Pickup：d起点与r起点间的最短路径，该值也可经换算表示成乘客r的实际等待时间；(3)EuclideanPickup：d起点与r起点间的欧式距离；(4)Return：d目的地与i目的地间的的最短路径；(5)EuclideanReturn：d目的地与r目的地间的欧式距离；(6)DriverTrip：Driver Table中的第4个字段，即d的起点与目的地间的最短路径；步骤3，动态拼车匹配相对最短路径距离，两点间欧式距离的计算复杂度要低的多；因此，动态拼车匹配方法就是基于Driver Table与Matching Table，利用欧式距离作为出发点，设计一系列的边界条件，通过提前过筛选掉一些不需要计算所有最短路径的司机，进而提高匹配效率，得到满足乘客需求的候选司机列表；匹配方法从整体上可分为两个阶段：欧氏距离匹配与半欧式距离匹配；3.1欧氏距离(Euclidean Distance)匹配过程欧氏距离匹配的思路是使用欧氏距离代替实际距离进行预估算和筛选；因为司机与乘客间的欧氏距离小于实际距离，因此可以利用不等式的传递性，初步排除一些不满足要求的司机；具体步骤如下：3.1.1时间筛选。以乘客的起点r为圆心，将乘客最大等待时间r_{max_Time}转化的欧氏距离作为半径画一个圆Q_R，即执行一个范围查询(range query)；所有不包含在Q_R内的司机将会被排除；3.1.2拼车成本筛选。将拼车费用的公式1中的Pickup和Return分别用欧氏距离EuclideanPickup和EuclideanReturn进行替换，得到新的费用公式Price(d,r)＝EuclideanPickup+2*RiderTrip+EuclideanReturn–DriverTrip     (公式2)因为欧氏距离在地图上两点间最短，根据不等式的传递性，若司机d使用公式2计算出的理想拼车费用大于r_{max_Price}，那么d用公式1得出的实际也必然大于r_{max_Price}；所以将这部分不符合条件的司机排除；3.2半欧氏距离(Semi‑Euclidean Distance)匹配过程为了找出正确的候选司机列表，在欧氏距离匹配结果的基础上，需要进一步筛选，同时还要减少最短路径计算和skyline比较的次数；在公式2的基础上，分步将欧氏距离用实际的最短路径距离代替来计算拼车费用Price(d,r)，并进行筛选，以达到筛选司机的同时尽可能减少计算的目的；半欧氏距离匹配法步骤如下：3.2.1公式2中Pickup替换将EuclideanPickup用实际Pickup代替，得到：Price(d,r)＝Pickup+2*RiderTrip+EuclideanReturn–DriverTrip     (公式3)3.2.2匹配表排序将匹配表中的每位司机根据EuclideanReturn‑DriverTrip的值按递增进行排序；接着设置一个阀值MAX，初始化其值为乘客提出拼车请求时的费用约束r_{max_Price}，作为最终成为匹配成功司机的拼车成本的上边界；基于skyline计算过程，即拼车费用与等待时间，MAX值将逐渐缩小，这样使得更多的满足乘客时间和费用约束的司机被过滤掉，即这些司机不能作为skyline结果返回；3.2.3候选司机筛选该筛选过程是迭代式的。在每一次迭代过程当中，需要首先从匹配表中挑选离乘客最近的一个司机d，可在路网上执行增量K近邻算法(Incremental K nearest neighbor)获取；然后计算他的实际Pickup值；司机d的Pickup值只可能是以下四种情况之一：A1司机d的Pickup>r_{max_Time}，即司机d无法按时接到乘客；此情况下会立即终止接下来的筛选流程，将匹配表中包括d在内的所有司机删除；因为其他司机相比于司机d，离乘客的起点更远，无法满足乘客的时间约束；A2司机d的Pickup<r_{max_Time}，但d根据公式3所计算出的拼车费用大于MAX；因为不满足费用约束，司机d将会被从匹配表中删除；一同被排除的还有匹配表中位于司机d之后的所有司机；因为根据公式3计算，虽然其他司机的RiderTrip值与司机d相同，但是他们的Pickup和EuclideanReturn‑DriverTrip的值都大于d，所以总拼车费用也必然大于d和MAX；A3司机d的Pickup<r_{max_Time}，且d根据公式3所计算出的拼车费用也小于MAX，但是d使用公式1计算出的拼车费用大于MAX；因此，d不能满足拼车费用约束，不能成为候选司机；A4以上三种情况之外；d将成为既能满足时间约束又能满足费用约束的候选司机；接着我们将MAX的值改为根据公式1计算得到的司机d的实际的拼车费用；然后将该司机从匹配表中删除，最后进入下一个迭代筛选过程；更改MAX的值是因为最终返回的匹配结果要求是skyline关系，即新的候选司机相对前一个候选司机来说，由于其等待时间要比前一个司机长，所以其造成的拼车费用要比上一个候选司机小才能作为最终结果返回。