欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2021107589144
申请人: 南京工程学院
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,包括以下步骤:

步骤一:对道路网络进行建模,基于交叉路口,将道路拆分成路段,并用路段模型,描述出租车司机的状态集、动作集以及乘客路段模型下的基本信息描述;

步骤二:基于出租车历史数据,建立概率模型,描述路段上各时间段司机寻客成功的概率分布情况;

步骤三:考虑拼车的情况下,基于绕路程度的限制,建立司机寻求拼车状态下的可行动作集并求出路段上各时间段司机拼车成功的概率分布情况;

步骤四:考虑司机间的竞争,加入灰色预测模型,结合历史数据挖掘的概率分布情况,求得实时的寻客和拼车成功概率分布情况;

步骤五:将以上各步骤得到的参数等,代入马尔可夫决策过程模型进行策略迭代,得到出租车司机的路线推荐。

2.根据权利要求1所述的基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,所述道路模型包括路段的基本属性,该属性包括长度,起点终点;所述乘客路段模型的属性包括乘客的上车点、下车点、乘客所能忍受的绕路程度;所述出租车模型包括状态集模型、行动集模型。

3.根据权利要求2所述的基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,所述出租车状态集模型的属性包括出租车所处位置、搭载状态集和司机当前所处时间段;出租车行动集模型:以司机当前所在路段为起始轴,当前所在路段终止点为轴心点,顺时针标号,即得到司机在路段roadi所有可选行动集合

4.根据权利要求1所述的基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,在步骤二中寻客成功的概率的计算方法为:通过对各路段分时段的历史数据分析,得到寻客成功的历史概率分布:其中,Xi是表示当前路段、当前时段的打车成功数目的随机变量,i=1、2、...n,n是道路总数;Yj是表示当前时段通过当前路段的空载出租车数目的随机变量,j=1、2、...m,m是…总数; 表示系统在当前路段、当前时段打车成功数目处于状态i的概率, 表示系统在当前时段通过当前路段的空载出租车数目处于状态j的概率。

5.根据权利要求4所述的基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,步骤三的具体步骤分为:

3.1、根据历史数据的处理和分析,来估算每个时段、每个区域的乘客到达不同目的地的概率,即计算乘客在时间段t从roadi出发到roadj的概率Pdestination:其中,n(i,j,t)是历史订单中时间段t从roadi到roadj的总订单数量;n(i,t)是历史订单中时间段t从roadi出发的总订单数量;

3.2、考虑司机已搭载一位乘客之后,欲搭载第二位乘客进行拼车以实现收益最大化的情况,那么引入乘客1和乘客2表示拼车的乘客对象,引入参数α控制司机的绕路程度;一般情况下是先接到乘客1,路途中接到乘客2,再把乘客1,2离终点近的一个先送达再送下一个,即: 记Dmin(i)为接到乘客i到终点的最短路径,Dact(i)为接到乘客i开始,一直到乘客i下车的实际行驶距离,要满足:Dact(i)≤αDmin(i)在接到乘客1后,假设无论是否拼车成功,都是先送乘客1到终点,那么则有:其中, 分别是乘客1的起点和终点,L1.e的定义域为乘客1起点 的邻接路段,求得的可行解为接到乘客后在路段的行动集合Aallowed;对于每一个可行解,求满足Dact(i)≤αDmin(i)的该路段中潜在的乘客2可能的目的地的集合L′1,那么在该路段拼车成功概率为:

Pcoride(k)=Pfind(k)×∑j∈L′Pdestination(k,j,t)即在路段roadi出租车司机找到乘客的概率修正为P=Pcoride;其中,roadk∈L1,Li是乘客i的目的地的集合;

在路段i+1成功拼车,则按上述模式送乘客达到终点,若未成功拼车,在路段roadk有:求得可行解集L2,为司机在路段roadk的行动集合Aallowed,同理求得所有可行解对应的拼车成功概率;

3.3、对于L′1求解:假设接到乘客2, 记乘客1起点(x1,y1)终点(x2,y2),乘客2起点(x3,y3)终点(x4,y4),其中x1,x2,x3,y1,y2,y3均为常数,若k=1,即先送乘客1,则有:

|x3‑x2|+|y3‑y2|+|x4‑x2|+|y4‑y2|≤α(|x4‑x3|+|y4‑y3|)在该状态下,求得x4,y4的可行解集若k=2,即先送乘客2,则有:求得可行解集 那么有

其中,Road为路段集合。

6.根据权利要求5所述的基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,步骤四的具体过程为:(0) 0

4.1、对获得的地理位置数据进行数据处理,使获得的地理位置数表示为:l =(l (1),

0 0

l(2),...l(n))

(0) 0

其中,l 为给定观测数据列,l(n)为经过n次累加所得数据列;

4.2、假设该灰度模型满足基本拟合条件。

GM(1,1)的灰微分方程对应的白微分方程为:得到方程的解为:

其中,c为发展系数,b称作灰作用量;

由此推导出以下预测值:

最终预测值如下:

4.3证明符合该灰度模型,满足拟合条件;

验证:

其中,∈(k)为相对残差,当|∈(k)|<0.1,说明本方法适合该灰度模型,误差较小,若|∈(k)|<0.2,说明基本达到标准;

验证:

其中,p(k)为级比偏差值,λ(k)为序列的水平比,c为发展系数;当|ρ(k)|<0.1,说明其方法适合该模型,误差较小,若|ρ(k)|<0.2,说明其基本达到标准。

7.根据权利要求5所述的基于马尔可夫决策过程的出租车司机寻客路线推荐方法,其特征在于,在步骤五中具体为:

5.1、在司机空载情况下,司机的回报在路段成功搭载乘客的概率,在司机接到一组乘客后,司机的回报拼车成功的概率,则有在路段roadi,司机的状态‑值函数为:最优状态‑值函数:

Vπ(Ltaxi)=max{V(Ri)}其中,take是搭载状态集,表示为take={0,1,2},其中0为空载,1为搭载一组乘客,2为拼车成功,Ltaxi是出租车司机所在位置,Roadi是Ltaxi邻接的路段;π即为推荐的寻客路线;

STOP为迭代计算的一个强制终止条件;

5.2、采用值迭代算法求解马尔可夫决策过程,得到给司机的寻客路线推荐。