We describe a new heuristic search algorithm, Interruptible A* (IA*), that we have implemented in a real-world decision aid for users of public transit. IA* is appropriate for shortest path problems where there is value to a suboptimal path returned quickly. We offer an example in which IA* returns an optimal path in a single iteration, and another where the algorithm finds a suboptimal path quickly before converging to the optimal path. Two admissibility conditions are presented, along with empirical results indicating that IA* is effective in both admissible and inadmissible cases.
A New Route Optimization Algorithm for Rapid Decision Support
Sae Technical Papers
Vehicle Navigation & Instrument Systems ; 1991
1991-10-01
Aufsatz (Konferenz)
Englisch
A new route optimization algorithm for rapid decision support
Kraftfahrwesen | 1991
|Decision-support system yields better pipeline route
Tema Archiv | 2000
|ROUTE DECISION DEVICE, ROUTE DECISION METHOD, AND PROGRAM
Europäisches Patentamt | 2022
|Flight Route Optimization With Genetic Algorithm
British Library Conference Proceedings | 2002
|