1. An Efficient Insertion Operator in Dynamic Ridesharing Services
- Author
-
Yi Xu, Ke Xu, Wei Li, Qian Tao, Yexuan Shi, and Yongxin Tong
- Subjects
Mathematical optimization ,business.industry ,Computer science ,Maximum flow problem ,02 engineering and technology ,Partition (database) ,Fenwick tree ,Computer Science Applications ,Dynamic programming ,Computational Theory and Mathematics ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Partition (number theory) ,020201 artificial intelligence & image processing ,business ,Time complexity ,Computer network ,Information Systems - Abstract
Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the "insertion operator". Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the \rev{maximum/sum} flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of $O(n^3)$ , where $n$ is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of $O(n^2)$ . We further improve the time efficiency of the insertion operator to $O(n)$ harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.
- Published
- 2022