Back to Search
Start Over
An Efficient Insertion Operator in Dynamic Ridesharing Services.
- Source :
-
IEEE Transactions on Knowledge & Data Engineering . Aug2022, Vol. 34 Issue 8, p3583-3596. 14p. - Publication Year :
- 2022
-
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 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)$ O (n 3) , where $n$ 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)$ O (n 2) . We further improve the time efficiency of the insertion operator to $O(n)$ 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 34
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 157931393
- Full Text :
- https://doi.org/10.1109/TKDE.2020.3027200