1.一种基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,包括以下步骤:S1.推荐乘客去附近的一个路段(ri)上等车,并给出在该位置建议等待的时间S2.若乘客在第一个路段上在给出的等待时间内没有等到空出租车,就推荐乘客走到与该路段相连的路口(c1)去等待,并给出建议等待的时间S3.若乘客在步骤S2所述的路口(c1)没有等到出租车,则继续推荐他走到相邻的路口(c2)上继续等待,如此循环,直至乘客在某个路口(cend)等到空出租车,结束推荐,计算乘客在一个路段或者路口等到空出租车的概率,得到乘客按照推荐路线可以等到出租车的总概率:推荐给乘客的等车路线为:π={ri→c1→c2→c3→…→cend}。
2.根据权利要求1所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,通过设定行走距离阈值(ΔD)和等待时间阈值(ΔT)作为推荐算法的终止条件。
3.根据权利要求2所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,所述行走距离阈值(ΔD)由以下方式得到:推荐乘客到附近的一个路段上等车,之后就推荐乘客去相邻的路口上等车,假设乘客在路段的中间等车,行走距离阈值(ΔD)为路段长度的一半,以保证至少可以推荐一个路口给乘客。
4.根据权利要求2所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,所述等待时间阈值(ΔT)由以下方式得到:不同时间段的等待时间是不同的,选择累积概率到达50%处的时间点作为该时间段内统计的等待时间阈值(ΔT1),这样就保证在50%的路口上的等待时间会小于这个阈值;
同时,乘客在行走的过程中也可能遇到出租车,乘客所行走的时间(ΔT0)也看作是等待时间的一部分,因此,在统计的等待时间阈值里面减去乘客行走所用的时间;
ΔT=ΔT1-ΔT0=ΔT1-ΔD/V0 (1)其中,V0为乘客的行走速度,单位为m/s。
5.根据权利要求1所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,步骤S1中,路段上的等待时间 由以下方式得到:采用非齐次泊松过程(NHPP)来模拟出租车到达的行为,取NHPP的参数为λ(t)=tP,t表示某个时间段,P为对应时间段的空车到达率,它是随不同的时间段而变化的,可以得到事件发生次数的NHPP分布律为:N(t)表示t时间段内到达的空车数量,k表示t时间段内有k辆空车到达;
空出租车的等待时间T在t范围内的概率为:
P{T<=t}=1-P{T>t}
=1-P{N(t)=0}(因为T>t,所以N(t)=0) =1-e-(tP)
=F(t)(即为T的概率分布函数)
求导可以得到概率密度函数:
所以可以求出t的均值:
因此,在t时间段内,在路段上的等待时间为:
6.根据权利要求1所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,步骤S2中,在路口的等待时间:
7.根据权利要求1所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,步骤S3中,所述乘客等到空出租车的概率,即空车到达率,空车到达率在不同时间段内是不同的,对应到马尔科夫决策过程模型中,也就是乘客转移到该位置的回报值,空车到达率从数学角度就是单位时间内一个路段或者路口上的空出租车的数量;
路段上的空车到达率的公式为:
路口上的空车到达率的公式为:
其中,|t|是时间段的长度,在本发明中,取经验值为60min, 表示t时间段内在一个路段到达的空车数量, 表示t时间段内路口到达的空车数量。
8.根据权利要求1所述的基于马尔科夫决策过程的乘客等出租车优化方法,其特征在于,步骤S3中,所述乘客按照推荐路线可以等到出租车的总概率,由以下方式得到:通过求解值函数来选择最优的推荐路线,第一个值函数是Vc(c),它计算以路口(c)为开始路口的路口序列的总回报值,即在该路口序列上乘客可以等到空出租车的总概率;第二个值函数是Vr(r),它计算以路段(r)为开始状态的推荐路线的总回报值,即在该等待路线上乘客可以等到空出租车的总概率;乘客附近可能有若干个路段,因此就会产生若干个推荐路线,本申请最终推给乘客的就是使得Vr(r)最大的推荐路线,因为起始点是路段,接下来介绍如何计算这两个值函数:当一名乘客在路口(c)等待一辆空出租车时,会有两种情况发生:
1)他可以立即等到空车,没有后续的路口序列,因此,
2)否则,推荐他到某个相邻的路口(ci)等待,但我们考虑的不仅仅只有ci一个路口,而是以ci为开始的路口序列,因此,由以上分析可知, (其中,cnext是路口c的
某个相邻路口);
同理, (c是路段r的某个相邻路口)。