一种用于城际网约车的合乘顺路匹配方法及系统与流程

本发明涉及城际网约车，特别涉及一种用于城际网约车的合乘顺路匹配方法及系统。

背景技术：

1、城际网约车作为一种灵活、便捷的出行方式，逐渐受到广大乘客的青睐。然而，在城际网约车服务中，如何高效、准确地为乘客提供合乘方案，一直是行业需要解决的问题。

2、传统的城际网约车合乘匹配方法往往基于简单的几何距离或预设规则进行路径匹配，通常存在诸多缺陷：基于几何距离的匹配方法仅考虑乘客出发地、目的地与车辆路径之间的几何距离，忽略了路径的实际走向和顺路程度，因此，即使乘客的出发地和目的地与车辆路径在几何上接近，也可能因为路径走向不一致而导致合乘效率低下；而基于简单规则的匹配方法通常设定一些简单的规则，如乘客出发地必须在车辆路径的某个范围内，或目的地必须在车辆路径的延伸方向上等，这些规则往往过于僵化，无法适应复杂的城际交通网络，导致匹配准确性低。

技术实现思路

1、基于此，本发明的目的是提出一种用于城际网约车的合乘顺路匹配方法及系统，以解决上述提到的问题。

2、根据本发明提出的一种用于城际网约车的合乘顺路匹配方法，所述方法包括：

3、构建城市区域网格的碱基编码库；

4、基于乘客出发地、目的地及车辆实时路径，生成对应的生物序列并进行双链比对，计算加权匹配度评分；

5、根据路径的加权匹配度评分，通过蚁群算法结合动态信息素机制生成潜在顺路路径候选集；

6、基于潜在顺路路径候选集，结合dijkstra算法生成基础最短路径，并通过生物序列比对筛选高匹配度路径，最终选择路径短程性与顺路匹配度兼顾的最优顺路路径。

7、更进一步的，所述构建城市区域网格的碱基编码库的步骤包括：

8、采集城市多源地理数据，包括poi分布、道路等级及交通流量；

9、将城市区域划分为网格，每个网格分配唯一的4位碱基编码；

10、建立网格坐标与碱基序列的双向映射关系，生成编码库元数据，包含区域功能类型及初始匹配奖励系数。

11、更进一步的，所述计算加权匹配度评分的步骤包括：

12、将乘客出发地编码为正向链序列sstart，目的地编码为负向链序列send，车辆路径编码为参考链序列svehicle；

13、将正向链序列sstart和负向链序列send进行拼接，形成一条完整的双链序列sdouble_chain；

14、通过needleman-wunsch算法对双链序列sdouble_chain和参考链序列svehicle进行双链比对，生成匹配得分矩阵m；

15、根据匹配得分矩阵m，计算原始匹配度r，公式为：

16、

17、其中，mef表示双链序列sdouble_chain的第e个碱基与参考链序列svehicle的第f个碱基的匹配得分，p为双链序列sdouble_chain的碱基数，g为参考链序列svehicle的碱基数，total_bases为双链序列sdouble_chain和参考链序列svehicle的总碱基数；

18、根据原始匹配度r，叠加路径重合奖励系数α，生成加权匹配度评分s，公式为：s＝r×α，其中，α为路径重合奖励系数，用于奖励路径重合度高的匹配。

19、更进一步的，所述通过needleman-wunsch算法对双链序列sdouble_chain和参考链序列svehicle进行双链比对，计算匹配得分矩阵的步骤包括：

20、创建一个(x+1)×(y+1)的得分矩阵h，其中，x为双链序列sdouble_chain的长度，y为参考链序列svehicle的长度；

21、初始化得分矩阵h的第一行和第一列；

22、对于得分矩阵h的每个位置(a，b)，计算比对得分，并对得分矩阵h进行填充，公式为：

23、

24、其中，match_score(sdouble_chai[a]，svehicle[b])为碱基sdouble_chai[a]和svehicle[b]的匹配得分，gap_penalty为空格罚分；

25、从得分矩阵h的右下角开始，回溯得到最优比对路径；

26、根据回溯路径，得到双链序列sdouble_chain和参考链序列svehicle的最优比对结果；

27、根据最优比对结果，构建匹配得分矩阵m，其中，矩阵元素mef表示双链序列sdouble_chain的第e个碱基与参考链序列svehicle的第f个碱基的匹配得分。

28、更进一步的，所述生成潜在顺路路径候选集的步骤包括：

29、为所有路径(i，j)初始化一个相同的信息素浓度τij(0)＝c；

30、根据信息素浓度和启发式信息引导每只蚂蚁选择优质顺路路径；

31、根据蚂蚁在路径上释放的信息素增量和挥发系数，更新每条路径的信息素浓度，公式为：

32、

33、其中，τij(t+1)为下一时刻路径(i，j)的信息素浓度，τij(t)为当前时刻路径(i，j)的信息素浓度，ρ为挥发系数，δτijc为蚂蚁c在路径(i，j)上释放的信息素增量，m为蚂蚁数量，δτijc为蚂蚁k在路径(i，j)上的信息素增量，δτijc＝sc/lc，lc为蚂蚁c对应路径的长度，sc为蚂蚁c对应路径的加权匹配度评分；

