一种基于通勤场景下的私家车拼车匹配方法

摘要

本发明公开了一种基于通勤场景下的私家车拼车匹配方法，包括以下步骤：S1：获取早高峰时段的通勤车辆的出行数据并进行预处理；S2：根据用户的行驶路径起点划分所属小区；S3：构建拼车匹配模型；S4：利用遗传算法求解拼车匹配模型的输出最佳拼车匹配方案。本发明针对同一小区的用户以小区为起点通过获取用户出行数据并进行预处理，进行用户所属小区划分，构建拼车匹配模型并求解最佳拼车匹配方案，适用性强，匹配效果好。

说明书

技术领域

本发明涉及智能交通技术领域，更具体地，涉及一种基于通勤场景下的私家车拼车匹配方法。

背景技术

城市交通拥堵会导致出行时间浪费、出行成本增加、交通事故增加、环境污染加剧等，严重阻碍城市化发展。目前交通拥堵问题已经成为我国最典型的城市病，尤其在早晚高峰时段，大多数通勤用户偏向于选择单独驾驶私家车出行，从而进一步加剧了拥堵。单独驾车所带来的私家车低利用率已经成为导致交通通行效率低下的重要因素之一，因此，拼车出行的模式应运而生。

“拼车”(即拼乘私家车，也可称“合乘”)指私家小汽车驾驶人与其他2-4人共乘出行，通过减少小汽车空座率达到减少小汽车出行量与道路需求等目的的集体行为，是一种创新的交通出行方式。城市通勤用户具有多用户、高频、固定线路等特点，是适用于拼车出行的强需求场景。

现有技术中，曹斌等人提出一种高效的大规模多对多拼车匹配算法(曹斌,洪峰,王凯,等.Uroad:一种高效的大规模多对多拼车匹配算法[J].计算机研究与发展,2019,56(04):866-883.)，该算法支持多乘客与多司机全局最优匹配，适用于大规模出行拼车。但该方案中规定每个匹配组合有且只有2名用户(即为“一名司机+一名乘客”的形式)，限制性较强，无法很好的适用于通勤场景。

发明内容

本发明为克服上述现有技术拼车匹配方法适用性不好，匹配效果不佳的缺陷，提供一种基于通勤场景下的私家车拼车匹配方法。

本发明的首要目的是为解决上述技术问题，本发明的技术方案如下：

一种基于通勤场景下的私家车拼车匹配方法，包括以下步骤：

S1：获取早高峰时段的通勤车辆的出行数据并进行预处理；

S2：根据用户的行驶路径起点划分所属小区；

S3：构建拼车匹配模型；

S4：利用遗传算法求解拼车匹配模型的输出最佳拼车匹配方案。

进一步的，获取早高峰时段的通勤车辆的出行数据并进行预处理具体步骤为：

S101：选取连续n个工作日早高峰时段的出行数据，筛选出出行次数不少于m次的用户数据；

S102：数据重算，将出行数据中每个用户的的出行时间的平均值作为其常规出发时间，由常规出发时间计算用户的期望到达时间，期望到达时间按如下公式计算:

S103：通过步骤S102的处理得到新的出行数据集。

进一步的，所述工作日数目n和出行次数m均为正整数，n和m分别为5和3。

进一步的，用户行驶路径起点即为用户所属小区。

进一步的，构建拼车匹配模型具体步骤为：

S301：设置模型的限定条件，具体包括：

同一小区所有用户的出发点和目的地都是事先确定的，且出发点位置相同；

所有用户都将在约定的出发时间窗内达到出发点；

拼车前所有用户的出行方式均为单独驾驶私家车出行；

S302：定义集合，具体包括：N＝{0,1,2,...,n}节点集合，0表示上车点；N\{0}表示下车点集合；K＝{1,2,...,k}车辆集合；

S303：定义变量，具体包括：

车辆k到达i的时间

S304：定义模型参数，具体参数包括有：

d

c

c

t

Δt

α表示可接受的最大时间阈值；

