Optimal Multi-Meeting-Point Route Search.

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 (\mathsf OMMPR<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq1-2492554.gif"/></alternatives>) query. Given a road network $G$<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq2-2492554.gif"/></alternatives> , a source node $s$<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq3-2492554.gif"/></alternatives>, a target node $t$<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq4-2492554.gif"/></alternatives> , and a set of query nodes $U$<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq5-2492554.gif"/></alternatives>, the \mathsf OMMPR<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq6-2492554.gif"/></alternatives> query aims at finding the best route starting from $s$ <alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq7-2492554.gif"/></alternatives> and ending at $t$<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq8-2492554.gif"/></alternatives> 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 \mathsf OMMPR<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq9-2492554.gif"/></alternatives> query is NP-hard. To answer the \mathsf OMMPR<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq10-2492554.gif"/></alternatives> query efficiently, we propose two novel parameterized solutions based on dynamic programming (DP), with the number of query nodes $l$<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq11-2492554.gif"/></alternatives> (i.e., $l=|U|$<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq12-2492554.gif"/></alternatives>) as a parameter, which is typically very small in practice. The two proposed parameterized algorithms run in $O(3^l\cdot m+ 2^l \cdot n\cdot (l+\log (n)))$<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq13-2492554.gif"/></alternatives> and $O(2^l \cdot (m + n\cdot (l+\log (n))))$<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq14-2492554.gif"/></alternatives> time, respectively, where $n$<alternatives><inline-graphic xlink:type="simple" xlink:href="yu-ieq15-2492554.gif"/></alternatives> and $m$<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq16-2492554.gif"/></alternatives> denote the number of nodes and edges in graph $G$<alternatives> <inline-graphic xlink:type="simple" xlink:href="yu-ieq17-2492554.gif"/></alternatives>, 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. [ABSTRACT FROM PUBLISHER]