一种基于智能匹配和路径优化的拼车方法及系统的制作方法
一种基于智能匹配和路径优化的拼车方法及系统的制作方法
【技术领域】
[0001] 本发明涉及公共交通服务技术领域，尤其涉及的是一种基于智能匹配和路径优化 的拼车方法及系统。
【背景技术】
[0002] 在现有技术中，基于互联网的智慧出行方法为利用手机动态收集出行需求，匹配 司机提供的运输服务，实现便捷的交通出行服务。当前，基于互联网的智慧出行包括需求匹 配及路径规划两步。在需求匹配阶段，根据个体出行需求和车辆位置，进行出行需求-运输 服务匹配，并通过司机和客户的APP进行配对确认。在路径规划阶段，根据出行客户的起点 和终点，考虑通行时间、通行距离等因素，设计耗费较低的路线，引导车辆在复杂城市交通 环境中行驶，提高出行舒适度。
[0003 ]拼车出行允许多个出行个体共享运输服务，充分利用车辆的载客量，能够进一步 降低出行费用，减轻相关的交通污染和能源消耗问题。拼车出行中的人-车的时空精准匹配 是关键。然而，当前的人-车匹配解决的是单个出行需求与车辆载客服务之间的配对，采用 人工响应方式进行，质量不高，智能化程度低，且无法处理多个乘客的拼车需求。特别地，城 市交通状态波动显著，决定着乘客与车辆之间的行驶时间，因而，对拼车出行需求匹配有着 重要影响。并且，车辆行驶路线受城市交通状态波动性的约束，存在一定的不确定性，对拼 车出行需求智能匹配及其路径优化提出了更大的挑战。
[0004] 因此，现有技术有待于进一步的改进。
【发明内容】
[0005] 鉴于上述现有技术中的不足之处，本发明的目的在于为用户提供一种基于智能匹 配和路径优化的拼车方法及系统，克服通过采用人工响应方式拼车，智能性差，并且不能实 现根据交通状态进行路径优化的缺陷。
[0006] 本发明解决技术问题所采用的技术方案如下：
[0007] -种基于智能匹配和路径优化的拼车方法，其中，包括：
[0008] A、获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息包括:乘客出 行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆实时位置信 息、车辆乘客个数以及车辆的ID;
[0009] B、计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时 间以及乘客数量创建人车匹配候选集；
[0010] C、建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规 划模型的目标函数的公式为：
[0012]其中，dvp为车辆v到乘客p出发位置所需要空驶的距离；％p为乘客p期望的出发时 间为车辆V到达乘客p处的时间。Xvp为0和1变量，其值为1时表示乘客p的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0013]所述目标函数的约束条件为：
所述tmax为乘客等待时间的预设最大值；
[0015] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0016] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量；
[0017] D、将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者时 变A星算法，得到最佳车辆行驶路径。
[0018] 所述的基于智能匹配和路径优化的拼车方法，其中，所述步骤B中计算各乘客与各 车辆之间的时空距离的公式为：
[0020]其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPy P分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0021 ]所述的基于智能匹配和路径优化的拼车方法，其中，所述步骤B还包括：
[0022] B1、根据计算出的各乘客与各车辆之间的时空距离，生成时空距离矩阵；
[0023] B2、根据所述时空距离矩阵，建立时空临近列表。
[0024]所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤C还包括： [0025] C1、根据生成的时空距离矩阵以及时空临近对优先的原则，依次将人车匹配候选 集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0026] C2、在满足目标函数的约束条件下，改变乘客与车辆的匹配，代入目标函数，得到 行驶路径最优的人车匹配对。
[0027] 所述的基于智能匹配和路径优化的拼车方法，其中，所述步骤C2中包括：
[0028] C21、在满足约束条件下，选择时空邻近的人车对进行探索性操作，结合拼车乘客 的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过预定阀值， 得到空驶距离最少且等待时间最短人车匹配对。
[0029] -种基于智能匹配和路径优化的拼车系统，其中，包括：
[0030] 信息获取模块，用于获取乘客出行信息集合与车辆状态信息集合;所述乘客出行 信息包括:乘客出行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括： 车辆实时位置信息、车辆乘客个数以及车辆的ID;
[0031] 候选集创建模块，用于计算各乘客与各车辆之间的时空距离，并根据计算出的时 空距离、乘客出行时间以及乘客数量创建人车匹配候选集；
[0032] 匹配计算模块，用于建立整数规划模型，根据所述人车匹配候选集得到人车匹配 结果;所述整数规划模型的目标函数的公式为：
[0034]其中，dvp为车辆v到乘客p出发位置所需要空驶的距离；#为乘客p期望的出发时 间。<为车辆V到达乘客P处的时间。Xvt^O和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0035]所述目标函数的约束条件为：
所述tmax为乘客等待时间的预设最大值；
[0037] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0038] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量；
[0039] 最佳路径计算模块，用于将所述人车匹配结果与实时交通状态相结合，利用时变 迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径。
[0040] 所述基于智能匹配和路径优化的拼车系统，其中，所述候选集创建模块中计算各 乘客与各车辆之间的时空距离的公式为：
[0042]其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPyP分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0043]所述基于智能匹配和路径优化的拼车系统，其中，所述候选集创建模块包括：
[0044]距离矩阵生成单元，用于根据计算出的各乘客与各车辆之间的时空距离，生成时 空距离矩阵；
[0045] 临近列表生成单元，用于根据所述时空距离矩阵，建立时空临近列表。
[0046] 所述基于智能匹配和路径优化的拼车系统，其中，所述匹配计算模块包括：
[0047]初始解生成单元，用于根据生成的时空距离矩阵以及时空临近对优先的原则，依 次将人车匹配候选集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0048] 初始解解生成单元，用于在满足目标函数的约束条件下，改变乘客与车辆的匹配， 代入目标函数，得到行驶路径最优的人车匹配对。
[0049] 所述基于智能匹配和路径优化的拼车系统，其中，所述最终解生成单元包括：
[0050] 智能优化子单元，用于在满足约束条件下，选择时空邻近的人车对进行探索性操 作，结合拼车乘客的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次 数超过预定阀值，得到空驶距离最少且等待时间最短的人车匹配对。
[0051] 有益效果，本发明提供了一种基于智能匹配和路径优化的拼车方法及系统，通过 获取乘客出行信息集合与车辆状态信息集合;计算各乘客与各车辆之 间的时空距离，并根 据计算出的时空距离、乘客出行时间以及乘客数量创建人车匹配候选集;建立整数规划模 型，根据所述人车匹配候选集得到人车匹配结果;将所述人车匹配结果与实时交通状态相 结合，利用时变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径，该方法利用动 态交通信息，度量个体出行需求的时空邻近性，采用时空局部性引导群体拼车智能匹配，并 设计耗费最低的动态车辆路径，实现海量出行需求服务时空精准匹配及高效率路径规划。
【附图说明】
[0052] 图1是本发明所提供的一种基于智能匹配和路径优化的拼车方法的步骤流程图。
[0053] 图2是本发明所提供的一种基于智能匹配和路径优化的拼车方法具体实施例示意 图。
[0054] 图3是本发明所提供的一种基于智能匹配和路径优化的拼车方法具体实施例中人 车匹配优化流程示意图。
[0055]图4a和图4b是本发明所提供的所述人车匹配示意图。
[0056]图5是本发明中一种基于智能匹配和路径优化的拼车系统原理结构示意图。
【具体实施方式】
[0057] 为使本发明的目的、技术方案及优点更加清楚、明确，以下参照附图并举实施例对 本发明进一步详细说明。应当理解，此处所描述的具体实施例仅仅用于解释本发明，并不用 于限定本发明。
[0058] 本发明提供了一种基于智能匹配和路径优化的拼车方法，如图1所示，所述方法包 括：
[0059] S1、获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息包括:乘客出 行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆实时位置信 息、车辆乘客个数以及车辆的ID。
[0060] 首先获取乘客的信息和车辆状态信息，并根据所述信息进行相应的拼车处理，具 体的所述乘客的信息包括:乘客所需要乘车出发的地点，乘客乘车的目的地，乘客的个数， 乘客是否接受拼车、以及乘客能接受到最长等待时间等信息。所述车辆状态信息包括:车辆 实时的位置信息，车辆驾驶到乘客所需要乘车出发的地点所需要的时间，车辆上乘客个数， 车辆上乘客是否接受拼车，以及车辆的ID等。
[0061] S2、计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时 间以及乘客数量创建人车匹配候选集。
[0062] 在进行本步骤的计算之前，还包括:先对获取的信息进行初步的过滤，将乘客输入 的乘车时间早于当前时间的数据删除，将乘客乘车时间超出预定阈值的出行需求标记为先 进行保存，所述预定阈值为超出待匹配出行的时间，比如:若乘客乘车时间为第三天的某个 时间，则由于该时间超过当前匹配的最大时间，该最大时间为预定阈值，可以动态的设置为 当天的剩余时间，也可以设置为某一固定时间，比如:5小时内，因此仅当乘客的出行时间在 预定阈值的时间内，才将其列入待匹配列表进行人车匹配。
[0063] 对乘客出发地点与当前车辆所在位置之间的空间距离进行计算，并根据计算结 果，对人车匹配信息进行过滤，将车辆行驶到乘客所在位置所需时间超出预定时间的数据 删除，该预定时间也可以通过车辆与乘客之间的距离来度量，若超出预定距离值，则判定该 车辆与乘客不匹配。
[0064]通过上述时间和距离的过滤后，根据乘客和车辆的其他信息，以及时空临近原则， 将与乘客与距离最近的车辆进行依次匹配，得到初步的人车匹配候选集。
[0065] S3、建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规 划模型的目标函数的公式为：
[0067]其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；g为乘客p期望的出发时 间。尽为车辆V到达乘客P处的时间。Xvt^O和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0068]所述目标函数的约束条件为：
所述tmax为乘客等待时间的预设最大值；
[0070] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0071] ΣΧνρηρ<Μ，其中nP为乘客数量，M为车辆V的最大载客量。
[0072]根据上述目标函数的公式，及其约束条件，按照人车之间距离由近到远的方式，依 次将人车匹配候选集中的信息代入上述目标函数，得到上述目标函数的初始解，并在满足 上述约束条件的前提下，依次改变人车匹配，并代入目标函数，最终获取人车匹配的最佳结 果。
[0073] S4、将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者 时变A星算法，得到最佳车辆行驶路径。
[0074] 将获取的人才匹配的最佳结果推送给乘客和车辆，以得到双方的确认信息后，获 取目前交通信息，为车辆推送最佳的到达乘客乘车地所在位置的最优化路径。所述最优化 路径的算法可以使用现有技术中的迪杰斯特拉算法或者A星算法。
[0075] 具体的，在所述步骤S2中计算各乘客与各车辆之间的时空距离的公式为：
[0077]其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPy P分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0078] 为了所述步骤S2还包括：
[0079] B1、根据计算出的各乘客与各车辆之间的时空距离，生成时空距离矩阵；
[0080] B2、根据所述时空距离矩阵，建立时空临近列表。
[0081 ] 所述步骤S3还包括：
[0082] S31、根据生成的时空距离矩阵以及时空临近对优先的原则，依次将人车匹配候选 集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0083] S32、在满足目标函数的约束条件下，改变乘客与车辆的匹配，代入目标函数，得到 行驶路径最短人车匹配对。
[0084] 所述步骤S32之后，还包括：
[0085] S321、在满足约束条件下，选择时空邻近的人车对进行探索性操作，结合拼车乘客 的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过预定阀值， 得到空驶距离最少且等待时间最短人车匹配对。
[0086] 具体的，首先，按照时空距离所有人车对由近至远排序，依次将数据压入时空临近 列表。然后，初始化乘客为待匹配。接着，依次取出时空临近列表中的人车对所对应的信息， 如果该对中的乘客状态为待匹配，则进一步检查是否接受拼车，若接受拼车，且车辆容量不 超过限制，则将对应车辆指配给该乘客，并标记车辆为已分配;若不接受拼车且车辆状态为 未分配，将对应车辆指配给该乘客，并标记车辆为已分配。
[0087] 利用时空邻近性设计启发式搜索方法，改善初始解质量。具体的步骤为:从时空邻 近性列表不断随机选择一个乘客，在同时满足时间约束、空驶距离约束和乘客数量约束的 条件下，结合人车对之间的方向相似性，反复改变人车对的匹配结果，并匹配出的人车对代 入目标函数，直至当前解的质量不再改善，即结束匹配，即认为获取到的最优的人车匹配 对，所述最优的人车匹配对为:空驶距离最少且等待时间最短人车匹配对。
[0088] 下面以本发明的【具体实施方式】为例，对本发明所述方法做进一步的解释。如图3所 述，所述【具体实施方式】包括以下主要步骤：
[0089] 首先、基于互联网的智慧出行信息收集:通过司机或乘客智能手机上智能应用程 序，控制中心通过移动互联网收集乘客的出行需求信息和车辆实时信息。
[0090] 收集当前时刻乘客出行需求信息，组成出行需求集合0D={〇dl，od2,od3，···， odn}。每个出行需求信息odi包括的内容如前述的出行需求信息。
[0091] 收集车辆实时信息，组成车辆状态集合V={vl，V2，V3，-_，vn}。每个元素 vi的内容 如前述的车辆信息。
[0092] 其次、根据车辆的实时位置信息和乘客的出行需求信息，计算车辆-乘客(ν-ρ)的 时空距离，建立人-车时空邻近 矩阵，度量车辆和乘客之间的时空邻近性。
[0093] (1)时空距离计算公式计算:公式如下：
[0095]其中，Χν和yv分别为车辆当前位置的经炜度，所述XdPy P分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0096] (2)时空距离矩阵生成:利用上述公式，计算每个车辆Dl公里范围内上所有乘客与 所有车辆之间的时空距离。
[0097]优选的，将Dl设置为5公里。遍历所有的车辆，计算所有有效的人-车对的时空距离 dvp，生成时空距离矩阵，其元素为车辆V-乘客P对之间的时空距离，行向量为车辆到Dl范围 内的乘客，所述时空距离矩阵根据下表中的数据信息生成，又由所述时空距离矩阵生成时 空临近列表。
[0099] 再次，根据时空邻近列表，设计时间过滤规则、空间过滤规则等方法，生成较为粗 糙的人-车匹配候选集。
[0100] (1)进行时间过滤:根据当前时刻t和乘客p的出发时刻t。的差异，进行需求过滤。 如果U〈t，出行需求已经无效，直接删除。如果，则离乘客出行需求还有较长时间， 标记出行需求为待匹配。否者，t Q〈=t+tmax，出行需求有效，将其保留在邻近列表中。本发明 中，七_根据经验设置。
[0101] (2)进行空间过滤:根据车辆V和乘客p的空间距离d，进行需求过滤。如果d>cUx， 则离乘客出行需求还有较长时间，标记出行需求为待匹配。否者，cK dmax，出行需求有效，将 其保留在邻近列表中，所述dmax根据经验设置。
[0102] (3)将邻近列表中所有未标记的乘客出行需求作为人车匹配候选集。然后，利用 人-车匹配候选集，结合出行拼车的需求，建立混合整数规划模型，基于时空局部性的启发 式优化进行优化求解，生成高质量的人-车对，实现运输服务和出行需求的精准时空配对。
[0103] 具体的，具体的，如图3所示，本步骤包括：
[0104] (1)人-车对:乘客p的出行需求odp由车辆V完成。一次匹配完成并经过确认后，为 每一个乘客安排唯一的车辆进行服务。由于可以拼车，因此，一个车辆可以和多个乘客配 对。图4a和图4b给出了人-车对的示意图，拼车出行情形如乘客p I、p2拼车vl完成出行。
[0105] (2)建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规 划模型的目标函数的公式为：
[0107] 其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；砹为乘客p期望的出发时 间。《为车辆V到达乘客P处的时间。X vt^O和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0108] 所述目标函数的约束条件为：
I所述tmax为乘客等待时间的预设最大值；
[0110] dvp<dmax，所述dmax为车辆空驶路程的预设最大值；
[0111] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量。
[0112] (3)基于时空邻近性列表，利用时空邻近启发式规则，生成初始解。首先，按照时空 距离将过滤后所有人-车对由近至远排序，将其压入列表。然后，初始化乘客为待匹配。接 着，依次取出列表中的人-车对，如果该对中的乘客状态为待匹配，则进一步检查是否接受 拼车，若接受拼车，且车辆容量不超过限制，则将对应车辆指配给该乘客，并标记车辆为已 分配;若不接受拼车且车辆状态为未分配，将对应车辆指配给该乘客，并标记车辆为已分 配。
[0113] (4)利用时空邻近性设计启发式搜索方法，不断改善初始解质量。不断随机选择一 个乘客，根据时空邻近性列表，在满足时间约束、空驶距离约束和乘客数量约束的条件下， 改变人-车匹配结果，接受那些改善目标值的改变。特别地，根据人车对之间的方向相似性， 改变乘客拼车的匹配。直至当前解的质量不再改善，即结束匹配。
[0114] 最后，将获取到的将人-车匹配结果推送给司机和乘客，要求双方确认。
[0115] 将确认后的人车对，结合动态交通信息，进行动态交通下的最优路径规划。对于单 个的人-车对，考虑动态交通信息，利用Djkstra算法或者时变A星算法，设计总体最优的车 辆时空路径。对于拼车出行的OD对，在最远OD对之间最优路径情况下，最小化路径扰动，从 而规划最佳的车辆时空路径。
[0116] 为了获取更佳的效果，在本步骤中还包括:依据历史交通信息和当前路况，预测到 达乘客出发地点的时间，将预期到达出发地点时间、预期到达目的地时间、司机联系方式等 推送给乘客，将车辆路线、乘客信息、乘客等待位置推送给司机，引导司机完成运输服务。
[0117] 本发明所述方法兼容了单个人-车匹配和多人与车之间的匹配，提供了更加便捷、 高效的交通出行服务，并且本发明所述方法，可以利用移动APP采集出行需求，并实现了实 时的出行需求-出行服务智能匹配。
[0118] 本发明所述方法中基于时空邻近性进行人车匹配，利用方向性加速拼车匹配效 率，实现了拼车出行需求的时空精准匹配优化，解决了匹配质量低下的问题，能够满足实时 性匹配要求，并且解决了实时交通状态波动的问题，提高了面向司机和乘客推荐出行信息 的准确度，改善了出行的舒适程度
[0119] 在上述方法的基础上，本发明还提供了一种基于智能匹配和路径优化的拼车系 统，如图5所示，所述系统包括：
[0120]信息获取模块110,用于获取乘客出行信息集合与车辆状态信息集合;所述乘客出 行信息包括:乘客出行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包 括:车辆实时位置信息、车辆乘客个数以及车辆的ID;
[0121]候选集创建模块120,用于计算各乘客与各车辆之间的时空距离，并根据计算出的 时空距离、乘客出行时间以及乘客数量创建人车匹配候选集；
[0122]匹配计算模块130,用于建立整数规划模型，根据所述人车匹配候选集得到人车匹 配结果;所述整数规划模型的目标函数的公式为：
[0124] 其中，dvp为车辆V到乘客p出发位置所需要空驶的距离； <为乘客p期望的出发时 间。4为车辆V到达乘客P处的时间。ΧηΛ〇和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0125] 所述目标函数的约束条件为：
.所述tmax为乘客等待时间的预设最大值；
[0127] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0128] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量；
[0129] 最佳路径计算模块140,用于将所述人车匹配结果与实时交通状态相结合，利用时 变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径。
[0130] 所述候选集创建模块中计算各乘客与各车辆之间的时空距离的公式为：
[0132] 其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPyP分别为乘客乘车出发位置 的经炜度，t vp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0133] 所述候选集创建模块包括：
[0134] 距离矩阵生成单元，用于根据计算出的各乘客与各车辆之间的时空距离，生成时 空距离矩阵；
[0135] 临近列表生成单元，用于根据所述时空距离矩阵，建立时空临近列表。
[0136] 所述匹配计算模块包括：
[0137] 初始解生成单元，用于根据生成的时空距离矩阵以及时空临近对优先的原则，依 次将人车匹配候选集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0138] 最终解生成单元，用于在满足目标函数的约束条件下，改变乘客与车辆的匹配，代 入目标函数，得到行驶路径最优的人车匹配对。
[0139 ] 所述最终解生成单元包括：
[0140] 智能优化子单元，用于在满足约束条件下，选择时空邻近的人车对进行探索性操 作，结合拼车乘客的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次 数超过预定阀值，得到空驶距离最少且等待时间最短人车匹配对。
[0141] 可以想到的是，上述动态交通信息不局限于本发明介绍中的时变旅行时间，还还 可以是时变旅行速度、交通畅通程度、突发交通管制信息等。时空邻近性度量方法不局限于 本发明介绍的方法，还可以其他邻近性度量方法。本发明中的车辆不仅限于出租车，还包括 私家车、小型客车、大型巴士等。使用智能设备不局限于智能手机，可以使用其他便携式设 备，例如智能手表、智能手环、车载终端等。
[0142] 本发明提供了一种基于智能匹配和路径优化的拼车方法及系统，通过获取乘客出 行信息集合与车辆状态信息集合;计算各乘客与各车辆之间的时空距离，并根据计算出的 时空距离、乘客出行时间以及乘客数量创建人车匹配候选集;建立整数规划模型，根据所述 人车匹配候选集得到人车匹配结果；将所述人车匹配结果与实时交通状态相结合，利用时 变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径，该方法利用动态交通信息， 度量个体出行需求的时空邻近性，采用时空局部性引导群体拼车智能匹配，并设计耗费最 低的动态车辆路径，实现海量出行需求服务时空精准匹配及高效率路径规划。
[0143] 可以理解的是，对本领域普通技术人员来说，可以根据本发明的技术方案及其发 明构思加以等同替换或改变，而所有这些改变或替换都应属于本发明所附的权利要求的保 护范围。
【主权项】
1. 一种基于智能匹配和路径优化的拼车方法，其特征在于，包括： A、 获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息包括:乘客出行时 间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆实时位置信息、车 辆乘客个数以及车辆的ID; B、 计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时间以 及乘客数量创建人车匹配候选集； C、 建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规划模 型的目标函数的公式为：其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；g为乘客p期望的出发时间。< 为车辆V到达乘客P处的时间；XvpSO和1变量，其值为1时表示乘客P的出行由车辆V完成，其 值为0时表示乘客P的出行由其他车辆完成； 所述目标函数的约束条件为：所述tmax为乘客等待时间的预设最大值； dvp<dmax，所述dmax为车辆空驶路程的预设最大值； Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量； D、 将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者时变A 星算法，得到最佳车辆行驶路径。2. 根据权利要求1所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤 B中计算各乘客与各车辆之间的时空距离的公式为：其中，Xv和yv分别为车辆当前位置的经炜度，所述&和^分别为乘客乘车出发位置的经 炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车辆的 平均通行速度。3. 根据权利要求1或2所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述 步骤B还包括： Bl、根据计算出的各乘客与各车辆之间的时空距离，生成时空距离矩阵； B2、根据所述时空距离矩阵建立时空临近列表。4. 根据权利要求3所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤 C还包括： C1、根据生成的时空距离矩阵以及时空临近对优先的原则，依次将人车匹配候选集中 乘客和车辆信息代入目标函数，生成人车初步配对结果； C2、在满足目标函数的约束条件下，智能改变乘客与车辆的匹配，代入目标函数，得到 行驶路径最优的人车匹配对。5. 根据权利要求4所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤 C2中包括： C21、在满足约束条件下，选择时空邻近的人车对进行探索性操作，结合拼车乘客的出 行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过预定阀值，得到 空驶距离最少且等待时间最短人车匹配对。6. -种基于智能匹配和路径优化的拼车系统，其特征在于，包括： 信息获取模块，用于获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息 包括:乘客出行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆 实时位置信息、车辆乘客个数以及车辆的ID; 候选集创建模块，用于计算各乘客与各车辆之间的时空距离，并根据计算出的时空距 离、乘客出行时间以及乘客数量创建人车匹配候选集； 匹配计算模块，用于建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果； 所述整数规划模型的目标函数的公式为：其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；杖为乘客p期望的出发时间；?β ν 为车辆V到达乘客P处的时间；xvPS〇和1变量，其值为1时表示乘客P的出行由车辆V完成，其 值为〇时表示乘客P的出行由其他车辆完成； 所述目标函数的约束条件为：所述tmax为乘客等待时间的预设最大值； dvp<dmax，所述dmax为车辆空驶路程的预设最大值； Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量； 最佳路径计算模块，用于将所述人车匹配结果与实时交通状态相结合，利用时变迪杰 斯特拉算法或者时变A星算法，得到最佳车辆行驶路径。7. 根据权利要求6所述基于智能匹配和路径优化的拼车系统，其特征在于，所述候选集 创建模块中计算各乘客与各车辆之间的时空距离的公式为：其中，Xv和yv分别为车辆当前位置的经炜度，所述&和^分别为乘客乘车出发位置的经 炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车辆的 平均通行速度。8. 根据权利要求7所述基于智能匹配和路径优化的拼车系统，其特征在于，所述候选集 创建模块包括： 距离矩阵生成单元，用于根据计算出的各乘客与各车辆之间的时空距离，生成时空距 离矩阵； 临近列表生成单元，用于根据所述时空距离矩阵，建立时空临近列表。9. 根据权利要求7所述基于智能匹配和路径优化的拼车系统，其特征在于，所述匹配计 算模块包括： 初始解生成单元，用于根据生成的时空距离矩阵以及时空临近对优先的原则，依次将 人车匹配候选集中乘客和车辆信息代入目标函数，并检查约束条件，生成人车初步配对结 果； 最终解生成单元，用于在满足目标函数的约束条件下，智能改变乘客与车辆的匹配，代 入目标函数，得到行驶路径最优的人车匹配对。10.根据权利要求9所述基于智能匹配和路径优化的拼车系统，其特征在于，所述最终 解生成单元包括： 智能优化子单元，用于在满足约束条件下，选择时空邻近的人车对进行探索性操作，结 合拼车乘客的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过 预定阀值，得到空驶距离最少且等待时间最短的人车匹配对。
【专利摘要】本发明提供了一种基于智能匹配和路径优化的拼车方法及系统，通过获取乘客出行信息集合与车辆状态信息集合；计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时间以及乘客数量创建人车匹配候选集；建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果；将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径，该方法利用动态交通信息，度量个体出行需求的时空邻近性，采用时空局部性引导群体拼车智能匹配，并设计耗费最低的动态车辆路径，实现海量出行需求服务时空精准匹配及高效率路径规划。
【IPC分类】G08G1/00, G01C21/34, G08G1/123
【公开号】CN105489002
【申请号】CN201610010115
【发明人】涂伟, 李清泉, 朱家松, 周宝定
【申请人】深圳大学
【公开日】2016年4月13日
【申请日】2016年1月5日
【技术领域】
[0001] 本发明涉及公共交通服务技术领域，尤其涉及的是一种基于智能匹配和路径优化 的拼车方法及系统。
【背景技术】
[0002] 在现有技术中，基于互联网的智慧出行方法为利用手机动态收集出行需求，匹配 司机提供的运输服务，实现便捷的交通出行服务。当前，基于互联网的智慧出行包括需求匹 配及路径规划两步。在需求匹配阶段，根据个体出行需求和车辆位置，进行出行需求-运输 服务匹配，并通过司机和客户的APP进行配对确认。在路径规划阶段，根据出行客户的起点 和终点，考虑通行时间、通行距离等因素，设计耗费较低的路线，引导车辆在复杂城市交通 环境中行驶，提高出行舒适度。
[0003 ]拼车出行允许多个出行个体共享运输服务，充分利用车辆的载客量，能够进一步 降低出行费用，减轻相关的交通污染和能源消耗问题。拼车出行中的人-车的时空精准匹配 是关键。然而，当前的人-车匹配解决的是单个出行需求与车辆载客服务之间的配对，采用 人工响应方式进行，质量不高，智能化程度低，且无法处理多个乘客的拼车需求。特别地，城 市交通状态波动显著，决定着乘客与车辆之间的行驶时间，因而，对拼车出行需求匹配有着 重要影响。并且，车辆行驶路线受城市交通状态波动性的约束，存在一定的不确定性，对拼 车出行需求智能匹配及其路径优化提出了更大的挑战。
[0004] 因此，现有技术有待于进一步的改进。
【发明内容】
[0005] 鉴于上述现有技术中的不足之处，本发明的目的在于为用户提供一种基于智能匹 配和路径优化的拼车方法及系统，克服通过采用人工响应方式拼车，智能性差，并且不能实 现根据交通状态进行路径优化的缺陷。
[0006] 本发明解决技术问题所采用的技术方案如下：
[0007] -种基于智能匹配和路径优化的拼车方法，其中，包括：
[0008] A、获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息包括:乘客出 行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆实时位置信 息、车辆乘客个数以及车辆的ID;
[0009] B、计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时 间以及乘客数量创建人车匹配候选集；
[0010] C、建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规 划模型的目标函数的公式为：
[0012]其中，dvp为车辆v到乘客p出发位置所需要空驶的距离；％p为乘客p期望的出发时 间为车辆V到达乘客p处的时间。Xvp为0和1变量，其值为1时表示乘客p的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0013]所述目标函数的约束条件为：
所述tmax为乘客等待时间的预设最大值；
[0015] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0016] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量；
[0017] D、将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者时 变A星算法，得到最佳车辆行驶路径。
[0018] 所述的基于智能匹配和路径优化的拼车方法，其中，所述步骤B中计算各乘客与各 车辆之间的时空距离的公式为：
[0020]其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPy P分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0021 ]所述的基于智能匹配和路径优化的拼车方法，其中，所述步骤B还包括：
[0022] B1、根据计算出的各乘客与各车辆之间的时空距离，生成时空距离矩阵；
[0023] B2、根据所述时空距离矩阵，建立时空临近列表。
[0024]所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤C还包括： [0025] C1、根据生成的时空距离矩阵以及时空临近对优先的原则，依次将人车匹配候选 集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0026] C2、在满足目标函数的约束条件下，改变乘客与车辆的匹配，代入目标函数，得到 行驶路径最优的人车匹配对。
[0027] 所述的基于智能匹配和路径优化的拼车方法，其中，所述步骤C2中包括：
[0028] C21、在满足约束条件下，选择时空邻近的人车对进行探索性操作，结合拼车乘客 的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过预定阀值， 得到空驶距离最少且等待时间最短人车匹配对。
[0029] -种基于智能匹配和路径优化的拼车系统，其中，包括：
[0030] 信息获取模块，用于获取乘客出行信息集合与车辆状态信息集合;所述乘客出行 信息包括:乘客出行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括： 车辆实时位置信息、车辆乘客个数以及车辆的ID;
[0031] 候选集创建模块，用于计算各乘客与各车辆之间的时空距离，并根据计算出的时 空距离、乘客出行时间以及乘客数量创建人车匹配候选集；
[0032] 匹配计算模块，用于建立整数规划模型，根据所述人车匹配候选集得到人车匹配 结果;所述整数规划模型的目标函数的公式为：
[0034]其中，dvp为车辆v到乘客p出发位置所需要空驶的距离；#为乘客p期望的出发时 间。<为车辆V到达乘客P处的时间。Xvt^O和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0035]所述目标函数的约束条件为：
所述tmax为乘客等待时间的预设最大值；
[0037] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0038] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量；
[0039] 最佳路径计算模块，用于将所述人车匹配结果与实时交通状态相结合，利用时变 迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径。
[0040] 所述基于智能匹配和路径优化的拼车系统，其中，所述候选集创建模块中计算各 乘客与各车辆之间的时空距离的公式为：
[0042]其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPyP分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0043]所述基于智能匹配和路径优化的拼车系统，其中，所述候选集创建模块包括：
[0044]距离矩阵生成单元，用于根据计算出的各乘客与各车辆之间的时空距离，生成时 空距离矩阵；
[0045] 临近列表生成单元，用于根据所述时空距离矩阵，建立时空临近列表。
[0046] 所述基于智能匹配和路径优化的拼车系统，其中，所述匹配计算模块包括：
[0047]初始解生成单元，用于根据生成的时空距离矩阵以及时空临近对优先的原则，依 次将人车匹配候选集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0048] 初始解解生成单元，用于在满足目标函数的约束条件下，改变乘客与车辆的匹配， 代入目标函数，得到行驶路径最优的人车匹配对。
[0049] 所述基于智能匹配和路径优化的拼车系统，其中，所述最终解生成单元包括：
[0050] 智能优化子单元，用于在满足约束条件下，选择时空邻近的人车对进行探索性操 作，结合拼车乘客的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次 数超过预定阀值，得到空驶距离最少且等待时间最短的人车匹配对。
[0051] 有益效果，本发明提供了一种基于智能匹配和路径优化的拼车方法及系统，通过 获取乘客出行信息集合与车辆状态信息集合;计算各乘客与各车辆之 间的时空距离，并根 据计算出的时空距离、乘客出行时间以及乘客数量创建人车匹配候选集;建立整数规划模 型，根据所述人车匹配候选集得到人车匹配结果;将所述人车匹配结果与实时交通状态相 结合，利用时变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径，该方法利用动 态交通信息，度量个体出行需求的时空邻近性，采用时空局部性引导群体拼车智能匹配，并 设计耗费最低的动态车辆路径，实现海量出行需求服务时空精准匹配及高效率路径规划。
【附图说明】
[0052] 图1是本发明所提供的一种基于智能匹配和路径优化的拼车方法的步骤流程图。
[0053] 图2是本发明所提供的一种基于智能匹配和路径优化的拼车方法具体实施例示意 图。
[0054] 图3是本发明所提供的一种基于智能匹配和路径优化的拼车方法具体实施例中人 车匹配优化流程示意图。
[0055]图4a和图4b是本发明所提供的所述人车匹配示意图。
[0056]图5是本发明中一种基于智能匹配和路径优化的拼车系统原理结构示意图。
【具体实施方式】
[0057] 为使本发明的目的、技术方案及优点更加清楚、明确，以下参照附图并举实施例对 本发明进一步详细说明。应当理解，此处所描述的具体实施例仅仅用于解释本发明，并不用 于限定本发明。
[0058] 本发明提供了一种基于智能匹配和路径优化的拼车方法，如图1所示，所述方法包 括：
[0059] S1、获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息包括:乘客出 行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆实时位置信 息、车辆乘客个数以及车辆的ID。
[0060] 首先获取乘客的信息和车辆状态信息，并根据所述信息进行相应的拼车处理，具 体的所述乘客的信息包括:乘客所需要乘车出发的地点，乘客乘车的目的地，乘客的个数， 乘客是否接受拼车、以及乘客能接受到最长等待时间等信息。所述车辆状态信息包括:车辆 实时的位置信息，车辆驾驶到乘客所需要乘车出发的地点所需要的时间，车辆上乘客个数， 车辆上乘客是否接受拼车，以及车辆的ID等。
[0061] S2、计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时 间以及乘客数量创建人车匹配候选集。
[0062] 在进行本步骤的计算之前，还包括:先对获取的信息进行初步的过滤，将乘客输入 的乘车时间早于当前时间的数据删除，将乘客乘车时间超出预定阈值的出行需求标记为先 进行保存，所述预定阈值为超出待匹配出行的时间，比如:若乘客乘车时间为第三天的某个 时间，则由于该时间超过当前匹配的最大时间，该最大时间为预定阈值，可以动态的设置为 当天的剩余时间，也可以设置为某一固定时间，比如:5小时内，因此仅当乘客的出行时间在 预定阈值的时间内，才将其列入待匹配列表进行人车匹配。
[0063] 对乘客出发地点与当前车辆所在位置之间的空间距离进行计算，并根据计算结 果，对人车匹配信息进行过滤，将车辆行驶到乘客所在位置所需时间超出预定时间的数据 删除，该预定时间也可以通过车辆与乘客之间的距离来度量，若超出预定距离值，则判定该 车辆与乘客不匹配。
[0064]通过上述时间和距离的过滤后，根据乘客和车辆的其他信息，以及时空临近原则， 将与乘客与距离最近的车辆进行依次匹配，得到初步的人车匹配候选集。
[0065] S3、建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规 划模型的目标函数的公式为：
[0067]其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；g为乘客p期望的出发时 间。尽为车辆V到达乘客P处的时间。Xvt^O和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0068]所述目标函数的约束条件为：
所述tmax为乘客等待时间的预设最大值；
[0070] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0071] ΣΧνρηρ<Μ，其中nP为乘客数量，M为车辆V的最大载客量。
[0072]根据上述目标函数的公式，及其约束条件，按照人车之间距离由近到远的方式，依 次将人车匹配候选集中的信息代入上述目标函数，得到上述目标函数的初始解，并在满足 上述约束条件的前提下，依次改变人车匹配，并代入目标函数，最终获取人车匹配的最佳结 果。
[0073] S4、将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者 时变A星算法，得到最佳车辆行驶路径。
[0074] 将获取的人才匹配的最佳结果推送给乘客和车辆，以得到双方的确认信息后，获 取目前交通信息，为车辆推送最佳的到达乘客乘车地所在位置的最优化路径。所述最优化 路径的算法可以使用现有技术中的迪杰斯特拉算法或者A星算法。
[0075] 具体的，在所述步骤S2中计算各乘客与各车辆之间的时空距离的公式为：
[0077]其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPy P分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0078] 为了所述步骤S2还包括：
[0079] B1、根据计算出的各乘客与各车辆之间的时空距离，生成时空距离矩阵；
[0080] B2、根据所述时空距离矩阵，建立时空临近列表。
[0081 ] 所述步骤S3还包括：
[0082] S31、根据生成的时空距离矩阵以及时空临近对优先的原则，依次将人车匹配候选 集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0083] S32、在满足目标函数的约束条件下，改变乘客与车辆的匹配，代入目标函数，得到 行驶路径最短人车匹配对。
[0084] 所述步骤S32之后，还包括：
[0085] S321、在满足约束条件下，选择时空邻近的人车对进行探索性操作，结合拼车乘客 的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过预定阀值， 得到空驶距离最少且等待时间最短人车匹配对。
[0086] 具体的，首先，按照时空距离所有人车对由近至远排序，依次将数据压入时空临近 列表。然后，初始化乘客为待匹配。接着，依次取出时空临近列表中的人车对所对应的信息， 如果该对中的乘客状态为待匹配，则进一步检查是否接受拼车，若接受拼车，且车辆容量不 超过限制，则将对应车辆指配给该乘客，并标记车辆为已分配;若不接受拼车且车辆状态为 未分配，将对应车辆指配给该乘客，并标记车辆为已分配。
[0087] 利用时空邻近性设计启发式搜索方法，改善初始解质量。具体的步骤为:从时空邻 近性列表不断随机选择一个乘客，在同时满足时间约束、空驶距离约束和乘客数量约束的 条件下，结合人车对之间的方向相似性，反复改变人车对的匹配结果，并匹配出的人车对代 入目标函数，直至当前解的质量不再改善，即结束匹配，即认为获取到的最优的人车匹配 对，所述最优的人车匹配对为:空驶距离最少且等待时间最短人车匹配对。
[0088] 下面以本发明的【具体实施方式】为例，对本发明所述方法做进一步的解释。如图3所 述，所述【具体实施方式】包括以下主要步骤：
[0089] 首先、基于互联网的智慧出行信息收集:通过司机或乘客智能手机上智能应用程 序，控制中心通过移动互联网收集乘客的出行需求信息和车辆实时信息。
[0090] 收集当前时刻乘客出行需求信息，组成出行需求集合0D={〇dl，od2,od3，···， odn}。每个出行需求信息odi包括的内容如前述的出行需求信息。
[0091] 收集车辆实时信息，组成车辆状态集合V={vl，V2，V3，-_，vn}。每个元素 vi的内容 如前述的车辆信息。
[0092] 其次、根据车辆的实时位置信息和乘客的出行需求信息，计算车辆-乘客(ν-ρ)的 时空距离，建立人-车时空邻近 矩阵，度量车辆和乘客之间的时空邻近性。
[0093] (1)时空距离计算公式计算:公式如下：
[0095]其中，Χν和yv分别为车辆当前位置的经炜度，所述XdPy P分别为乘客乘车出发位置 的经炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0096] (2)时空距离矩阵生成:利用上述公式，计算每个车辆Dl公里范围内上所有乘客与 所有车辆之间的时空距离。
[0097]优选的，将Dl设置为5公里。遍历所有的车辆，计算所有有效的人-车对的时空距离 dvp，生成时空距离矩阵，其元素为车辆V-乘客P对之间的时空距离，行向量为车辆到Dl范围 内的乘客，所述时空距离矩阵根据下表中的数据信息生成，又由所述时空距离矩阵生成时 空临近列表。
[0099] 再次，根据时空邻近列表，设计时间过滤规则、空间过滤规则等方法，生成较为粗 糙的人-车匹配候选集。
[0100] (1)进行时间过滤:根据当前时刻t和乘客p的出发时刻t。的差异，进行需求过滤。 如果U〈t，出行需求已经无效，直接删除。如果，则离乘客出行需求还有较长时间， 标记出行需求为待匹配。否者，t Q〈=t+tmax，出行需求有效，将其保留在邻近列表中。本发明 中，七_根据经验设置。
[0101] (2)进行空间过滤:根据车辆V和乘客p的空间距离d，进行需求过滤。如果d>cUx， 则离乘客出行需求还有较长时间，标记出行需求为待匹配。否者，cK dmax，出行需求有效，将 其保留在邻近列表中，所述dmax根据经验设置。
[0102] (3)将邻近列表中所有未标记的乘客出行需求作为人车匹配候选集。然后，利用 人-车匹配候选集，结合出行拼车的需求，建立混合整数规划模型，基于时空局部性的启发 式优化进行优化求解，生成高质量的人-车对，实现运输服务和出行需求的精准时空配对。
[0103] 具体的，具体的，如图3所示，本步骤包括：
[0104] (1)人-车对:乘客p的出行需求odp由车辆V完成。一次匹配完成并经过确认后，为 每一个乘客安排唯一的车辆进行服务。由于可以拼车，因此，一个车辆可以和多个乘客配 对。图4a和图4b给出了人-车对的示意图，拼车出行情形如乘客p I、p2拼车vl完成出行。
[0105] (2)建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规 划模型的目标函数的公式为：
[0107] 其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；砹为乘客p期望的出发时 间。《为车辆V到达乘客P处的时间。X vt^O和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0108] 所述目标函数的约束条件为：
I所述tmax为乘客等待时间的预设最大值；
[0110] dvp<dmax，所述dmax为车辆空驶路程的预设最大值；
[0111] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量。
[0112] (3)基于时空邻近性列表，利用时空邻近启发式规则，生成初始解。首先，按照时空 距离将过滤后所有人-车对由近至远排序，将其压入列表。然后，初始化乘客为待匹配。接 着，依次取出列表中的人-车对，如果该对中的乘客状态为待匹配，则进一步检查是否接受 拼车，若接受拼车，且车辆容量不超过限制，则将对应车辆指配给该乘客，并标记车辆为已 分配;若不接受拼车且车辆状态为未分配，将对应车辆指配给该乘客，并标记车辆为已分 配。
[0113] (4)利用时空邻近性设计启发式搜索方法，不断改善初始解质量。不断随机选择一 个乘客，根据时空邻近性列表，在满足时间约束、空驶距离约束和乘客数量约束的条件下， 改变人-车匹配结果，接受那些改善目标值的改变。特别地，根据人车对之间的方向相似性， 改变乘客拼车的匹配。直至当前解的质量不再改善，即结束匹配。
[0114] 最后，将获取到的将人-车匹配结果推送给司机和乘客，要求双方确认。
[0115] 将确认后的人车对，结合动态交通信息，进行动态交通下的最优路径规划。对于单 个的人-车对，考虑动态交通信息，利用Djkstra算法或者时变A星算法，设计总体最优的车 辆时空路径。对于拼车出行的OD对，在最远OD对之间最优路径情况下，最小化路径扰动，从 而规划最佳的车辆时空路径。
[0116] 为了获取更佳的效果，在本步骤中还包括:依据历史交通信息和当前路况，预测到 达乘客出发地点的时间，将预期到达出发地点时间、预期到达目的地时间、司机联系方式等 推送给乘客，将车辆路线、乘客信息、乘客等待位置推送给司机，引导司机完成运输服务。
[0117] 本发明所述方法兼容了单个人-车匹配和多人与车之间的匹配，提供了更加便捷、 高效的交通出行服务，并且本发明所述方法，可以利用移动APP采集出行需求，并实现了实 时的出行需求-出行服务智能匹配。
[0118] 本发明所述方法中基于时空邻近性进行人车匹配，利用方向性加速拼车匹配效 率，实现了拼车出行需求的时空精准匹配优化，解决了匹配质量低下的问题，能够满足实时 性匹配要求，并且解决了实时交通状态波动的问题，提高了面向司机和乘客推荐出行信息 的准确度，改善了出行的舒适程度
[0119] 在上述方法的基础上，本发明还提供了一种基于智能匹配和路径优化的拼车系 统，如图5所示，所述系统包括：
[0120]信息获取模块110,用于获取乘客出行信息集合与车辆状态信息集合;所述乘客出 行信息包括:乘客出行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包 括:车辆实时位置信息、车辆乘客个数以及车辆的ID;
[0121]候选集创建模块120,用于计算各乘客与各车辆之间的时空距离，并根据计算出的 时空距离、乘客出行时间以及乘客数量创建人车匹配候选集；
[0122]匹配计算模块130,用于建立整数规划模型，根据所述人车匹配候选集得到人车匹 配结果;所述整数规划模型的目标函数的公式为：
[0124] 其中，dvp为车辆V到乘客p出发位置所需要空驶的距离； <为乘客p期望的出发时 间。4为车辆V到达乘客P处的时间。ΧηΛ〇和1变量，其值为1时表示乘客P的出行由车辆V完 成，其值为〇时表示乘客P的出行由其他车辆完成；
[0125] 所述目标函数的约束条件为：
.所述tmax为乘客等待时间的预设最大值；
[0127] dvp <dmax，所述dmax为车辆空驶路程的预设最大值；
[0128] Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量；
[0129] 最佳路径计算模块140,用于将所述人车匹配结果与实时交通状态相结合，利用时 变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径。
[0130] 所述候选集创建模块中计算各乘客与各车辆之间的时空距离的公式为：
[0132] 其中，Xv和yv分别为车辆当前位置的经炜度，所述XdPyP分别为乘客乘车出发位置 的经炜度，t vp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车 辆的平均通行速度。
[0133] 所述候选集创建模块包括：
[0134] 距离矩阵生成单元，用于根据计算出的各乘客与各车辆之间的时空距离，生成时 空距离矩阵；
[0135] 临近列表生成单元，用于根据所述时空距离矩阵，建立时空临近列表。
[0136] 所述匹配计算模块包括：
[0137] 初始解生成单元，用于根据生成的时空距离矩阵以及时空临近对优先的原则，依 次将人车匹配候选集中乘客和车辆信息代入目标函数，生成人车初步配对结果；
[0138] 最终解生成单元，用于在满足目标函数的约束条件下，改变乘客与车辆的匹配，代 入目标函数，得到行驶路径最优的人车匹配对。
[0139 ] 所述最终解生成单元包括：
[0140] 智能优化子单元，用于在满足约束条件下，选择时空邻近的人车对进行探索性操 作，结合拼车乘客的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次 数超过预定阀值，得到空驶距离最少且等待时间最短人车匹配对。
[0141] 可以想到的是，上述动态交通信息不局限于本发明介绍中的时变旅行时间，还还 可以是时变旅行速度、交通畅通程度、突发交通管制信息等。时空邻近性度量方法不局限于 本发明介绍的方法，还可以其他邻近性度量方法。本发明中的车辆不仅限于出租车，还包括 私家车、小型客车、大型巴士等。使用智能设备不局限于智能手机，可以使用其他便携式设 备，例如智能手表、智能手环、车载终端等。
[0142] 本发明提供了一种基于智能匹配和路径优化的拼车方法及系统，通过获取乘客出 行信息集合与车辆状态信息集合;计算各乘客与各车辆之间的时空距离，并根据计算出的 时空距离、乘客出行时间以及乘客数量创建人车匹配候选集;建立整数规划模型，根据所述 人车匹配候选集得到人车匹配结果；将所述人车匹配结果与实时交通状态相结合，利用时 变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径，该方法利用动态交通信息， 度量个体出行需求的时空邻近性，采用时空局部性引导群体拼车智能匹配，并设计耗费最 低的动态车辆路径，实现海量出行需求服务时空精准匹配及高效率路径规划。
[0143] 可以理解的是，对本领域普通技术人员来说，可以根据本发明的技术方案及其发 明构思加以等同替换或改变，而所有这些改变或替换都应属于本发明所附的权利要求的保 护范围。
【主权项】
1. 一种基于智能匹配和路径优化的拼车方法，其特征在于，包括： A、 获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息包括:乘客出行时 间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆实时位置信息、车 辆乘客个数以及车辆的ID; B、 计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时间以 及乘客数量创建人车匹配候选集； C、 建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果;所述整数规划模 型的目标函数的公式为：其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；g为乘客p期望的出发时间。< 为车辆V到达乘客P处的时间；XvpSO和1变量，其值为1时表示乘客P的出行由车辆V完成，其 值为0时表示乘客P的出行由其他车辆完成； 所述目标函数的约束条件为：所述tmax为乘客等待时间的预设最大值； dvp<dmax，所述dmax为车辆空驶路程的预设最大值； Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量； D、 将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者时变A 星算法，得到最佳车辆行驶路径。2. 根据权利要求1所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤 B中计算各乘客与各车辆之间的时空距离的公式为：其中，Xv和yv分别为车辆当前位置的经炜度，所述&和^分别为乘客乘车出发位置的经 炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车辆的 平均通行速度。3. 根据权利要求1或2所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述 步骤B还包括： Bl、根据计算出的各乘客与各车辆之间的时空距离，生成时空距离矩阵； B2、根据所述时空距离矩阵建立时空临近列表。4. 根据权利要求3所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤 C还包括： C1、根据生成的时空距离矩阵以及时空临近对优先的原则，依次将人车匹配候选集中 乘客和车辆信息代入目标函数，生成人车初步配对结果； C2、在满足目标函数的约束条件下，智能改变乘客与车辆的匹配，代入目标函数，得到 行驶路径最优的人车匹配对。5. 根据权利要求4所述的基于智能匹配和路径优化的拼车方法，其特征在于，所述步骤 C2中包括： C21、在满足约束条件下，选择时空邻近的人车对进行探索性操作，结合拼车乘客的出 行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过预定阀值，得到 空驶距离最少且等待时间最短人车匹配对。6. -种基于智能匹配和路径优化的拼车系统，其特征在于，包括： 信息获取模块，用于获取乘客出行信息集合与车辆状态信息集合;所述乘客出行信息 包括:乘客出行时间、乘客出发地、乘客目的地以及乘客个数;所述车辆状态信息包括:车辆 实时位置信息、车辆乘客个数以及车辆的ID; 候选集创建模块，用于计算各乘客与各车辆之间的时空距离，并根据计算出的时空距 离、乘客出行时间以及乘客数量创建人车匹配候选集； 匹配计算模块，用于建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果； 所述整数规划模型的目标函数的公式为：其中，dvp为车辆V到乘客p出发位置所需要空驶的距离；杖为乘客p期望的出发时间；?β ν 为车辆V到达乘客P处的时间；xvPS〇和1变量，其值为1时表示乘客P的出行由车辆V完成，其 值为〇时表示乘客P的出行由其他车辆完成； 所述目标函数的约束条件为：所述tmax为乘客等待时间的预设最大值； dvp<dmax，所述dmax为车辆空驶路程的预设最大值； Σ Xvpnp < M，其中nP为乘客数量，M为车辆V的最大载客量； 最佳路径计算模块，用于将所述人车匹配结果与实时交通状态相结合，利用时变迪杰 斯特拉算法或者时变A星算法，得到最佳车辆行驶路径。7. 根据权利要求6所述基于智能匹配和路径优化的拼车系统，其特征在于，所述候选集 创建模块中计算各乘客与各车辆之间的时空距离的公式为：其中，Xv和yv分别为车辆当前位置的经炜度，所述&和^分别为乘客乘车出发位置的经 炜度，tvp为车辆从当前时刻开始到达乘客乘车出发处所需要的时间，V为当前道路上车辆的 平均通行速度。8. 根据权利要求7所述基于智能匹配和路径优化的拼车系统，其特征在于，所述候选集 创建模块包括： 距离矩阵生成单元，用于根据计算出的各乘客与各车辆之间的时空距离，生成时空距 离矩阵； 临近列表生成单元，用于根据所述时空距离矩阵，建立时空临近列表。9. 根据权利要求7所述基于智能匹配和路径优化的拼车系统，其特征在于，所述匹配计 算模块包括： 初始解生成单元，用于根据生成的时空距离矩阵以及时空临近对优先的原则，依次将 人车匹配候选集中乘客和车辆信息代入目标函数，并检查约束条件，生成人车初步配对结 果； 最终解生成单元，用于在满足目标函数的约束条件下，智能改变乘客与车辆的匹配，代 入目标函数，得到行驶路径最优的人车匹配对。10.根据权利要求9所述基于智能匹配和路径优化的拼车系统，其特征在于，所述最终 解生成单元包括： 智能优化子单元，用于在满足约束条件下，选择时空邻近的人车对进行探索性操作，结 合拼车乘客的出行方向性，改变乘客与车辆的匹配，不断优化目标函数，直至迭代次数超过 预定阀值，得到空驶距离最少且等待时间最短的人车匹配对。
【专利摘要】本发明提供了一种基于智能匹配和路径优化的拼车方法及系统，通过获取乘客出行信息集合与车辆状态信息集合；计算各乘客与各车辆之间的时空距离，并根据计算出的时空距离、乘客出行时间以及乘客数量创建人车匹配候选集；建立整数规划模型，根据所述人车匹配候选集得到人车匹配结果；将所述人车匹配结果与实时交通状态相结合，利用时变迪杰斯特拉算法或者时变A星算法，得到最佳车辆行驶路径，该方法利用动态交通信息，度量个体出行需求的时空邻近性，采用时空局部性引导群体拼车智能匹配，并设计耗费最低的动态车辆路径，实现海量出行需求服务时空精准匹配及高效率路径规划。
【IPC分类】G08G1/00, G01C21/34, G08G1/123
【公开号】CN105489002
【申请号】CN201610010115
【发明人】涂伟, 李清泉, 朱家松, 周宝定
【申请人】深圳大学
【公开日】2016年4月13日
【申请日】2016年1月5日
最新回复(0)