Online Multi-Request Route Planning over Time-Dependent Road Networks

This is a dataset related to spatial crowdsourcing, encompassing data on workers and tasks. The urban spatial data is sourced from an open dataset, and its website link has been provided in the paper.

Route planning problem has been well studied in static road networks, since it has wide applications in transportation networks. However, recently there have been more actual requirements that current path planning algorithms cannot solve, such as food delivery, ride-sharing and crowdsourced parcel delivery. These requirements are in a dynamic scenario, but the existing algorithms are offline. These requirements need to find the least total travel time path from the source through the nodes that appear dynamically over time to the destination, which referred to as the online route planning. On the other hand, the costs of edges in road networks always change over time, since real road networks are dynamic. Such road networks can be modelled as time-dependent road networks. Therefore, in this paper, we study the Online Route Planning over Time-Dependent road networks (ORPTD). With consideration for multiple workers, we then study its extended problem, the Online Multi-Worker-Aware Route Planning over Time-Dependent road networks (OMWARPTD) problem. We also formally proof that the OMWARPTD problem is NP-complete and its competitive ratio cannot be guaranteed. Since these problems are NP-hard, and provide approximate solutions. To adapt to the large-scale time-dependent road networks, we further speed up the algorithms by incorporating indexing techniques into them. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real datasets.