基于动态时间切片和热度迁移的即时车辆共乘匹配方法

摘要

本发明提供一种基于动态时间切片和热度迁移的即时车辆共乘匹配方法，涉及车辆共乘技术领域。该方法首先使用共乘距离比率来评价司机和乘客的匹配价值，并定义司机和乘客匹配的约束条件；再基于动态时间切片划分和基于预测的迁移方法，求出司机和乘客匹配的初始解；使用一种优化的评估矩阵生成方法来计算司机和乘客间的最短路径和共乘距离比率；并通过贪婪算法获得即时车辆共乘匹配问题的初始解；通过使用多规则求解搜索算法，改进已有解；当获得最终的全局匹配方案时，不匹配的乘客将被迁移到下一个时间切片。该方法使用了高效的多规则求解搜索算法，可以有效地为实时拼车问题提供高质量的解。

说明书

技术领域

本发明涉及车辆共乘技术领域，尤其涉及一种基于动态时间切片和热度迁移的即时车辆共乘匹配方法。

背景技术

车辆共乘是由司机集合、乘客集合和共乘服务平台所构成的一种共享交通资源的服务形式。车辆共乘通过对一定时空范围内的司机集合和乘客集合进行价值匹配和路径规划来共享交通资源，在缓解交通拥堵、减少碳排放和提高出行效率方面发挥着非常积极的作用。为使司机利润最大化和与乘客匹配价值达到最大，车辆共乘研究在进行司机和乘客匹配时考虑以下目标之一：(1)最大化乘客数量；(2)最小化司机的总行驶距离或行驶时间；(3)最小化总的绕行距离。车辆共乘问题一般采用两步方式解决，首先建立该问题的数学模型，然后根据模型特性选择最优化或近似算法进行求解。即时车辆共乘需及时处理乘客订单信息，避免乘客等待时间过长，因此需要匹配算法在极短的时间内对大量司机集合和乘客集合进行匹配。在现实情况中，处理车辆共乘过程中的建模和解决大规模实时数据面临着以下挑战：(1)现实匹配方案的评估方法；(2)动态时间切片分割策略；(3)司乘对基于利润的自适应阈值；(4)求解大规模实时数据的匹配和路径规划算法。

发明内容

本发明要解决的技术问题是针对上述现有技术的不足，提供一种基于动态时间切片和热度迁移的即时车辆共乘匹配方法，实现车辆共乘服务中司机和乘客的匹配。

为解决上述技术问题，本发明所采取的技术方案是：基于动态时间切片和热度迁移的即时车辆共乘匹配方法，包括以下步骤：

步骤1：使用共乘距离比率来评价司机和乘客的匹配价值，并定义司机和乘客匹配的约束条件；

步骤1.1：计算司机和乘客的共乘距离比率和对应的目标函数；

在路网Gra＝中，每个节点u∈U，每条边e∈E，对于任意司乘对，其中每个司机

