一种全局和局部协同的双Q网约车调度方法

本发明涉及一种全局和局部协同的双q网约车调度方法，属于网约车调度。

背景技术：

1、近年来，网约车因其高效、便捷等特性已成为城市居民主要的出行方式之一。其调度算法的设计是一个极具挑战的研究问题。一方面，要同时考虑平台收益，司机收入，用户体验等多个相互矛盾的指标；另一方面，调度决策之间的时序依赖和车单空间分布的动态变化，使算法设计更加复杂。很多研究者尝试使用组合优化算法(例如km算法)或组合优化算法结合强化学习的方法来实现网约车的调度，尽管实现了一定程度的多目标优化同时保障了一定的调度效率，但仍然面临以下4个不足：

2、（1）二分图随机排序导致的结构偏置：在车单规模大、候选空间复杂的情况下，二分图往往存在多种节点候选排序，不同排序对应不同的调度最优解。这些解在当前窗口的即时收益差别不大，但对未来车单分布影响不同，进一步对长期收益的影响差异显著。现有研究构建二分图忽视了这一点，普遍采用随机排序，导致二分图存在结构偏置，输出长期视角下的次优解，无法最大化长期收益。

3、（2）多目标优化与调度效率的冲突：网约车调度需同时兼顾平台收益、司机收入与乘客体验等多个相互冲突的目标。其最长使用的强化学习技术能够提供长期价值建模，但目前常用的探索策略（例如），计算成本过高，同时时间延迟也过大。

4、（3）局部决策与全局决策的兼容性：智能体架构的选择将直接决定强化学习调度模型的性能。完全去中心化会导致智能体之间过度竞争从而收敛到局部最优；完全中心化又会面临状态空间动作空间爆炸；半中心化虽兼具两者优势，但仍需协调局部策略与全局调度。

5、（4）离线预测模型的预测局限导致调度短视：基于历史数据训练的预测模型能够提供供需趋势，但对订单上传时间、起点、终点等随机因素缺乏预测能力，使得前序窗口的最优策略在最新窗口仍存在短视。因此需要一种在线可生效的补偿机制来动态修正前序次优决策。

6、专利“cn120975486a，一种基于动态博弈模型的网约车调度方法及系统”所提出动态博弈模型完成了司乘个性化偏好建模能够平衡司乘双方利益，但是却忽略了网约车调度顺序对长期收益的影响。

7、专利“cn121581350a，基于网约车载客需求位置及热点区域的车辆调度优化方法”所提出的bilstm-gru-attention组合预测模型能够预测订单需求，并以此为基础执行k-means聚类、系统聚类、greedy-nsga-ⅱ算法完成网约车调度，提高了整个网约车系统的服务质量和运营效率。然而预测模型难以预测一些随机因素（例如订单起点、终点），会导致调度策略存在一定短时，从而损害长期收益。

技术实现思路

1、本发明的目的在于提供一种全局和局部协同的双q网约车调度方法，旨在解决现有技术中二分图随机排序导致的结构偏置以及因预测局限导致的调度短视的技术问题。

2、为实现上述目的，本发明的技术方案是：一种全局和局部协同的双q网约车调度方法，包括以下步骤：

3、step1：获取历史车单数据，从所述历史车单数据中抽取车单模式；

4、step2：基于车单模式进行离线环境建模，构建环境模拟器；

5、step3：将路网均分为大小相等的若干个网格，每个网格分配唯一id，根据车辆的实时定位以及订单的起点与终点，将车辆与订单映射到不同网格内；

6、step4：在将车辆与订单映射到不同网格后，使用时序残差网络trn在具有网格id的历史车单数据上离线训练区域价值评估模型与供需预测模型；其中，所述区域价值评估模型用于评估局部调度策略，所述供需预测模型用于评估全局调度策略；

7、step5：从所述环境模拟器实时获取最新车单数据后，执行动态解耦机制，实时滚动修正前序次优调度策略，为每个空闲车辆构建圆形搜索区域，将所述圆形搜索区域内的订单构成每辆车的候选订单集合，并计算不同车辆在所有订单上与其他车辆的竞争强度；

8、step6：按照竞争强度从小到大的顺序对空闲车辆排序，将排序后的空闲车辆作为一侧节点，等待订单作为另一侧节点，从而构建二分图；其中，空闲车辆节点与等待订单节点连线的权重代表当前空闲车辆与等待订单匹配的价值；

9、step7：对车单判定树vodt进行初始化；其中，所述初始化为按照竞争强度从小到大的顺序将空闲车辆依次插入vodt的每一层中作为节点，树的深度等于空闲车辆的数量，节点的分支代表当前车辆的候选订单，分支数量等于候选订单数量，从根节点开始向下遍历车单判定树产生不同路径，对应不同的全局调度策略与全局q值，路径中的每个节点与对应分支代表局部调度策略对应局部q值；

