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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Time-constrained heuristic search for practical route finding


    Weitere Titelangaben:

    Titel japanisch


    Beteiligte:
    Hiraishi, H. (Autor:in) / Ohwada, H. (Autor:in) / Mizoguchi, F. (Autor:in)


    Erscheinungsdatum :

    1999


    Format / Umfang :

    9 Seiten, 13 Quellen



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Japanisch




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

    TANIZAKI DAISUKE / SHIBATA TOMOFUMI | Europäisches Patentamt | 2017

    Freier Zugriff

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

    TANIZAKI DAISUKE / SHIBATA TOMOFUMI | Europäisches Patentamt | 2015

    Freier Zugriff

    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 | Europäisches Patentamt | 2023

    Freier Zugriff