We describe a heuristic search algorithm that finds a provably optimal solution subject to a specified time interval. While this algorithm is amenable to previous works to retain the specified time interval by changing the value of epsilon during the search, our basic strategy is that node expansion around the starting node is pessimistic (exact search), and we accomplish the approximate exploration of nodes around the goal by increasing epsilon . This strategy is suitable for real-time route finding in automobile navigation systems. We conducted our experiments to clarify the practical features of the algorithm, using a digital map of a commercial automobile navigation system. The resulting advantage is that the estimation of the finishing time of the search is quite accurate, and optimal solutions are produced by making full use of the permissible search time, regardless of different machine performances.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Time-constrained heuristic search for practical route finding


    Additional title:

    Titel japanisch


    Contributors:
    Hiraishi, H. (author) / Ohwada, H. (author) / Mizoguchi, F. (author)


    Publication date :

    1999


    Size :

    9 Seiten, 13 Quellen



    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    Japanese




    ROUTE-FINDING SYSTEM, ROUTE-FINDING METHOD, AND ROUTE-FINDING PROGRAM

    TANIZAKI DAISUKE / SHIBATA TOMOFUMI | European Patent Office | 2017

    Free access

    Route-finding system, route-finding method, and route-finding program

    TANIZAKI DAISUKE / SHIBATA TOMOFUMI | European Patent Office | 2015

    Free access

    Best Neighbor Heuristic Search for Finding Minimum Paths in Transportation Networks

    Adler, Jeffrey L. | Transportation Research Record | 1998



    ROUTE FINDING SYSTEM AND ROUTE FINDING METHOD

    ENDO YOSHIHITO | European Patent Office | 2023

    Free access