The topological features of urban road networks represent the interconnecting links between different road networks within cities. Shortest path search methods have garnered significant attention in the field of intelligent transportation. In real-world scenarios, it is essential to determine the shortest path between a given starting and target road section within a specific range based on road network topology. However, traditional path search methods often exhibit low efficiency during whole map searches. To address this issue, this paper introduces a time-constrained shortest path method leveraging the Dijkstra algorithm. In the proposed approach, the passing time of a road under the maximum speed limit is utilized as the weight of the road section, while the time constraint is set according to the actual requirements to find the shortest path between the starting and reachable target sections within the specified time range. Using map data from Xi’an City, this paper compares the time performance of time-constrained shortest path method to that of a uniform-cost search algorithm with spatio-temporal constraints. Experimental results indicate that the proposed method demonstrates superior time performance under various time constraints. The proposed approach is applicable to location prediction, online map matching, and other practical transportation issues, potentially enhancing the efficiency of existing algorithms.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Time-constrained shortest path search algorithm for urban road network


    Contributors:
    Jun, Kang (author) / Zihao, Wu (author) / Qianqian, Wang (author)


    Publication date :

    2023-08-04


    Size :

    3346875 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Urban road network shortest path acquisition method based on angle limitation and bidirectional search

    DING JIANXUN / FENG ZHANYU / JIANG YUPENG et al. | European Patent Office | 2021

    Free access

    Urban road network shortest path acquisition method based on directivity induction

    DING JIANXUN / JIANG YUPENG / ZHOU RUNDONG et al. | European Patent Office | 2021

    Free access

    Urban K shortest path acquisition method considering real-time road condition

    DING JIANXUN / SHAN YUNHAN / DUAN RUI et al. | European Patent Office | 2024

    Free access

    The Variance-Constrained Shortest Path Problem

    Sivakumar, Raj A. | Online Contents | 1994


    An improved solution algorithm for the constrained shortest path problem

    Santos, Luis / Coutinho-Rodrigues, João / Current, John R. | Elsevier | 2006