计算机科学
平面图(考古学)
线路规划
芯(光纤)
数学优化
时间复杂性
分布式计算
运筹学
算法
工程类
电信
数学
历史
考古
作者
Jiachuan Wang,Peng Cheng,Libin Zheng,Chao Feng,Lei Chen,Xuemin Lin,Zheng Wang
出处
期刊:Proceedings of the VLDB Endowment
[VLDB Endowment]
日期:2020-03-01
卷期号:13 (7): 979-991
被引量:41
标识
DOI:10.14778/3384345.3384348
摘要
The dramatic development of shared mobility in food delivery, ridesharing, and crowdsourced parcel delivery has drawn great concerns. Specifically, shared mobility refers to transferring or delivering more than one passenger/package together when their traveling routes have common sub-routes or can be shared. A core problem for shared mobility is to plan a route for each driver to fulfill the requests arriving dynamically with given objectives. Previous studies greedily and incrementally insert each newly coming request to the most suitable worker with a minimum travel cost increase, which only considers the current situation and thus not optimal. In this paper, we propose a demand-aware route planning (DARP) for shared mobility services. Based on prediction, DARP tends to make optimal route planning with more information about requests in the future. We prove that the DARP problem is NP-hard, and further show that there is no polynomial-time deterministic algorithm with a constant competitive ratio for the DARP problem unless P=NP. Hence, we devise an approximation algorithm to realize the insertion operation for our goal. With the insertion algorithm, we devise a prediction based solution for the DARP problem. Extensive experiment results on real datasets validate the effectiveness and efficiency of our technique.
科研通智能强力驱动
Strongly Powered by AbleSci AI