A New Route Optimization Algorithm for Rapid Decision Support 912818

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.


Subscribers can view annotate, and download all of SAE's content. Learn More »


Members save up to 43% off list price.
Login to see discount.
Special Offer: With TechSelect, you decide what SAE Technical Papers you need, when you need them, and how much you want to pay.