34、将所有蚂蚁生成的路径，根据加权匹配度评分s和路径长度l的比值s/l进行排序，选择前n条路径作为候选顺路路径，生成潜在顺路路径候选集。

35、更进一步的，所述基于潜在顺路路径候选集，结合dijkstra算法生成基础最短路径，并通过生物序列比对筛选高匹配度路径，最终选择路径短程性与顺路匹配度兼顾的最优顺路路径的步骤包括：

36、对于潜在顺路路径候选集中的每条候选顺路路径pk，使用dijkstra算法寻找其对应的基础最短路径；

37、在基础最短路径附近生成变异路径群，并通过生物序列比对筛选高匹配度路径；

38、将筛选后的高匹配度路径与候选顺路路径合并，形成综合路径群；

39、通过粒子群优化算法迭代优化综合路径群，输出最优顺路路径。

40、更进一步的，所述对于潜在顺路路径候选集中的每条候选顺路路径pk，使用dijkstra算法寻找其对应的基础最短路径的步骤包括：

41、对于每条候选顺路路径pk，设置路径的起点sk和终点zk；

42、初始化距离数组distk[]，其中，distk[i]表示从路径的起点sk到节点i的最短距离，初始时distk[sk]＝0，其余为无穷大；

43、初始化前驱节点数组prevk[]，用于记录最短路径；

44、从未确定最短距离的节点中选择距离最小的节点u；

45、对于节点u的每个邻接节点v，若distk[u]+auv

46、重复上述过程，直到所有节点的最短距离确定；

47、根据前驱节点数组prevk[]，回溯得到从起点sk和终点zk的基础最短路径。

48、更进一步的，所述在基础最短路径附近生成变异路径群，并通过生物序列比对筛选高匹配度路径的步骤包括：

49、在基础最短路径pshortest，k附近生成一组变异路径；

50、将每条变异路径和基础最短路径pshortest，k分别编码为生物序列；

51、通过needleman-wunsch算法对生物序列进行比对，计算原始匹配度r；

52、根据原始匹配度r，叠加路径重合奖励系数α，生成加权匹配度评分s＝r×α；

53、根据加权匹配度评分s，筛选出高于预设匹配度阈值的高匹配度路径。

54、更进一步的，所述通过粒子群优化算法迭代优化综合路径群，输出最优顺路路径的步骤包括：

55、将综合路径群中的路径作为粒子群的初始位置，并随机初始化粒子速度；

56、车辆行驶过程中，迭代更新粒子速度和位置，以在当前搜索空间中不断探索新的路径，速度更新公式为：

57、vi(t+1)＝wvi(t)+c1r1(pbest，i-xi(t))+c2r2(gbest-xi(t))，

58、位置更新公式为：

59、xi(t+1)＝xi(t)+vi(t+1)，

60、其中，vi(t+1)为粒子i在迭代次数t+1时的速度，vi(t)为粒子i在迭代次数t时的速度，w为惯性权重，c1为个体学习因子，c2为群体学习因子，r1、r2为随机数，pbest，i为粒子i在搜索过程中找到的最优顺路路径，gbest为整个粒子群在搜索过程中找到的最优顺路路径，xi(t+1)为粒子i在迭代次数t+1时的位置，xi(t+1)为粒子i在迭代次数t时的位置；

61、迭代过程中，根据以加权匹配度评分和路径长度的比值定义的适应度函数，评估每条路径的质量，公式为：

62、f＝s/l，

63、其中，f为适应度值，值越大表示路径越优，l为路径长度，s为加权匹配度评分；

64、通过比较不同粒子的适应度值，筛选出更优的路径；

65、迭代完成后，得到最终的最优顺路路径gbest。

66、本发明还提出一种用于城际网约车的合乘顺路匹配系统，用于实现上述的用于城际网约车的合乘顺路匹配方法，所述系统包括：

67、编码库模块：用于构建城市区域网格的碱基编码库；

68、匹配度模块：用于基于乘客出发地、目的地及车辆实时路径，生成对应的生物序列并进行双链比对，计算加权匹配度评分；

69、候选路径模块：用于根据路径的加权匹配度评分，通过蚁群算法结合动态信息素机制生成潜在顺路路径候选集；

70、最优路径模块：用于基于潜在顺路路径候选集，结合dijkstra算法生成基础最短路径，并通过生物序列比对筛选高匹配度路径，最终选择路径短程性与顺路匹配度兼顾的最优顺路路径。

71、综上，本发明的用于城际网约车的合乘顺路匹配方法，通过生物序列比对，将地理位置数据转化为生物序列并进行双链比对，计算加权匹配度评分，以更精确地量化路径之间的顺路程度，从而提高合乘匹配的准确性；然后通过蚁群算法结合动态信息素机制，快速生成潜在顺路路径候选集，避免全局搜索的计算负担；随后，利用dijkstra算法寻找最短路径，并结合生物序列比对筛选高匹配度路径，最终选择路径短程性与顺路匹配度兼顾的最优顺路路径。本发明通过结合碱基编码、双链比对、蚁群优化与dijkstra协同等技术，实现了城际网约车场景下路径短程性与顺路匹配度的量化平衡，能够高效准确地为乘客提供高质量的合乘方案，大大提高了合乘匹配的准确率及路径的质量。

72、本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实施例了解到。