English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Querying the shortest path between two vertexes is a fundamental operation ina variety of applications, which has been extensively studied over static roadnetworks. However, in reality, the travel costs of road segments evolve overtime, and hence the road network can be modeled as a time-dependent graph. Inthis paper, we study the shortest path query over large-scale time-dependentroad networks. Existing work focuses on a hierarchical partition structure,which makes the index construction and travel cost query inefficient. Toimprove the efficiency of such queries, we propose a novel index by decomposinga road network into a tree structure and selecting a set of shortcuts on thetree to speed up the query processing. Specifically, we first formally define ashortcut selection problem over the tree decomposition of the time-dependentroad network. This problem, which is proven to be NP-hard, aims to select andbuild the most effective shortcut set. We first devise a dynamic programmingmethod with exact results to solve the selection problem. To obtain the optimalshortcut set quickly, we design an approximation algorithm that guarantees a0.5-approximation ratio. Based on the novel tree structure, we devise ashortcut-based algorithm to answer the shortest path query over time-dependentroad networks. Finally, we conduct extensive performance studies usinglarge-scale real-world road networks. The results demonstrate that our methodcan achieve better efficiency and scalability than the state-of-the-art method.

Querying Shortest Path on Large Time-Dependent Road Networks with Shortcuts