探究物流效率提升方案,货拉拉论文入选国际顶级学术会议KDD

近日,国际数据科学和数据挖掘领域的最顶级学术会议KDD入选论文正式揭晓。今年KDD吸引了全球范围内705篇论文投递,仅收录了138篇论文,收录率不足20%。货拉拉论文《Improving the Information Disclosure in Mobility-on-Demand Systems》(《一种MoD系统中信息披露的优化方法》)从705篇论文中脱颖而出成功入选。该论文通过数据建模解决互联网物流智能分单问题,提升互联网物流平台效率,实现业务指标优化。

本文对货拉拉论文《Improving the Information Disclosure in Mobility-on-Demand Systems》进行详细解读。货拉拉技术团队该论文中提出了一种优化信息披露方式的框架,通过建模和求解,通过算法选取最合适的司机进行履约,实现订单的精准推送,实现平台效率、用户体验和司机体验的整体提升。

 

一、研究背景

当下货拉拉货运采用的订单分配方式为全局广播,即在指定 时间/距离 等范围内,将所有订单推送给所有司机,司机通过浏览订单列表的方式,做抉择,选取符合预期的订单进行响应,对于同一订单被多个司机响应的场景,由算法综合考虑平台效率、用户体验、司机体验等因素,选取最合适的司机进行履约。

 

定义订单推送给司机为一种信息披露,本论文提出的算法便是在订单广播环节提出的改进。

 

作为司机,处于不同的状态(时空,供需,今日累计工作时长,今日累计收入等),面对不同的选择(订单列表),对收入的期望也会有所差异。

举几个例子:

1) 供给受限的情况,待匹配订单数远远大于运力数

司机相对主动,倾向于接价格更高的订单;

2)需求受限的情况,待匹配订单数远远小于运力数

司机相对被动,倾向于选择不空驶,尽量不计较价格;

3)无限制的播单场景,司机的订单列表里有全城,甚至是全国的订单

司机相对主动,在系统订单过剩时,会选择困难;

4)强限制的派单场景,司机的订单列表里不超过一个订单

司机相对被动,在系统 没有派单/派单不满意 时,会有焦虑感;

通过对司机的决策行为进行准确地估计,并通过优化信息披露(哪些订单给哪些司机看)的方式,我们期望实现司机体验、用户体验和平台效率的整体提升。

 

二、研究价值

1.区别于传统的推荐系统,例如抖音,豆瓣,淘宝等,电商网站的商品,以及短视频等内容,相对来说是一个不受限的资源,即一个商品可以被成百上千个用户购买,一条视频可以被推荐给千千万万的用户。

货拉拉场景:订单因时空问题,会被推送给有限个司机;司机因屏幕问题,只能浏览有限个订单。这一类带资源约束的问题,目前没有成熟有效的解决方案。

 

2.区别于传统的派单模式,众包业务的播单模式引入了更多的运力保障。

a.引入了更多的复杂度

对于m个司机,n个订单的业务场景

派单解决的是1vs1的匹配问题,播单解决的问题是n vs m的信息披露问题

纯暴力的搜索空间:

图片1.png

随着问题规模的不断变大, 其对应复杂度呈指数增长。

 

b.引入了更多的司机竞争

不管是供给过剩,还是需求过剩的场景,司机对某一类订单的偏好比较一致,例如高价格、高小费等属性,导致该类订单响应的司机数多,而订单最终只能由一位司机来履约,势必产生很多的无效司机选择,导致平台整体效率降低。

三、算法框架

1.预测

基于业务场景下的条件依赖,我们拓展了Multinormal Logit Model,将司机的决策分两步来估计:

a.司机选择接单,或者不接单

b.司机选择候选列表中的某一订单进行响应

图片2.png

通过在历史行为数据上做最大化对数似然估计,我们对模型的参数进行拟合:

图片3.png

可以逐级来分析建模的合理性:

1)第一级,司机看到某个订单列表,有一定的概率会选择不接单,如果当前的列表他不满意,他会等待,直到在未来的某个时空出现满意的候选订单列表;

2)第二级,司机认为当前订单列表满意

i) 会从中选取最偏好的订单响应;

ii)基于此候选订单列表,如果减少订单o的信息披露,则司机对于其他订单 o’的接单意愿会提升,而司机对于第一级的 不接单的概率也会提升(第一级的满意度降低)

 

2.规划

a.目标函数

图片4.png

b.问题求解

i. 全局的信息披露

图片6.png

 

ii. 局部的信息披露

 

图片5.png

iii. 原始的砍边算法

iv. 最小化损失的砍边算法(Minimal Loss Edge Cutting)

图片7.png

 

 

整体算法如下:

图片8.png

3.实验

a.线:

选取货拉拉平台上3个城市的历史数据,训练司机决策预估模型

b.在线:

选取货拉拉平台上3个城市的若干时间段,按照分组轮换做AB实验

A:货拉拉现有的全局信息披露方式

B:基于司机决策预估模型的$$MLEC$$算法框架

l 定量结果(从整体的响应率、司机使用率来看,提出框架有较大提升)

图片9.png

解整体的局部供需问题

l 定性结果(颜色越深,表示订单响应问题比较严重,提出框架能够缓)

图片10.png

《Improving the Information Disclosure in Mobility-on-Demand Systems》论文提出了一种优化信息披露方式的框架,通过建模和求解,实现业务指标的优化。这项研究不仅适用于货拉拉这种互联网物流平台,同样也可应用于带资源约束的推荐系统。

(0)
上一篇 2021年6月25日 07:19
下一篇 2021年6月25日 10:27