基于GPS大数据的出租车高效益智能集体调度算法

摘要

一种基于GPS大数据的出租车高效益智能集体调度算法。它包括：(1)从GPS大数据中获取出租车的行驶数据以及财务数据，将行驶轨迹与对应的财务信息相匹配；(2)对城市的地理区域进行网格划分；(3)将GPS大数据中出租车发生交易的地域与各网格相匹配，得到各网格内的乘客分布估计；(4)计算出租车公司在t时刻调度出租车的调度成本；(5)令出租车分布与乘客分布估计相一致；(6)以调度成本最低作为全局完成调度目标的最优策略，获得集体策略规划模型。本发明的出租车调度算法使城市内出租车分布与乘客需求达到供需平衡，并兼顾调度成本，形成具有高效益、高运力的出租车调度模型，实现经济效益和社会效益的综合提升。

权利要求

1.一种基于GPS大数据的出租车高效益智能集体调度算法，其特征在于，包括以下步骤：步骤1)数据预处理：从GPS大数据中获取出租车的行驶数据以及财务数据，根据出租车标识在所述行驶数据以及财务数据中将行驶轨迹与对应的财务信息相匹配；

步骤2)区域划分：对城市的地理区域进行网格划分并将网格记为(i，j)，i＝1，2…m，j＝1，2，…n；

步骤3)将GPS大数据中出租车发生交易的地域与各网格相匹配，得到所有网格内在t时段关于空间上的乘客分布估计：其中，N为所有的乘车记录总数；Nij(t)为在t时段内，第(i，j)个网格发生的总乘车记录数；

步骤4)计算出租车公司在t时刻调度出租车的调度成本

其中，dijsk为每辆出租车从第(i，j)个区域到第(s，k)个区域的距离；

xijsk(t)为从(i，j)区域调度到(s，k)区域的空载出租车比例，i,s＝1,2,…m；

j,k＝1,2,…n；0≤x(t)≤1；N为出租车公司拥有的出租车总数；K为单位距离的调度成本；

步骤5)使出租车分布与乘客分布估计相一致，即调度结束后，在任意区域(i，j)内其中，Tij(t)表示t时刻出租车的初始分布；

步骤6)以调度成本Z1最低作为全局完成调度目标的最优策略，获得集体策略规划模型：

2.根据权利要求1所述的基于GPS大数据的出租车高效益智能集体调度算法，其特征在于：所述步骤5)还包括：根据各网格内每单生意平均收益修正出租车分布其中，Cij(t)为t时刻第(i，j)网格区域的乘客单笔生意平均收益。

说明书

基于GPS大数据的出租车高效益智能集体调度算法

技术领域

[0001] 本发明涉及大数据领域，特别涉及一种基于GPS大数据的出租车高效益智能集体调度算法。

背景技术

[0002] 城市交通除公交、地铁之外，出租车在人们的出行中扮演着非常重要的角色。但现实中常出现这样的尴尬情景：一边是出租车满大街转悠，另一边是乘客打不到车；一边是出租车扎堆，另一边是一辆车也没有。这种情况随着“滴滴”、“首汽”等网约车平台的出现有所改观，但营运车辆空载后到接单的这个时段依然存在着盲目行驶，热点区域车辆扎推等现象，对于乘客而言，依然存在着打车等待时间过长等问题，城市交通效率有待提升。

[0003] 城市居民出行具有随机性，不同时间、不同区域的乘客分布也不均匀，并且会随着城市的发展、道路的拓展以及周边环境的变化而快速变化，依靠经验实现出行供需的精准对接是不可能的，必须借助大数据的收集和分析研究才能实现。出租车GPS大数据的收集是实时且透明的，它记录了乘客的上车时间、下车时间、上车地点、下车地点、行驶里程、费用等信息，这为挖掘乘客随机行为背后的出行规律，实现以出租车运营效益、运力和交通资源均衡分布为多重优化目标，制定实时高效寻客策略提供了基础数据。

[0004] 目前，国内外借助出租车GPS数据开展寻客策略研究，现有的出租车寻客策略大多数是对于单辆出租车的线路推荐，而没有宏观考虑整体的出租车调度。这样往往会出现出租车扎堆，运力过剩的现象，导致寻客效率降低，效益下降。

发明内容

[0005] 为了解决背景技术中出租车扎堆、运力过剩的问题，本发明提供一种出租车资源均衡分布，达到运力与客流量基本一致的基于GPS大数据的出租车高效益智能集体调度算法。

