Preference-Aware Task Assignment in On-Demand Taxi Dispatching: An Online Stable Matching Approach

• DOI: 10.1609/aaai.v33i01.33012245
• Publication Date: 2019-09-10T07:42:38Z
• Authors: Boming Zhao; Pan Xu; Yexuan Shi; Yongxin Tong; Zimu Zhou; Yuxiang Zeng
• Keywords: Ignorance; Online algorithm; Revealed preference

A central issue in on-demand taxi dispatching platforms is task assignment, which designs matching policies among dynamically arrived drivers (workers) and passengers (tasks). Previous maximize the profit of platform without considering preferences workers tasks (e.g., may prefer high-rewarding while nearby workers). Such ignorance impairs user experience will decrease long run. To address this problem, we propose preference-aware assignment using online stable matching. Specifically, define a new model, Online Stable Matching under Known Identical Independent Distributions (OSM-KIID). It not only maximizes expected total profits (OBJ-1), but also tries to satisfy by minimizing number blocking pairs (OBJ-2). The model features practical arrival assumption validated on real-world dataset. Furthermore, present linear program based algorithm LP-ALG, achieves an ratio at least 1−1/e OBJ-1 has most 0.6·|E| expectedly, where |E| edges compatible graph. We show that natural Greedy can have arbitrarily bad performance maintaining around 0.5·|E| pairs. Evaluations both synthetic real datasets confirm our theoretical analysis demonstrate LP-ALG strictly dominates all baselines objectives when notably outnumber workers.