This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
A New Route Optimization Algorithm for Rapid Decision Support
Annotation ability available
Sector:
Language:
English
Abstract
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.
Authors
Citation
Bander, J. and White, C., "A New Route Optimization Algorithm for Rapid Decision Support," SAE Technical Paper 912818, 1991, https://doi.org/10.4271/912818.Also In
References
- Cutler, M. R. Potter, R. F. The Effectiveness of Telephone Information Service in Transit US Department of Transportation Urban Mass Transportation Administration February 1984
- Denardo, E. Dynamic Programming: Models and Applications Englewood Cliffs New Jersey Prentice-Hall 1982
- Ford, L. R., Jr. Network Flow Theory 923 The Rand Corporation Santa Monica, CA. 1956
- Dantzig, G. B. “Discrete-Variable Extreme Problems,” Operations Research 5 1957 268 273
- Bellman, R. E. “On a Routing Problem,” Quarterly of Applied Mathematics 16 1958 87 90
- Moore, E. F. “The Shortest Path through a Maze,” Proceedings of the International Symposium on the Theory of Switching, 2 The Annals of the Computation Laboratory of Harvard University 30 1957 Harvard University Press Cambridge, Mass.
- Dijkstra, E. W. “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik 1 1959 269 271
- Hillier, F. S. Lieberman, G. J. Introduction to Operations Research Oakland, CA Holden-Day, Inc. 1986
- Gould, R. Graph Theory Menlo Park, CA Benjamin/Cummings Publishing Company 1988
- Bertsekas, D. P. Dynamic Programming: Deterministic and Stochastic Models Englewood Cliffs, NJ Prentice-Hall 1987
- Denardo, E. Dynamic Programming: Models and Applications Englewood Cliffs, NJ Prentice-Hall 1982
- McCorduck, P. Machines Who Think: A Personal Inquiry into the History and Prospects of Artificial Intelligence San Francisco W. H. Freeman 1979
- Hart, P. E. Nilsson, N. J. Raphael, B. 1968 “A formal basis for the heuristic determination of minimum cost paths.” IEEE Transactions on Systems Science and Cybernetics 100 107
- Dijkstra, E. “A Note on Two Problems in Connection with Graphs,” Numerische Mathematik 1 1959 269 271
- Dreyfus, S. Law, A. The Art and Theory of Dynamic Programming New York Academic Press 1977 57
- Hart, P. E. Nillson, N. J. Raphael, B. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Trans. Systems, Science and Cybernetics 100 107
- Golden, B. L. “Shortest-Path Algorithms: A Comparison,” Operations Research 24 6 November-December 1976 1164 1168
- Golden, B. L. Ball, M. “Shortest Paths with Euclidean Distances: An Explanatory Model.” Networks 8 1978 297 314
- Rich, E. Knight, K. Artificial Intelligence McGraw-Hill Book Company 11 27 89
- Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving Reading, MA Addison-Wesley 1984
- Chakrabarti, P. P. Ghose, S. DeSarkar, S. C. “Heuristic Search through Islands” Artificial Intelligence 29 1986 339 347
- Dechter, R. Pearl, J. “The Optimality of A* Revisited.” Proc of the 3d AAAI Natl. Conf on AI Washington, DC 1983 59 99
- Huyn, N. Dechter, R. Pearl, J. “Probabilistic analysis of the complexity of A* Artificial Intelligence 15 1980 241 54