其中，司机集合为D＝{d

步骤1.2：定义司机和乘客匹配的约束条件；

所述司机和乘客匹配的约束条件包括绕行距离约束、迁移约束和唯一性约束，具体为：

(1)以公式4定义司机和乘客匹配的绕行距离约束：

其中，

(2)以公式5定义司机和乘客匹配的迁移约束，当η

(3)以公式6和7定义司机和乘客匹配的唯一性约束，司机d

步骤2：基于动态时间切片划分和基于预测的迁移方法，求出司机和乘客匹配的初始解；基于预测的迁移方法使用司机和乘客的历史匹配数据来预测评估司机和乘客匹配的自适应阈值，只有当司机和乘客的匹配价值超过一定的共乘距离比率时才进行匹配，具体方法为：

步骤2.1：使用动态时间切片划分方法划分共乘时间；

定义两个上限：(1)最大乘客数Max_user：表示在一个时间切片内要匹配的最大通勤者数量；(2)最大等待时间Max_time：表示当前已匹配乘客的最大等待时间；基于以下规则进行时间切片T

(1)使用N

(2)使用Δt表示当前时间t和

步骤2.2：使用基于预测的迁移方法，在时间切片划分后，筛选出司机集合的待匹配乘客；

通过分析司机和乘客的历史匹配数据来确定匹配阈值

其中，N

步骤2.3：根据当前时间切片指数和司机和乘客的历史匹配数据集中的原始时间切片指数间的差异计算两者间的阈值的最小值来评估被迁移到下一时间切片的乘客；

对于一个被迁移的司机

其中，e

步骤3：使用多规则求解搜索算法来搜索即时车辆共乘问题的解集；

首先，使用一种优化的评估矩阵生成方法来计算

步骤3.1：通过公式定义多规则求解搜索算法中的不连续值替换操作、单步变更操作和单步变更解集；

步骤3.1.1：以公式10定义一个I形式的解决方案，以公式11-15定义多规则求解搜索算法中的不连续值替换操作；

I＝(I

D

其中，I表示即时车辆共乘匹配问题的m维解向量，即匹配方案，其中向量的每个维度对应于d

步骤3.1.2：以公式16-17定义多规则求解搜索算法中的单步变更操作SSR，不连续值替换操作DVR的一个解I通过改变I

其中，

步骤3.1.3：定义单步变更解集；如果通过单步变更操作

步骤3.2：通过初始化算法生成评估矩阵和解矩阵；定义评估矩阵V(m×n)来表示价值在匹配司机和乘客时起到主观驱动作用；V中每个条目v

步骤3.2.1：对于已有司机集合

步骤3.2.2：获取司机集合

步骤3.2.3：计算司机d所在地到其他所有节点的最短路径disMap1；

disMap1＝shortest_path(loc(d),all) (18)

步骤3.2.4：计算所有其他所有节点到司机d目的地的最短路径disMap2；

disMap2＝shortest_path(all,dst(d)) (19)

步骤3.2.5：获取乘客集合{R∪R

步骤3.2.6：计算乘客r的所在地和目的地之间的最短路径dis1；

dis1＝shortest_path(loc(r),dst(r)) (20)

步骤3.2.7：从司机d的循环中得到司机d的所在地与乘客r目的地之间的最短路径dis2；

dis2＝dis1Map[loc(d)][loc(r)] (21)

步骤3.2.8：从司机d的循环中得到司机d的目的地与乘客r目的地之间的最短路径dis3；

dis3＝dis2Map[dst(d)][dst(r)] (22)

步骤3.2.9：由步骤3.2.2-步骤3.2.8得到当前评估矩阵

其中，disMap1表示司机d所在地loc(d)到所有节点的最短路径表，shortest_path表示最短路径求解算法，即Dijkstra算法，all表示路网中的所有节点，disMap2表示路网中所有节点到司机d目的地dst(d)的最短路径表；

步骤3.3：生成即时车辆共乘问题的初始解；通过多规则求解搜索算法迭代从初始解集中的一个初始节点开始，使用贪婪算法来构造与此初始节点相匹配的初始解；对于给定的评估矩阵V(m×n)，对应的解矩阵P(m×n)中的所有条目被初始化为零；接下来对评估矩阵V中的每一列所有的条目都升序排序，然后从底部开始访问；具体实施步骤如下：

步骤3.3.1：由步骤3.2得到司机d和乘客r的匹配评估矩阵V，初始化定义解矩阵P(m×n)；

步骤3.3.2：对于评估矩阵V每列中的每一个元素，如果解矩阵P(m×n)的行值和大于0或者列值和大于0，则对评估矩阵V的列进行升序排序；

步骤3.3.3：对评估矩阵的排序列进行遍历，如果遍历到的当前元素在评估矩阵中的位置，对应在匹配方案中的位置列和为0，则将匹配方案中该位置置为1，并且选择跳过此列；

步骤3.4：根据不连续值替换的特点设计三种不同的规则来搜索多规则求解搜索算法的解；

(1)随机向下SSR规则：在解矩阵P(m×n)中选择值为1的两行进行位置交换；

(2)随机概率向下SSR规则：随机搜索解矩阵P(m×n)的列，依据该列所在位置与当前匹配位置的差值，选取所有差值为正值的位置并依据差值做概率分布来随机选取下一个位置，两个位置如果交换后价值增加，则进行交换；

(3)随机大值向下SSR规则：随机搜索并定位一个x

步骤3.5：随机使用步骤3.4中的一种规则进行搜索，直至获得全局最优方案。

采用上述技术方案所产生的有益效果在于：本发明提供的基于动态时间切片和热度迁移的即时车辆共乘匹配方法，使用一个具有动态时间切片和基于预期迁移的实时拼车框架，对即时车辆共乘问题进行了形式化建模，并使用了两种方法根据从历史数据中了解到的阈值，动态划分时间范围并迁移未匹配的乘客，本发明方法的动态时间切片划分能够在交通资源的利用率和一天中不同时间切片乘客的等待时间之间提供更智能的平衡。同时，本发明方法使用了一种高效的多规则求解搜索算法，可以有效地为实时拼车问题提供高质量的解。

附图说明

图1为本发明实施例提供的基于动态时间切片和热度迁移的即时车辆共乘匹配方法的整体框架图

图2为本发明实施例提供的基于动态时间切片和热度迁移的即时车辆共乘匹配方法的流程图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

本实施例中，基于动态时间切片和热度迁移的即时车辆共乘匹配方法，如图1、2所示，包括以下步骤：

步骤1：使用共乘距离比率来评价司机和乘客的匹配价值，并定义司机和乘客匹配的约束条件；

步骤1.1：计算司机和乘客的共乘距离比率和对应的目标函数；

在路网Gra＝中，每个节点u∈U，每条边e∈E，对于任意司乘对，其中每个司机

其中，司机集合为D＝{d

步骤1.2：定义司机和乘客匹配的约束条件；

所述司机和乘客匹配的约束条件包括绕行距离约束、迁移约束和唯一性约束，具体为：

(1)以公式4定义司机和乘客匹配的绕行距离约束：

其中，

(2)以公式5定义司机和乘客匹配的迁移约束，产生一个高质量的匹配结果，当η

(3)以公式6和7定义司机和乘客匹配的唯一性约束，司机d

步骤2：基于动态时间切片划分和基于预测的迁移方法，求出司机和乘客匹配的初始解；基于预测的迁移方法使用司机和乘客的历史匹配数据来预测评估司机和乘客匹配的自适应阈值，只有当司机和乘客的匹配价值超过一定的共乘距离比率时才进行匹配，具体方法为：

步骤2.1：使用动态时间切片划分方法划分共乘时间；

定义两个上限：(1)最大乘客数Max_user：表示在一个时间切片内要匹配的最大通勤者数量；(2)最大等待时间Max_time：表示当前已匹配乘客的最大等待时间；基于以下规则进行时间切片T

(1)使用N

(2)使用Δt表示当前时间t和

步骤2.2：使用基于预测的迁移方法，在时间切片划分后，筛选出司机集合的待匹配乘客；

通过分析司机和乘客的历史匹配数据来确定匹配阈值

其中，N

步骤2.3：根据当前时间切片指数和司机和乘客的历史匹配数据集中的原始时间切片指数间的差异计算两者间的阈值的最小值来评估被迁移到下一时间切片的乘客；

对于一个被迁移的司机

其中，e

步骤3：使用多规则求解搜索算法来搜索即时车辆共乘问题的解集；

首先，使用一种优化的评估矩阵生成方法来计算

步骤3.1：通过公式定义多规则求解搜索算法中的不连续值替换操作、单步变更操作和单步变更解集；

步骤3.1.1：以公式10定义一个I形式的解决方案，以公式11-15定义多规则求解搜索算法中的不连续值替换操作；

I＝(I

D

其中，I表示即时车辆共乘匹配问题的m维解向量，即匹配方案，其中向量的每个维度对应于d

步骤3.1.2：以公式16-17定义多规则求解搜索算法中的单步变更操作SSR，不连续值替换操作DVR的一个解I通过改变I

其中，

步骤3.1.3：定义单步变更解集；如果通过单步变更操作

步骤3.2：通过初始化算法生成评估矩阵和解矩阵，定义两个矩阵来加速即时车辆共乘匹配问题的求解；定义评估矩阵V(m×n)来表示价值在匹配司机和乘客时起到主观驱动作用；V中每个条目v

步骤3.2.1：对于已有司机集合

步骤3.2.2：获取司机集合

步骤3.2.3：计算司机d所在地到其他所有节点的最短路径disMap1；

disMap1＝shortest_path(loc(d),all) (18)

步骤3.2.4：计算所有其他所有节点到司机d目的地的最短路径disMap2；

disMap2＝shortest_path(all,dst(d)) (19)

步骤3.2.5：获取乘客集合{R∪R

步骤3.2.6：计算乘客r的所在地和目的地之间的最短路径dis1；

dis1＝shortest_path(loc(r),dst(r)) (20)

步骤3.2.7：从司机d的循环中得到司机d的所在地与乘客r目的地之间的最短路径dis2；

dis2＝dis1Map[loc(d)[ploc(r)] (21)

步骤3.2.8：从司机d的循环中得到司机d的目的地与乘客r目的地之间的最短路径dis3；

dis3＝dis2Map[dst(d)][dst(r)] (22)

步骤3.2.9：由步骤3.2.2-步骤3.2.8得到当前评估矩阵

其中，disMap1表示司机d所在地loc(d)到所有节点的最短路径表，shortest_path表示最短路径求解算法，即Dijkstra算法，all表示路网中的所有节点，disMap2表示路网中所有节点到司机d目的地dst(d)的最短路径表；

步骤3.3：生成即时车辆共乘问题的初始解；通过多规则求解搜索算法迭代从初始解集中的一个初始节点开始，使用贪婪算法来构造与此初始节点相匹配的初始解；对于给定的评估矩阵V(m×n)，对应的解矩阵P(m×n)中的所有条目被初始化为零；接下来对评估矩阵V中的每一列所有的条目都升序排序，然后从底部开始访问；具体实施步骤如下：

步骤3.3.1：由步骤3.2得到司机d和乘客r的匹配评估矩阵V，初始化定义解矩阵P(m×n)；

步骤3.3.2：对于评估矩阵V每列中的每一个元素，如果解矩阵P(m×n)的行值和大于0或者列值和大于0，则对评估矩阵V的列进行升序排序；

步骤3.3.3：对评估矩阵的排序列进行遍历，如果遍历到的当前元素在评估矩阵中的位置，对应在匹配方案中的位置列和为0，则将匹配方案中该位置置为1，并且选择跳过此列；

步骤3.4：根据不连续值替换的特点设计三种不同的规则来搜索多规则求解搜索算法的解；

(1)随机向下SSR规则：在解矩阵P(m×n)中选择值为1的两行进行位置交换；

(2)随机概率向下SSR规则：随机搜索解矩阵P(m×n)的列，依据该列所在位置与当前匹配位置的差值，选取所有差值为正值的位置并依据差值做概率分布来随机选取下一个位置，两个位置如果交换后价值增加，则进行交换；

(3)随机大值向下SSR规则：与之前的规则类似，最大向上SSR规则也随机搜索并定位一个x

步骤3.5：随机使用步骤3.4中的一种规则进行搜索，直至获得全局最优方案。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明权利要求所限定的范围。