Combinatorial Optimization Meets Reinforcement Learning: Effective Taxi Order Dispatching at Large-Scale

强化学习 计算机科学 调度(生产过程) 符号 匹配(统计) 二部图 组合优化 比例(比率) 订单(交换) 运筹学 人工智能 数学优化 理论计算机科学 算法 图形 物理 经济 统计 算术 量子力学 数学 财务
作者
Yongxin Tong,Dingyuan Shi,Yi Xu,Weifeng Lv,Zhiwei Qin,Xiaocheng Tang
出处
期刊:IEEE Transactions on Knowledge and Data Engineering [Institute of Electrical and Electronics Engineers]
卷期号:35 (10): 9812-9823 被引量:20
标识
DOI:10.1109/tkde.2021.3127077
摘要

Ride hailing has become prevailing. Central in ride hailing platforms is taxi order dispatching which involves recommending a suitable driver for each order. Previous works use pure combinatorial optimization solutions for taxi dispatching, which suffer in practice due to complex dynamics of demand and supply and temporal dependency among dispatching decisions. Recent studies try to adopt data-driven method into combinatorial optimization hoping knowledge from history data would help overcome these challenges. Among these attempts, adoption of reinforcement learning shows great promise but current adoptions are a unidirectional integration which restricts the potential performance gains. In this work, we propose L earning T o D ispatch(LTD), a systematic solution that allows synergic integration of reinforcement learning and combinatorial optimization for large-scale taxi order dispatching. We demonstrate the necessity of online learning and taxi scheduling for reinforcement learning to work in synergy with combinatorial optimization, and devise corresponding algorithms. We also devise many tricks for more efficient calculation of the bipartite matching. Experiments show our methods can improve $36.4\%$ and $42.0\%$ on utility and efficiency at most, respectively. Especially, it achieves state-of-the-art performance in terms of utility.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
刘期岜完成签到 ,获得积分20
1秒前
林夏果完成签到,获得积分10
1秒前
闾丘志泽完成签到,获得积分10
2秒前
听思念渐近完成签到,获得积分10
2秒前
斯文败类应助emotional_damage采纳,获得10
3秒前
YHF2完成签到,获得积分10
4秒前
老薛完成签到,获得积分10
4秒前
5秒前
5秒前
科研通AI2S应助sx采纳,获得10
6秒前
sxy完成签到,获得积分20
6秒前
ABC完成签到,获得积分10
7秒前
8秒前
飞飞发布了新的文献求助10
11秒前
11秒前
笨笨歌曲发布了新的文献求助10
12秒前
Akim应助虚心醉蝶采纳,获得10
13秒前
...完成签到,获得积分10
14秒前
15秒前
ln0完成签到,获得积分10
15秒前
16秒前
18秒前
友好碧完成签到 ,获得积分10
18秒前
19秒前
研友_yLpzpZ完成签到,获得积分10
21秒前
袁大头发布了新的文献求助10
21秒前
shenxiaohui完成签到,获得积分20
23秒前
24秒前
zzzyyyuuu完成签到 ,获得积分10
25秒前
Zhoujian发布了新的文献求助10
25秒前
fgjvythjd完成签到 ,获得积分10
25秒前
小号发布了新的文献求助10
25秒前
小白完成签到 ,获得积分10
26秒前
27秒前
Wangjingxuan完成签到,获得积分10
28秒前
xin完成签到,获得积分10
28秒前
finger完成签到,获得积分10
29秒前
30秒前
正直尔白发布了新的文献求助10
30秒前
三冘完成签到,获得积分10
30秒前
高分求助中
Sustainability in Tides Chemistry 2800
The Young builders of New china : the visit of the delegation of the WFDY to the Chinese People's Republic 1000
Rechtsphilosophie 1000
Bayesian Models of Cognition:Reverse Engineering the Mind 888
Handbook of Qualitative Cross-Cultural Research Methods 600
Very-high-order BVD Schemes Using β-variable THINC Method 568
Chen Hansheng: China’s Last Romantic Revolutionary 500
热门求助领域 (近24小时)
化学 医学 生物 材料科学 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 基因 遗传学 催化作用 物理化学 免疫学 量子力学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 3137214
求助须知:如何正确求助?哪些是违规求助? 2788251
关于积分的说明 7785413
捐赠科研通 2444284
什么是DOI,文献DOI怎么找? 1299869
科研通“疑难数据库(出版商)”最低求助积分说明 625639
版权声明 601023