[0006] 本发明解决其技术问题所采用的技术方案是：一种基于GPS大数据的出租车高效益智能集体调度算法，包括以下步骤：

[0007] 步骤1)数据预处理：从GPS大数据中获取出租车的行驶数据以及财务数据，根据出租车标识在所述行驶数据以及财务数据中将行驶轨迹与对应的财务信息相匹配；

[0008] 步骤2)区域划分：对城市的地理区域进行网格划分并将网格记为(i，j)，i＝1，2…m，j＝1，2，…n，

[0009] 步骤3)将GPS大数据中出租车发生交易的地域与各网格相匹配，得到所有网格内在t时段关于空间上的乘客分布估计：

[0010]

[0011] 其中，N为所有的乘车记录总数；Nij(t)为在t时段内，第(i，j)个网格发生的总乘车记录数；

[0012] 步骤4)计算出租车公司在t时刻调度出租车的调度成本

[0013]

[0014] 其中，dijsk为每辆出租车从第(i，j)个区域到第(s，k)个区域的距离；xijsk(t)为从(i，j)区域调度到(s，k)区域的空载出租车比例，i,s＝1,2,…m；j,k＝1,2,…n；0≤x(t)≤1；N为出租车公司拥有的出租车总数；K为单位距离的调度成本；

[0015] 步骤5)使出租车分布与乘客分布估计相一致，即调度结束后，在任意区域(i，j)内[0016]

[0017] 其中，Tij(t)表示t时刻出租车的初始分布；

[0018] 步骤6)以调度成本Z1最低作为全局完成调度目标的最优策略，获得集体策略规划模型：

[0019]

[0020] 。

[0021]

[0022] 所述步骤5)还包括：根据各网格内每单生意平均收益修正出租车分布

[0023]

[0024] 其中，Cij(t)为t时刻第(i，j)网格区域的乘客单笔生意平均收益。

[0025] 本发明的有益效果是：本发明兼顾出租车到达热点载客区域的时间成本及到达后的出租车供需关系等情况，以高效益载客、供需均衡分布为多重目标，从全局角度实现空车调度，在效益优先的前提下最大程度利用出租车资源，并避免热点区域供远大于需的局面，实现了高效益实时寻客策略，填补之前研究的空白和不足，为出租车司机、车辆运营公司以及交通管理部门做调度决策提供一种有效、科学的方法，实现经济效益和社会效益的综合提升。

附图说明

[0026] 图1为本发明实施例的集体策略高效益寻客推荐调度结果三维图。

[0027] 图2为本发明实施例的集体策略寻客推荐调度结果统计及效益提升验证表[0028] 图3为本发明实施例的集体策略日效益提升时序分布图

[0029] 图4为本发明实施例的集体策略月效益提升时序分布图。

具体实施方式

[0030] 下面结合附图对本发明实施例作进一步说明：

[0031] 本发明实施例中，一种基于GPS大数据的出租车高效益智能集体调度算法，包括以下步骤：

[0032] 步骤1)数据预处理：从GPS大数据中获取出租车的行驶数据以及财务数据，根据出租车标识在所述行驶数据以及财务数据中将行驶轨迹与对应的财务信息相匹配；

[0033] 步骤2)区域划分：对城市地域进行网格划分，网格划分可以有两种方法，一是按单位距离进行划分，单位距离设定为1km*1km；另一种按n*m进行划分，两者都可行，但后者更加灵活。将划分的各个网格记为(i，j)，记xij，yij，i＝1，2…m，j＝1，2，…n为第(i，j)个网格区域中心点的经纬度，xmin,ymin,xmax,ymax表示纽约行政区域最小经度纬度和最大经纬度，可得每个空间网格的尺寸为Δx*Δy，

[0034]

[0035] 第(i，j)个区域中心点经纬度为：

[0036]

[0037] 网格距离决定了出发点到推荐点所花的时间成本，是提升高效益寻客策略精准度的关键指标。我们将网格距离定义为两个区域中心的距离，因为一般道路都是南北走向或者东西走向，所以该距离的计算可近似为延经度方向距离差加上延纬度方向距离差。于是可得第(i，j)个网格到第(s，k)个网格距离定义为：

[0038] dijsk＝|xij-xsk|Ux+|yij-ysk|Uy

[0039] 其中，Ux表示在该网格一度纬线对应的实际长度，Uy表示在该网格一度经线对应的实际长度。任意纬度的一度经线长度一样，而一度纬线的长度与行政区域的经度值θ相关，且有Ux＝Uycos(θ)。

