众包出行中的请求分配及路线推荐问题的研究

In recent years, crowdsourced transportation platforms (e.g. Didi, Uber, Grab, Lyft) attract more and more users, including both customers and drivers. Crowdsourced transportation platforms have a large crowd of registered drivers, and they can provide customers with on-demand trip services in a timely manner. For the sake of response time, existing platforms prefer to assign trip requests to drivers using heuristics. For example, they tend to assign a request to the nearest driver available. Furthermore, the platforms usually charge a customer based on the distance and the time of the trip...However, two important issues remain unsolved in those platforms: (i) the drivers may be unable to express their preferences (e.g. some drivers may not be willing to go to remote or congested destinations); (ii) customers may have fare disputes with the drivers. The second issue arises because existing platforms do not provide an accurate estimate of the fare when a trip begins. The fare depends on the traffic and the route chosen by the driver. However, it may be hard for the customer (especially during a travel abroad) to check whether the route corresponds to a reasonable fare. To improve the satisfaction of customers and drivers, this project aims to (1) develop preference-aware trip request assignment techniques, and (2) develop representative route recommendation techniques to prevent fare disputes in advance, as well as (3) build an open-source test system for extensive simulation and performance evaluation. We believe that our project will strengthen the crowdsourced transportation services and benefit the public.

近年来，类似于滴滴、优步、Grab的众包出行平台越来越受欢迎。这类平台利用大群司机及时为乘客提供按需出行服务。为减少乘客的等待时间，现有平台一般将每个出行请求分配给离其最近的司机，并在行程结束时根据实际行驶的距离以及时间向乘客收费。然而，司机可能有自己的接单喜好。比如有些司机排斥去偏僻或拥堵的目的地。另外，用户可能会与司机关于出行费用产生纠纷。这些问题都是现有平台没有解决的。为提高司机和乘客的满意度，本课题提供了新的解决方案。对于司机而言，我们根据司机的个人偏好和成本设计有效的出行请求分配算法；对于乘客而言，我们在行程开始前为其推荐最具代表性的k条路线（及其预估费用）供其选择，有效避免费用纠纷。另外，本课题的输出将为众包出行服务提供一个开源测试系统。这将激励业界在部署新技术前先在我们的测试系统上进行性能评估。本课题将改善众包出行平台的服务体验，令其在中国服务业经济中扮演更加重要的角色。

随着数字经济的发展，众包平台如滴滴、优步、Grab等在人们的日常生活中起到非常重要的作用。本项目围绕基于机器学习模型的众包任务动态分配及规划这一科学问题，联合了海量数据存储与处理以及机器学习领域的研究力量，在众包任务调度及规划方面提出了面向数据特点的特征提取机制、基于强化学习的任务分配方法以及针对实时交通情况的路线规划算法，对乘客的出行需求及司机的接单喜好进行充分挖掘，以提高司机和乘客的满意度。在课题执行的三年时间里，各项研究内容均按研究计划顺利开展，并取得了一定的成果。首先，本课题提出了针对具体场景及特点的任务/工人特征提取方法，并基于动态规划的方法在保证任务完成率的同时，为工人提供尽可能满足对应偏好需求的动态众包任务分配方法。其次，为了支持多类型任务，课题考虑了不同的任务约束条件，如技能需求、工人多样性需求、不可拼单任务需求等。并对不同类型的任务进行进一步优化，为工人规划最优任务完成路线，以保证工人可以以最小的代价完成所分配的所有任务。再次，课题还对海量众包任务数据的存储、可信处理以及用户的隐私保护等进行研究。为高效地存储海量时空众包数据，本项目研究列式数据存储机制以高效进行海量众包数据存取；为保护任务发布者以及公认的隐私以及提高数据安全性，本项目提出基于区块链的时空众包服务框架，在任务分配的同时保护地址隐私、账户隐私等问题。本课题共发表9篇学术论文，其中SCI检索6篇，CCFB核心期刊1篇，优秀会议论文2篇，同时获得授权国家发明专利1项，公开国家发明专利1项。