An enhanced path-optimization algorithm for real-time intelligent transportation systems
Corressponding author's email:
badx@hcmute.edu.vnKeywords:
Dijkstra algorithm, Path-optimization, Intelligent transportation system, robot system, real-time path-finding algorithmAbstract
Development of intelligent robot systems that could efficiently transport goods with the minimal time and high accuracy is an important demand for increasing the productivity of the factory. This paper reports new technologies to improve performance of the Dijkstra algorithm for the path-finding application of the transportation systems. Drawbacks of the conventional searching method are first studied for real-time situations. Two important hypotheses are then considered for the practical applications at which number of the passing nodes and the shape of the passing routine are sufficient conditions for an optimal path. Implementation of the two new features are conducted based on analyses of the conventional one and noting additional optimal objectives. The modified algorithm was successfully deployed and verified both in simulation and experiments. The testing results confirm that the proposed method could reduce the routing time of the robot system down to 14.5% as compared to the classical algorithm.
Downloads: 0
References
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik 1, pp. 269-271, 1959.
P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, pp. 100–107, 1968.
P. E. Hart, N. J. Nilsson, and B. Raphael, “Correction to ’A Formal Basis for the Heuristic
Determination of Minimum Cost Paths,” SIGART Newsletter, vol. 37, pp. 28–29, 1972.
N. J. Nilsson. Principles of Artificial Intelligence. Palo Alto: Tioga Publishing Company, 1980.
R. W. Floyd, “Algorithm 97: Shortest path,” Communications of the ACM, pp. 3-345, 1962
S. Warshall, “A theorem on boolean matrices”. Journal of the ACM, vol. 9, pp.11–12, 1962.
R. Bellman, “On a routing problem,” Quarterly of Applied Mathematics, vol. 16. pp. 87-90, 1958.
S. Knopp, P. Sanders, D. Schultes, F. Schulz, and D. Wagner, “Computing many-to-many shortest paths using highway hierarchies,” In Proceedings of the Workshop on Algorithm Engineering and Experiments, 36–45. New Orleans, Louisiana. .2007, January6.
Y. Huang, Q. Yi, M. Shi, “An improved Dijkstra shortest path algorithm,” in The 2nd International Conference on Computer Science and Electronics Engineering, 2013.
F. B. Zhan and C. Noon. 1998. “Shortest path algorithms: An evaluation using real road networks,” Transportation Science, vol. 32, no. 1, pp. 65-73, 1998.
T. Willhalm, “Engineering Shortest Paths and Layout Algorithms for Large Graphs,” Ph. D. Thesis, Karlsruhe University, 2005.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 2nd Ed. New York: MIT Press and McGraw-Hill, 2001.
Downloads
Published
How to Cite
Issue
Section
Categories
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright © JTE.