[0040] 步骤3)将GPS大数据中出租车发生交易的地域与各网格相匹配，得到所有网格内在t时段关于空间上的乘客分布估计：

[0041]

[0042] 其中，N为所有的乘车记录总数；Nij(t)为在t时段内，第(i，j)个网格发生的总乘车记录数；

[0043] 步骤4)计算出租车公司在t时刻调度出租车的调度成本

[0044]

[0045] 其中，dijsk为每辆出租车从第(i，j)个区域到第(s，k)个区域的距离；xijsk(t)为从(i，j)区域调度到(s，k)区域的空载出租车比例，i,s＝1,2,…m；j,k＝1,2,…n；0≤x(t)≤1；N为出租车公司拥有的出租车总数；K为单位距离的调度成本；

[0046] 步骤5)使出租车分布与乘客分布估计相一致，即调度结束后，在任意区域(i，j)内[0047]

[0048] 其中，Tij(t)表示t时刻出租车的初始分布；考虑到出租车资源的均衡分布是指任意地区的客户能够具有相同的打车满意度，也就是任意时刻，任意区域的乘客具有相同的概率打到出租车，即出租车运力分布与乘客空间分布相一致。全局调度应尽可能实现出租车空间分布接近于乘客空间分布Pij(t)，这样，对于每个司机来说，接到一单生意的概率是一样的，而因为每个区域每单生意平均收益并不一致，为了保持公平性，适当增加高效益区域运力，根据各网格内每单生意平均收益修正出租车分布

[0049]

[0050] 其中，Cij(t)为t时刻第(i，j)网格区域的乘客单笔生意平均收益。

[0051] 步骤6)以调度成本Z1最低作为全局完成调度目标的最优策略：显然全局完成调度目标的最优策略应该是调度成本Z1最低，又由于N，K为常数，所以Z1最低的策略等价于Z最低，即

[0052]

[0053] 综上，以调度成本Z1最低作为全局完成调度目标的最优策略，获得集体策略规划模型：

[0054]

[0055]

[0056] 本发明根据乘客的分布估计Pij(t)推算出各网格内的出租车需求量，并以最低调度成本minZ1(t)的原则，对出租车集体提供调度方案，兼顾出租车到达热点载客区域的时间成本及到达后的出租车供需关系等情况，以高效益载客、供需均衡分布为多重目标，从全局角度实现空车调度，在效益优先的前提下最大程度利用出租车资源，并避免热点区域供远大于需的局面，实现了高效益实时寻客策略。

[0057] 下面结合纽约市的出租车数据对模型进行验证：将纽约城的空间分割为20*20个网格，分别选取4月1号和4月3号早上8点早高峰、下午3点和晚上8点的时空切片，出租车初始分布以延时3个半小时后的下车车辆数的分布来模拟。按出租车保有量为1.5万辆计算，以4月1号(工作日)早上8点调度结果为例，如图1，左图为各网格车辆调出情况，右图为各网格车辆调入情况。

[0058] 其他5个时段的调度情况不再累述，图2记录了以上6个时段调度结果的统计数据，并对调度结果有效性进行了验证，具体验证如下：

[0059] 1、估计t时刻出租车空载率

[0060] 记K(t)为t时段空载率，由客户需求时数等于出租车提供时数得：

[0061]

[0062]

[0063] 其中Tave(t)表示平均每单行驶时长，Tw和M为常量，分别表示单位时长和城市出租车保有量。

[0064] 2、估计(i，j)区域t时段单位时间收益

[0065]

[0066] 为t时刻第(i，j)网格区域的乘客单笔生意平均收益

[0067]

[0068] 其中Taveij(t)表示(i，j)区域t时刻平均每单行驶时长，Tij(t)表示t时刻出租车的分布，Pij(t)表示t时刻客户的分布

[0069] 4、结果验证

[0070] 调度前后的效益对比如图3所示，其中三角曲线表示为调度前的总效益∑A2(t)，十字曲线表示为调度后的总效益∑A1(t)。

[0071]

[0072] 则当天的效益提升率为13.98％。同理，对2016年4月份的效益提升进行分析，月收益提升率定义为：

[0073]

[0074] 如图4所示，按月收益提升率计算4月的收益提升率为11.4％，策略有效性非常明显。

[0075] 各位技术人员须知：虽然本发明已按照上述具体实施方式做了描述，但是本发明的发明思想并不仅限于此发明，任何运用本发明思想的改装，都将纳入本专利专利权保护范围内。