Loading...
墨滴

fxyten

2021/04/04  阅读:46  主题:默认主题

基于图的动态供需系统均衡度量——GEM算法(JASA)

1 背景

近年来,伴随人们对于出行多样化需求的提升,诸如滴滴出行等网约车平台的规模和市场份额不断上升。因此,相比于简单地考虑盈利,平台更多时候需要密切关注市场供给量和需求量的平衡,保证系统持续稳定健康地运转。从平台的角度来说,优化供需的目的是控制调度成本,提高司机和乘客的留存率;而从整个市场来看,可以提高市场效率,尽可能实现市场出清。

同时,平台现有的运营或者策略评估的核心指标,包括人均GMV、应答率等,只能对策略的短期影响进行评估。而供需信息更加注重策略带来的长期影响,对于双边市场中间层或平台的发展具有重大价值,因此需要引入新的度量供需关系的指标辅助平台进行智能化运营和策略评估。供需的优化能够使得平台运力更加合理的匹配乘客的出行需求,对于长期的GMV,应答率等也会有提升的作用。

2 GEM 的贡献

为了解决这个问题,由上海财经大学统计学院周帆助理教授与滴滴出行AI Labs首席统计学家朱宏图教授团队合作完成的文章《Graph-Based Equilibrium Metrics for Dynamic Supply-Demand Systems with Applications to Ride-sourcing Platforms》中,在广义Wasserstein距离的基础上进行改进,提出了一个新的基于图的均衡度量(Graph-Based Equilibrium Metrics, GEM),通过求解一个加权图空间中带约束的非平衡的最优运输问题,来量化共享出行平台(ride-sourcing platform,比如滴滴出行)中供需网络之间的距离。GEM构建了一个通用的均衡度量,可以用来量化任一双边市场中买卖双方之间的匹配关系,并作为评估不同策略优劣的重要指标。该文章已被统计学顶级期刊 Journal of the American Statistical Association 接收。

论文地址https://www.tandfonline.com/doi/abs/10.1080/01621459.2021.1898409

项目地址https://github.com/mlzxzhou/GEM

数据地址https://outreach.didichuxing.com/app-vue/outreach.didichuxing.com?id=1025

相比于传统的距离度量,GEM考虑了供需双方总量的不平衡。举例来说,因为对供需双方标准化的原因,下图两种情况的Wasserstein距离或Hellinger距离相等,而这两者在实际中显然代表了不同的供需状况。

标准化后无法判断供需是否真正平衡
标准化后无法判断供需是否真正平衡

另一方面,GEM还考虑了真实情境下区域间传输的不对称性。如下图a所示,A区域到B区域是单行道,因此可以移动A中的供给去匹配B中的需求,但是反之则不行。此外,对于滴滴这类的派单平台,为了保证乘客体验,可以匹配的供需之间的距离需要满足一定范围限制。在下图B中,A与C尽管可以经过B相连,但其距离如果太远,按Wasserstein方法((b)下图)强行匹配这一供给与需求并不符合实际的平台派单规则,因此将可供匹配的运力限制在距离需求一定距离范围内((b)上图)的GEM方法更加合理。

3 GEM应用案例

文章利用三个案例来检验GEM在有限样本下的表现性能,包括:

(1)应答率预测;(2)订单调度策略设计;(3)策略评估。

文章使用的数据来源为:滴滴平台2018年4月21日至5月20日、2018年11月12日至11月25日、2018年12月03日至12月16日H市经过区域划分的订单数量(发单量、应答量、完单量)及司机数量数据,以及H市经过划分的的格子地理距离信息。

为了后续实验分析GEM的有效性,文中定义了两个由GEM方法构建的指标:

(1)供需比率 :t时间段区域 的乘客订单量与GEM优化所得最优司机供给量 之比,按照每个区域需求量进行加权得到同一时间整个城市的GEM值。

(2)供需距离 :t时间段区域 的订单量 与GEM计算所得最优司机供给量 之差。

3.1 案例一:应答率的预测

应答率(司机接单数/乘客发单数)是衡量乘客需求是否得到有效满足的指标。能否通过历史供需平衡指标去预测未来的应答率,为平台实施策略提供参考,是衡量一个供需平衡指标是否有用的重要标准。因此,案例一评估了历史的GEM值对于未来应答率的预测效果。