10、step8：利用maql模型迭代更新vodt，并基于二分图利用km算法根据迭代更新后的vodt输出当前迭代轮次最优网约车调度策略，当km算法输出的最优网约车调度策略收敛后，迭代停止，输出最终最优网约车调度策略；其中，maql模型为双q模型，所述双q模型为局部q模型与全局q模型，且maql模型在区域价值评估模型与供需预测模型的指导下以迭代的方式更新vodt，具体为：

11、局部q模型在区域价值评估模型的指导下评估局部调度策略的价值并更新vodt的局部q值，全局q模型在供需预测模型的指导下评估全局调度策略的价值并更新vodt的全局q值。

12、可选地，所述使用时序残差网络trn在具有网格id的历史车单数据上离线训练区域价值评估模型与供需预测模型具体为：

13、

14、

15、其中，与分别为供需预测模型与区域价值评估模型，与为训练函数，用于封装trn对供需预测模型的训练与优化过程，用于封装trn对区域价值评估模型的训练与优化过程，和分别为由环境模拟器产生的实时车辆数据集和订单数据集，代表第个时间窗口，和为trn的可学习参数集合。

16、可选地，所述执行动态解耦机制，实时滚动修正前序次优调度策略具体为：

17、首先，定义动态解耦机制为：当新的车单到达时，调度平台不仅需要对当前时间窗口的车单进行匹配，还应将前序已匹配车单重新纳入匹配空间，对前序次优决策进行滚动校正，实现连续窗口的持续优化；

18、然后，定义动态解耦机制的触发条件为：

19、条件一：车辆当前已匹配订单，且尚未到达已匹配订单的起点；

20、条件二：新订单位于车辆的候选区域中；

21、条件三：新订单的即时利润与未来潜在收益的加权和大于当前已匹配订单；

22、条件四：已匹配订单的剩余容忍时间大于或等于新订单的剩余容忍时间；

23、四个条件均满足则触发动态解耦机制；

24、最后，对于触发了动态解耦机制的新订单与已匹配的车单，依次执行：

25、动作一：解耦已匹配的车单；

26、动作二：匹配车辆与新订单；

27、动作三：将旧订单的状态更新为等待，在下一个时间窗口重新参加调度流程。

28、可选地，所述竞争强度具体为：

29、

30、

31、其中，表示车辆对订单的竞争强度，表示车辆对所有订单的竞争强度；表示车辆的候选订单集合，表示订单的候选车辆集合，代表第个时间窗口，为计算集合长度的函数，表示订单的总数量，表示车辆的总数量。

32、可选地，所述step8具体为：

33、step8.1：将每个空闲车辆作为独立智能体通过km算法做出局部调度策略，将调度平台作为中心智能体通过km算法汇聚所有局部调度策略为一个全局调度策略；

34、step8.2：计算局部调度策略的即时奖励，表达式为：

35、

36、其中，表示第个独立智能体完成订单所需时长，表示折扣因子，表示车单利润；

37、根据即时奖励得到vodt的分支的初始局部q值，表达式为：

38、

39、其中，表示vodt的分支的初始局部q值，表示订单起点网格的即时价值评估，表示订单终点网格在服务周期结束时的未来价值评估，代表第个时间窗口；

40、通过maql模型中的局部q模型在区域价值评估模型的指导下评估局部调度策略的价值并更新vodt的局部q值，表达式为：

41、

42、其中，表示局部q模型，与分别表示第次迭代中，vodt中分支与的局部q值，与为权重，且，表示平衡因子，其中，为衰减系数，用于控制平衡因子的收敛速度，表示分支的探索次数，表示最大迭代次数；

43、step8.3：通过maql模型中的全局q模型在供需预测模型的指导下评估全局调度策略的价值并更新vodt的全局q值，表达式为：

44、

45、其中，表示全局q模型，表示当前时间窗口的供需比例，所述供需比为空闲车辆与等待订单的比例，表示由供需预测模型提供的下一时刻的供需比例。

46、本发明的有益效果是：

47、（1）本发明提出多智能体竞争强度的概念，用于量化车辆调度优先级并构建车单判定树vodt，从而提供结构化策略空间，缓解二分图多最优解带来的结构偏置并加速策略收敛。

48、（2）本发明双向整合了maql与组合优化算法km。maql在离线模型的指导下持续更新判定树vodt，km在树中搜索最优策略并反向更新maql，形成迭代式的“更新-探索-更新”闭环协同流程，实现多目标优化的同时保障在线调度效率。

49、（3）本发明设计了动态解耦机制ddm，从实时计算的角度弥补预测模型的局限性，实现对前序次优匹配的滚动修正。