Optimal Multi-Meeting-Point Route Search
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Knowledge and Data Engineering, 2016, 28 (3), pp. 770 - 784
- Issue Date:
- 2016-03-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 07300432.pdf | Published Version | 947.02 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 1989-2012 IEEE. Real-time ride-sharing applications (e.g., Uber and Lyft) are very popular in recent years. Motivated by the ride-sharing application, we propose a new type of query in road networks, called the optimal multi-meeting-point route (OMMPR) query. Given a road network G , a source node s , a target node t , and a set of query nodes U, the OMMPR query aims at finding the best route starting from s and ending at t such that the weighted average cost between the cost of the route and the total cost of the shortest paths from every query node to the route is minimized. We show that the problem of computing the OMMPR query is NP-hard. To answer the OMMPR query efficiently, we propose two novel parameterized solutions based on dynamic programming (DP), with the number of query nodes l (i.e., l=|U|) as a parameter, which is typically very small in practice. The two proposed parameterized algorithms run in O(3 m+ 2 n (l+\log (n))) and O(2 (m + n (l+\log (n)))) time, respectively, where n and m denote the number of nodes and edges in graph G, thus they are tractable in practice. To reduce the search space of the DP-based algorithms, we propose two novel optimized algorithms based on bidirectional DP and a carefully-designed lower bounding technique. We conduct extensive experimental studies on four large real-world road networks, and the results demonstrate the efficiency of the proposed algorithms.
Please use this identifier to cite or link to this item: