时空敏感拼车系统的关键算法设计

Advances of information technology (e.g., mobile Internet) facilitate the increasing popularity of ridesharing systems. However, existing ridesharing algorithms typically overlook the importance of maintaining the long-term and healthy operation of ridesharing systems. That is, they employ suboptimal spatial-temporal decision granularities, fail to balance the utilities of all parties in the system, and ignore the long-term evolution of the system states. Addressing the aforementioned limitations of existing work, this project investigates the design of key algorithms for spatially and temporally sensitive ridesharing systems in the following three aspects: we develop spatial-temporal order clustering algorithms that are adaptive to the unique spatial-temporal properties of ridesharing orders, design Pareto optimal fair pricing algorithms that strike a balance among the utilities of drivers, passengers, and the ridesharing platform, and propose order dispatch algorithms that optimize the platform’s long-term utility. Order clustering establishes appropriate spatial-temporal decision granularities for pricing and matching, which in turn affect order clustering results as well. The aforementioned three aspects complement each other and boost the evolution of ridesharing systems’ performance in an integrated manner. This project will contribute to new algorithmic tools and design philosophies of ridesharing systems. Furthermore, we will test and implement our algorithms in real-world ridesharing systems. Currently, we have already obtained the GPS trajectories of over 40 million taxi and DiDi Express orders, and thus this project has a solid basis in terms of spatial-temporal data.

移动互联网等信息技术的发展使得拼车系统的使用日趋普及。然而现有的拼车算法忽视系统长期良性运转的重要性：缺失最优时空决策尺度的设定、未能兼顾系统各方收益、忽略系统状态的长期演进。本项目突破上述限制，以拼车系统的时空敏感性为核心，从订单聚合、行程定价、司乘匹配三个关键角度展开拼车算法设计：1.研发自适应时空可拼性的订单聚合算法，为平台确立最优时空决策尺度；2.设计帕雷托最优的公平行程定价算法，全面权衡系统各方收益；3.考量当前决策对系统未来状态演进的影响，提出平台收益长效最优的司乘匹配算法。订单聚合为定价和匹配确立合适的时空决策尺度，后两者又反作用于前者，影响订单聚合的结果。上述三部分相辅相承，形成有机整体，推进拼车系统整体性能的进化。本项目为拼车系统设计提供算法支持和思想探索，且拟在实际系统中测试并落地所研发的算法。本项目已获取逾4000万滴滴快车和出租车订单的轨迹数据，具备坚实的数据基础。

移动互联网等信息技术的发展使得拼车系统的使用日趋普及。然而现有的拼车算法忽视系统长期良性运转的重要性：缺失最优时空决策尺度的设定、未能兼顾系统各方收益、忽略系统状态的长期演进。本项目突破上述限制，以拼车系统的时空敏感性为核心，从订单聚合、行程定价、司乘匹配三个关键角度展开拼车算法设计：1.研发自适应时空可拼性的订单聚合算法，为平台确立最优时空决策尺度；2.设计帕雷托最优的公平行程定价算法，全面权衡系统各方收益；3.考量当前决策对系统未来状态演进的影响，提出平台收益长效最优的司乘匹配算法。订单聚合为定价和匹配确立合适的时空决策尺度，后两者又反作用于前者，影响订单聚合的结果。上述三部分相辅相承，形成有机整体，推进拼车系统整体性能的进化。项目在国际期刊和会议上共发表论文17篇，其中CCF-A类论文10篇、CCF-B类论文5篇。项目申请国家发明专利3项。