网约车任务分配系统优化
作者:
基金项目:

2021年度广东省普通高校重点科研平台和科研项目(2021 KTSCX160); 广东省质量工程(ZXKC202105)


Optimization of Task Allocation System for Online Car-hailing
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [18]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    网约车是一种广泛应用的共享移动应用, 其核心问题是将出租车请求分配给具有不同目标的司机, 尽管对网约车的任务分配进行了广泛的研究, 但在很大程度上忽视了司机之间收入的公平性, 由于优化视角的短视和分配技术的耗时, 先行者对网约车公平任务分配的研究在公平性、效用性方面还存在不足. 在本文中, 提出了公平分配学习(LAF)方法, 它既优化了效用又优化了公平性的高效任务分配方案, 采用强化学习以整体的方式进行分配, 并提出一套加速技术, 以实现大规模数据的快速公平分配. 实验结果表明, 公平分配学习方法在公平性、效用性和效率方面分别比现有水平高出86.7%、29.1%和797%.

    Abstract:

    Online car-hailing is a kind of widely used mobile application. Its core problem is to assign requests to taxi drivers with different goals. Although extensive research on task allocation has been carried out, a largely ignored problem is the income equality of drivers. Due to the short-sighted optimization and time-consuming allocation, fairness and utility receive less attention in the research on fair task allocation. In this study, an efficient task assignment scheme, learning to assign with fairness (LAF), was proposed to optimize both utility and fairness. It adopts reinforcement learning to allocate tasks holistically and proposes a set of acceleration techniques to achieve rapid and equitable allocation on a large scale. The experimental results show that the fairness, effectiveness, and efficiency of LAF are 86.7%, 29.1%, and 797% higher than the existing level, respectively.

    参考文献
    [1] Anthony BM, Chung C. Online bottleneck matching. Journal of Combinatorial Optimization, 2014, 27: 100–114. [doi: 10.1007/s10878-012-9581-9
    [2] Tang XC, Qin ZW, Zhang F, et al. A deep value-network based approach for multi-driver order dispatching. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Anchorage: ACM, 2019. 1780–1790.
    [3] Wang YS, Tong YX, Cheng L, et al. Adaptive dynamic bipartite graph matching: A reinforcement learning approach. 2019 IEEE 35th International Conference on Data Engineering (ICDE). Macao: IEEE, 2019. 1478–1489.
    [4] Tong YX, She JY, Ding BL, et al. Online minimum matching in real-time spatial data: Experiments and analysis. Proceedings of the VLDB Endowment, 2016, 9(12): 1053–1064. [doi: 10.14778/2994509.2994523
    [5] Xu P, Shi YX, Cheng H, et al. A unified approach to online matching with conflict-aware constraints. Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Honolulu: AAAI, 2019. 2221–2228.
    [6] Sühr T, Biega AJ, Zehlike M, et al. Two-sided fairness for repeated matchings in two-sided markets: A case study of a ride-hailing platform. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Anchorage: ACM, 2019. 3082–3092.
    [7] Bokányi E, Hannák A. Understanding inequalities in ride-hailing services through simulations. Scientific Reports, 2020, 10(1): 6500. [doi: 10.1038/s41598-020-63171-9
    [8] Buchbinder N, Naor J. Fair online load balancing. Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures. Cambridge: ACM, 2006. 291–298.
    [9] Tong YX, Chen YQ, Zhou ZM, et al. The simpler the better: A unified approach to predicting original taxi demands based on large-scale online platforms. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax: ACM, 2017. 1653–1662.
    [10] Lesmana NS, Zhang X, Bei XH. Balancing efficiency and fairness in on-demand ridesourcing. Proceedings of the 33rd International Conference on Neural Information Processing Systems. Vancouver: NeurIPS, 2019. 5310–5320.
    [11] Zhang LY, Hu T, Min Y, et al. A taxi order dispatch model based on combinatorial optimization. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax: ACM, 2017. 2151–2159.
    [12] Wang X, Agatz N, Erera A. Stable matching for dynamic ride-sharing systems. Transportation Science, 2018, 52(4): 850–867. [doi: 10.1287/trsc.2017.0768
    [13] Xu Z, Li ZX, Guan QW, et al. Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London: ACM, 2018. 905–913.
    [14] Garfinkel RS. Technical note—An improved algorithm for the bottleneck assignment problem. Operations Research, 1971, 19(7): 1747–1751. [doi: 10.1287/opre.19.7.1747
    [15] Lorenz MO. Methods of measuring the concentration of wealth. Publications of the American Statistical Association, 1905, 9(70): 209–219. [doi: 10.2307/2276207
    [16] Kash I, Procaccia AD, Shah N. No agent left behind: Dynamic fair division of multiple resources. Journal of Artificial Intelligence Research, 2014, 51: 579–603. [doi: 10.1613/jair.4405
    [17] Chen Z, Cheng P, Chen L, et al. Fair task assignment in spatial crowdsourcing. Proceedings of the VLDB Endowment, 2020, 13(12): 2479–2492. [doi: 10.14778/3407790.3407839
    [18] Edmonds J, Karp RM. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 1972, 19(2): 248–264. [doi: 10.1145/321694.321699
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

陈立军,张屹,陈孝如,杨微.网约车任务分配系统优化.计算机系统应用,2022,31(6):19-28

复制
分享
文章指标
  • 点击次数:841
  • 下载次数: 1929
  • HTML阅读次数: 1730
  • 引用次数: 0
历史
  • 收稿日期:2021-09-14
  • 最后修改日期:2021-10-14
  • 在线发布日期: 2022-05-26
文章二维码
您是第11117171位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号