这一案例使用H市2018年4月21日至5月20日的供需数据,将整个城市分成800个不重叠的六边形子区域,每个区域的司机数量和乘客数量按1分钟进行计算。

实验使用过去10个十分钟的时间片以及过去5天与预测时刻相同的时间窗口的历史GEM值去预测下一个10(或60)分钟时间片内全城应答率(司机接单数/乘客发单数)的对数:

测试周真实应答率与基于不同方法的预测值的比较
测试周真实应答率与基于不同方法的预测值的比较

文章使用均值绝对百分比误差(MAPE)和均方根误差(RMSE)作为评价指标去比较GEM、基于Hellinger距离、基于Wasserstein距离的方法的预测精度。

H市按周一至周日划分的不同方法预测应答率RMSE
H市按周一至周日划分的不同方法预测应答率RMSE

实验结果表明GEM的预测效果显著好于其他方法,比起次优的方法RMSE降低了70.6%。

该实验证明了GEM能够更好地预测应答率,尤其是应答率显著波动的时间段。这对平台提前预测未来供需状况,提前调配运力,减少订单响应的等待时间,提升用户体验。

3.2 订单调度策略设计

订单调度是指网约车平台为附近乘客分配空闲的司机。标准的订单调度方法更加注重提高应答率和客户的满意度。然而用户的出行需求是持续存在的,如何通过增加司机的收入,吸引足够多的司机或保证司机留存,以满足双边市场供给量的需求,也是一个订单调度策略设计需要重点考虑的问题。

一些更先进的算法力求在小的上车距离和大的司机收入之间取得平衡,但没有考虑多个司机前往同一个目的地的交互影响。为了设计更好的调度策略,文章将GEM加入优化目标,通过模拟验证GEM加入优化目标后对司机预期收益的影响。

订单调度作为一个二分图问题的匹配过程:(1)准备配对的订单和车辆;(2)量化满足调度约束的所有车辆-订单对的潜在预期收益;(3)寻找最优的匹配方式,以使总收益最大化。
订单调度作为一个二分图问题的匹配过程:(1)准备配对的订单和车辆;(2)量化满足调度约束的所有车辆-订单对的潜在预期收益 ;(3)寻找最优的匹配方式,以使总收益最大化。

实验结果表明,使用GEM设计的订单调度策略,在司机总收入额1千万元以上的前提下,应答率和司机收入提高了1%以上,这在数额上是一个很大的提高。

这一提升证明了GEM引入调度策略,能够在不增加乘客成本的情况下改善供需平衡,有效提高司机收入。其价值在于考虑当前派单对未来的影响,优化平台供需关系,从长远的角度提升司机收入和用户体验。

3.3 案例三:策略有效性验证

在网约车这种非常实时的双边交易市场,供不应求或者供过于求的局部时空几乎不可避免的存在,像滴滴这样的网约车平台通常采用时间片轮转的实验设计方式,相邻时间片采用AB实验的方法,比较策略的优劣。因此,案例三目的是验证GEM是否能对不同策略带来的变化做出敏感的反应,成为评价策略优劣的重要指标。

该案例AB test使用的是2018年12月3日至16日H市的实验数据,并用2018年11月12日至25日的数据作为AA test参照。首先比较随机选择的2018年12月8日H市不同策略下以30min为间隔的GEM值:

策略评估结果:(A)测试日不同策略GEM值比较;(B)早高峰时间段供需距离
策略评估结果:(A)测试日不同策略GEM值比较;(B)早高峰时间段供需距离

(A)图中绿点和红点分别表示控制组和实验组策略。被蓝色圆圈标记时间段7:00到8:00 a.m.表明当将策略从控制策略更改为实验策略时,GEM值显著降低。

其次,文章中构建以GEM值、应答率、完单率、GMV为被解释变量,以实验/对照组虚拟变量 和一些受策略影响较小的变量 (如订单量和司机量)为解释变量的回归模型,通过是否实验组的虚拟变量系数的双侧t检验,判断新策略是否会带来GEM值的显著变化:

实验结果表明,在AA test中,应答率、完单率、GMV及GEM在5%显著性水平下均没有表现出明显的处理效应(treatment effect),而在AB test中GEM值从控制组到实验组有明显的下降,应答率、完单率、GMV有明显的提高。

该变化说明,如果使用单个指标评价策略,GEM是一个可行的选项。

fxyten

2021/04/04  阅读:46  主题:默认主题

作者介绍

fxyten