An Efficient Insertion Operator in Dynamic Ridesharing Services
- 28 September 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 34 (8) , 3583-3596
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)$ , 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.
Keywords
Funding Information
- National Key Research and Development Program of China (2018AAA0101100)
- National Natural Science Foundation of China (61822201, 62076017, U1811463, 61690202)
- Beijing Municipal Science and Technology (Z191100002519012)
This publication has 29 references indexed in Scilit:
- An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windowsEuropean Journal of Operational Research, 2011
- Analysis of the dial-a-ride problem of Hunsaker and SavelsberghOperations Research Letters, 2011
- The dial-a-ride problem: models and algorithmsAnnals of Operations Research, 2007
- A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problemEuropean Journal of Operational Research, 2006
- On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem2006
- A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windowsTransportation Research Part B: Methodological, 2004
- Efficient feasibility testing for dial-a-ride problemsOperations Research Letters, 2002
- The General Pickup and Delivery ProblemTransportation Science, 1995
- A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windowsTransportation Research Part B: Methodological, 1986
- An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time WindowsTransportation Science, 1983