(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211130610.4 (22)申请日 2022.09.16 (71)申请人 暨南大学 地址 510632 广东省广州市天河区黄埔大 道西601号 (72)发明人 郭穗鸣　沈乾榕　陈超　刘志全　 徐恪　 (74)专利代理 机构 广州市华学知识产权代理有 限公司 4 4245 专利代理师 杜柱东 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 30/02(2012.01) G06Q 30/06(2012.01) G06Q 50/30(2012.01)G06F 16/9535(2019.01) G06N 20/00(2019.01) (54)发明名称 基于强化学习和动态定价机制的寻客路径 推荐方法 (57)摘要 本发明公开了一种基于强化学习和动态定 价机制的寻客路径推荐方法， 方法包括S1、 城市 网格划分， 将城市地图平均划分为若干网格； S2、 司机行为建模， 基于马尔可夫决策过程对司机行 为和环境进行建模； S3、 强化学习求解， 对司机 行 为模型， 用Q学习算法求解Q表， 得到最优解； S4、 寻客路径推荐， 根据得到的Q表， 向司机推荐在每 个状态下的最佳行动。 本发明在网格的粒度上为 司机推荐寻客路径， 最大化司机在每小时内的平 均利润率， 在考虑动态定价机制的情况下， 向司 机推荐搜索乘客的路径， 实现更高的利 润。 权利要求书3页 说明书8页 附图2页 CN 115526387 A 2022.12.27 CN 115526387 A 1.基于强化学习和动态定价机制的寻 客路径推荐方法， 其特 征在于， 包括以下步骤： S1、 城市网格划分， 将城市地图平均划分为若干网格； S2、 司机行为建模， 基于马尔可 夫决策过程对司机行为和环境进行建模； S3、 强化学习求 解， 对司机行为模型， 用Q学习算法求 解Q表， 得到最优解； S4、 寻客路径推荐， 根据得到的Q表， 向司机推荐在每 个状态下的最佳 行动。 2.根据权利要求1所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 给定一个城市的网格划分、 智能移动出行服务的GPS轨迹数据库、 订单数据库以及由 司机构成的集合， 对任意一辆空车， 当其到达一个网格时， 向司机推荐下一步的行动， 直至 该司机接载到乘客或当前一小时的时间段结束为止， 寻客路径推荐时考虑最大化司机的利 润率； 向司机推荐下一 步的行动具体为前往某个相邻网格或在当前网格继续 逗留。 3.根据权利要求1所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 步骤S2中， 司机行为建模包括状态和行动定义、 状态跳转定义以及奖励定义； 其中奖 励基于动态定价机制。 4.根据权利要求3所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 状态与行动定义具体为： 采用三个量描述一个状态s＝(l,t,d)， 其中l是司机 的当前位置， t是当前的时间， d是 司机进入当前网格的方向； d一共有10种可能的取值， 即 为司机在当前网格刚放下乘客， 为继续在当 前网格寻 客； 为简化表示， 采用0 至9依次表示d的10种可能取值； 行 动 a 实 际 上 则 是 离 开 当 前 网 格 的 方 向 ， a 一 共 有 9 种 可 能 的 取 值 ， 即 其中， 为继续在当前网格寻客； 为简化表示， 采用1 至9依次表示a的9种可能取值； 如果司机采取 行动a跳转到下一个网格， 则在下一个时刻， 即有d＝10 ‑a。 5.根据权利要求3所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 状态跳转包括两种情况： 成功接载到乘客并运送 乘客到目的地； 没有接载到乘客， 继续进行搜索； 假设司机当前的状态为s0＝(i,ti,di)， 在成功接载到乘客并运送乘客到目的地的情况 中， 司机采取行动后， 到达了相邻的网格j， 驾 驶的距离和时间分别是ddrive(i,j)和tdrive(i, j)； 在网格j中， 司机进行寻客， 驾驶的距离和时间分别是dseek(j)和tseek(j)； 司机在网格j 能接载到乘客的概 率用Ppickup(j)表示， 该乘客的目的地网格为 k的概率用Pdest(j,k)表示； 司机接载到乘客后， 将乘客运送到目的地网格k， 驾驶的距离和时间分别是ddrive(j,k) 和tdrive(j,k)； 乘客到达目的地后， 司机在网格k 刚刚放下乘客， 所以进入网格k的方向为0， 司机到达的下一个 状态是s1＝(k,ti+tdrive(i,j)+tseek(j)+tdrive(j,k),0)。 6.根据权利要求5所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 假设司机当前的状态为s0＝(i,ti,di)， 在没有接载到乘客， 继续进行搜索的情况中，权　利　要　求　书 1/3 页 2 CN 115526387 A 2司机采取 行动a后， 前往相邻的网格j， 驾驶的距离和时间分别是ddrive(i,j)和tdrive(i,j)； 司机随后在网格j寻客， 驾驶的距离和时间分别 是dseek(j)和tseek(j)； 由于司机没能在 网格j接载到乘 客， 概率为1 ‑Ppickup(j)， 因此， 司机此时进入网格j的方向是d＝10 ‑a， 即司机 从原来的状态s0到达了新状态s2＝(j,ti+tdrive(i,j)+tseek(j),10‑a)。 7.根据权利要求6所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 奖励机制包括两种情况， 两种情况分别对应状态跳转的两种情况， 即成功接载到乘 客 并运送乘客到目的地和没有接载到乘客， 继续进行搜索； 在第一种情况中， 奖励分为两 部分： 第一部分为接载乘客从网格j至网格k所获得的收入， 用f(j,k)＝p(j)*(15+2.8ddrive (j,k))表示， 其中， p(j)为乘客在网格j上车时的动态价格系数， 15元为起步价， 且每公里 2.8元， ddrive(j,k)为从网格j至k的行驶距离； 第二部分为司 机在从状态s0跳转到状态s1之间所耗费的油费， 用 ‑β(ddrive(i,j)+dseek (j)+ddrive(j,k))表示， 其中， β 为单位距离的油费； 在该种情况， 司机获得的奖励为： r1＝f(j,k) ‑β(ddrive(i,j)+dseek(j)+ddrive(j,k))； 在第二种情况中， 司机未能接载到乘客， 所以司机的奖励r2为负值， 仅为在从状态s0跳 转到状态s2之间所耗费的油费， 表示 为： r2＝β(ddrive(i,j)+dseek(j))。 8.根据权利要求1所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 强化学习求 解具体包括： S31、 Q表初始化， 将所有的Q 值Q(s,a)置为0； S32、 状态初始化， 初始化司机的状态s＝(linit,t＝0,d＝0)， 其中linit为真实数据中司 机在这个小时开始寻 客所在的网格； S33、 动态价格系数赋值， 根据每个网格中出现不同动态价格系数的概率， 指定每个网 络内的动态价格系数； S34、 以概率∈模拟司机在探索和利用中选择， 探索指司机查询Q表后， 随机选择一种行 动a， 利用指司机查询Q表后， 选择最高Q 值所对应的行动a， ； S35、 当司机做出 行动后， 更新Q值Q(s,a)、 状态s和时间t； S36、 重复步骤S32至步骤S35， 直至步骤S35中Q值更新前后的差的绝对值小于一预设阈 值， Q表收敛， 最后输出Q表。 9.根据权利要求8所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 步骤S3 3具体为： 从真实的智能移动出行服务数据中计算在每个网格中出现不同动态价格系数的概率， 获得每个网格中动态价格系数的实际分布函数； 根据每个网格的动态价格系数的实际分布 函数， 随机指定每 个网格内的动态价格系数。 10.根据权利要求8所述的基于强化学习和动态定价机制的寻客路径推荐方法， 其特征 在于， 步骤S3 5中， 更新 Q值具体为： 更新Q值Q(s,a)： Q(s,a)表示司机在状态s选择行动a所获得的效用， 司机从状态s跳转 到s′， 环境返回奖励r， 则根据Q学习算法， Q(s,a)根据下式进行 更新：权　利　要　求　书 2/3 页 3 CN 115526387 A 3