A New Route Optimization Algorithm for Rapid Decision Support

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.