[e

[ee

q

q

S305：构建数学模型，所述数学模型包括：目标函数和约束条件。

进一步的，所述目标函数表达式为：

其中，

进一步的，所述约束条件包括：

其中，约束条件(1)表示时间窗约束，用户出发时间差值须在一定阈值内，且保证乘客必须在规定的时间窗内到达目的地；约束条件(2)表示一次访问约束，表示对每个乘客来说，为其提供服务的车辆有且只有一辆；约束条件(3)表示载客量约束，目的地下客数之和不超过车载容量；约束条件(4)表示决策变量为0-1变量；约束条件(5)表示时间惩罚函数，c

进一步的，利用遗传算法求解拼车匹配模型的输出最佳拼车匹配方案，其中遗传算法设计包括：染色体编码与解码、初始种群的生成、适应度函数、遗传算子、算法终止规则。

进一步的，所述染色体编码与解码包括：将同一小区的用户作为遗传算法中遗传空间的染色体进行编码，解码得到的为同一小区的用户拼车组合；

所述初始种群的生成包括：设置初始种群规模为M，初始种群的生成采用随机生成样本的方法，生成M个用户编码排列顺序，每一个排列顺序构成一种解，对应的可认为是一种拼车路线；

所述适应度函数用于衡量新生成个体的优劣，然后进行遗传操作，所述适应度函数为：

C

所述遗传算子包括：轮盘赌选择法、单点交叉算子和倒位变异算子，所述轮盘赌选择法每个个体的选择概率与其适应度值成比例，设置种群规模为M，个体x的适应度值为F

所述单点交叉算子在配对的染色体中随机选择一个交叉位置，然后在该位置对配对的染色体进行基因位变换；所述倒位变异算子对个体随机产生两个变异位，将变异区域的基因序列按照逆序的方式变换，再放入原位置；

所述算法终止规则为迭代次数等于其进化代数。

进一步的，所述遗传算法的进化代数为50。

与现有技术相比，本发明技术方案的有益效果是：

本发明针对同一小区的用户以小区为起点通过获取用户出行数据并进行预处理，进行用户所属小区划分，构建拼车匹配模型并求解最佳拼车匹配方案，适用性强，匹配效果好。

附图说明

图1为本发明方法流程图。

图2为本发明实施例中染色体编码形式示意图。

图3为本发明实施例单点交叉算子流程图。

图4为本发明实施例倒位变异操作示意图。

图5为本发明实施例小区出行量与拼车效果的关系图。

具体实施方式

为了能够更清楚地理解本发明的上述目的、特征和优点，下面结合附图和具体实施方式对本发明进行进一步的详细描述。需要说明的是，在不冲突的情况下，本申请的实施例及实施例中的特征可以相互组合。

在下面的描述中阐述了很多具体细节以便于充分理解本发明，但是，本发明还可以采用其他不同于在此描述的其他方式来实施，因此，本发明的保护范围并不受下面公开的具体实施例的限制。

实施例1

如图1所示，一种基于通勤场景下的私家车拼车匹配方法，包括以下步骤：

S1：获取早高峰时段的通勤车辆的出行数据并进行预处理；

在一个具体的实施例中，需要说明的是，本发明所述的早高峰为工作日的早上7点30分-9点。首先获取出行原始数据包括：用户号码、行驶路径、出发时间、到达时间以及路网基本属性数据，如表1所示为出行原始数据表。

表1出行原始数据表

获取了上述出行原始数据后需要进一步进行数据预处理，具体步骤为：

S101：选取连续5个工作日早高峰时段的出行数据，筛选出出行次数不少于3次的用户数据；

S102：数据重算，将出行数据中每个用户出行时间的平均值作为其常规出发时间，由常规出发时间计算用户的期望到达时间，期望到达时间按如下公式计算：

S103：通过步骤S102的处理得到新的出行数据集。

S2：根据用户的行驶路径起点划分所属小区；用户行驶路径起点所在小区即为用户所属小区。

需要说明的是，本发明基于同一小区进行通勤拼车，因此需要根据行驶路径的起点字段进行小区划分。例如如某用户行驶路径为1007-1009-1011-1013-1053-1054-1026-1025，则其所属小区为1007。

S3：构建拼车匹配模型；

需要说明的是，本发明的拼车匹配模型以同一小区的通勤用户作为研究对象，假设用户均能在给定的时间窗内到达指定上下车位置，通过车载容量限制、出发时间窗和到达时间窗限制、一次访问限制等约束，将所有用户进行拼车匹配，使得所有匹配组合的出行成本最小化。用户出行成本包括车辆固定成本、车辆行驶成本和时间惩罚成本。

构建拼车匹配模型具体步骤为：

S301：设置模型的限定条件，具体包括：

同一小区所有用户的出发点和目的地都是事先确定的，且出发点位置相同；

所有用户都将在约定的出发时间窗内达到出发点；

拼车前所有用户的出行方式均为单独驾驶私家车出行；

S302：定义集合，具体包括：N＝{0,1,2,...,n}节点集合，0表示上车点；N\{0}表示下车点集合；

K＝{1,2,...,k}车辆集合；

S303：定义变量，具体包括：

车辆k到达i的时间

S304：定义模型参数，具体参数包括有：

d

c

c

t

Δt

α表示可接受的最大时间阈值；

[e

[ee

q

q

S305：构建数学模型，所述数学模型包括：目标函数和约束条件。

进一步的，所述目标函数表达式为：

其中，

进一步的，所述约束条件包括：

其中，约束条件(1)表示时间窗约束，用户出发时间差值须在一定阈值内，且保证乘客必须在规定的时间窗内到达目的地；约束条件(2)表示一次访问约束，表示对每个乘客来说，为其提供服务的车辆有且只有一辆；约束条件(3)表示载客量约束，目的地下客数之和不超过车载容量；约束条件(4)表示决策变量为0-1变量；约束条件(5)表示时间惩罚函数，c

S4：利用遗传算法求解拼车匹配模型的输出最佳拼车匹配方案。

需要说明的是，得到拼车匹配模型后本发明遗传算法求解模型的最优解得到最佳拼车匹配方案，其中遗传算法设计包括：染色体编码与解码、初始种群的生成、适应度函数、遗传算子、算法终止规则。

所述染色体编码将要求解的问题表示成遗传空间的染色体或者个体，求解生成最优个体，通过解码转换为问题的最优方案。本发明的编码方式为整数编码，将同一小区的用户用“1,2,…,n”表示。也就是说将同一小区的用户作为遗传算法中遗传空间的染色体进行编码，解码得到的为同一小区的用户拼车组合；

例如，1001小区有8名用户，编号为1-8，通过算法求解最终获得最优解为四个拼车组合：2-5-4、7-3、1、8-6，算法求解所得最优解(未解码前)如图2所示。解码过程首先将2作为第一个拼车组合的用户，从左向右依次查询，将满足到达时间窗和载客量约束的编码加入第一个拼车组合，直至达到载客量上限或遍历完所有编码，即获得完整的第一个拼车组合2-5-4；将编码串中2、5、4删去，以7作为第二个拼车组合的用户，重复上述步骤，获得第二个拼车组合7-3；重复操作，直到所有用户编码基因都被安排，即获得1001小区的所有拼车组合。

设置初始种群规模为M，初始种群的生成采用随机生成样本的方法，生成M个用户编码排列顺序，每一个排列顺序构成一种解，对应的可认为是一种拼车路线；

适应度函数用于衡量新生成个体的优劣，然后进行遗传操作，适应度函数值越大，解的质量越好，进入下一代的几率越高。本发明所述适应度函数为：

C

遗传算子主要包括三种操作即：选择操作、交叉操作、变异操作，

其中，选择操作的目的是把优化的个体直接遗传到下一代，或通过配对交叉产生新的个体再遗传到下一代。个体被选中的概率与适应度值有关，个体适应度值越高，被选中的概率越大。本发明采用轮盘赌选择法进行选择操作，所述轮盘赌选择法每个个体的选择概率与其适应度值成比例，设置种群规模为M，个体x的适应度值为Fx，则个体被选中的概率为：

所述遗传算子包括：轮盘赌选择法、单点交叉算子和倒位变异算子，

交叉操作是指从种群中随机选择两个个体进行染色体的交换组合，把父代的优秀特征遗传给子代，从而产生新的优秀个体。本发明采用单点交叉算子进行相关操作，该算子在配对的染色体中随机选择一个交叉位置，然后在该位置对配对的染色体进行基因位变换。如图3所示为单点交叉算子执行流程示意图。

变异操作是指将个体的某些基因位进行变动，从而产生新的个体。变异操作使算法维持群体多样性，避免出现未成熟收敛现象，属于辅助算子。本发明采用的变异算子为倒位变异，对个体随机产生两个变异位，将变异区域的基因序列按照逆序的方式变换，再放入原位置。如图4所示为倒位变异操作示意图。

算法的终止需要预设一个条件，由于模型目标函数为求最优，求解前无法获知其最优值，因此本发明的算法终止规则是迭代次数达到其进化代数，进化代数设置为50。预设一个固定的进化代数可以有效地控制求解精度和效率，避免运行时间过长。

实施例2

本实施例通过具体的数据来说明和验证本发明方法。

数据集：本发明选取某市的203772条卡口过车数据作为验证数据集，日期为2019年9月2日至2019年9月6日(周一至周五共计5天)，时间为早高峰时段7:30-9:00，数据集需包含4个基本字段，即用户号码、行驶路径、出发时间、到达时间。此外还需获取路网基本属性数据，即路段长度和路段间连接关系，以便计算用户期望到达时间。

拼车匹配模型参数设置如表2所示。

表2拼车匹配模型参数设置表

遗传算法中，染色体长度为各小区参与拼车的用户数量，选择算子采用轮盘赌算子，交叉算子为单点交叉，变异算子为倒位变异。算法参数设置如表3所示。

表3遗传算法参数设置表

通过数据预处理，筛选出早高峰时段固定通勤车辆出行数据共23015条。通过划分小区，统计不同出行规模小区的数量分布如表4所示。

表4不同出行规模小区数量分布表

通过建模和求解，获得城市整体拼车后早高峰出行状况，如表5所示。利用本发明的拼车方法，城市早高峰出行车辆数减少了37％，可以有效缓解交通拥堵，提高车辆的使用率，使整体出行成本达到最小。部分小区早高峰拼车后出行状况如表6所示。

表5整体求解结果

表6部分小区求解结果

分别统计不同出行量小区拼车后的出行车辆数占比，比值越小，说明拼车后出行量越小，拼车效果越好。由图5可知，出行量为0-50之间的小区拼车效果最佳，而此类小区的数量在整个城市中也相对较多；当小区出行量达到100以上时，拼车效果趋于稳定。因此，本发明提出的方法应用于不同出行量规模的小区，都可达到较好的拼车效果，尤其在出行量较小(0-100)的小区拼车效果最佳。

相同或相似的标号对应相同或相似的部件；

附图中描述位置关系的用语仅用于示例性说明，不能理解为对本专利的限制；

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。