A Solution to Best Itinerary Problem Based on Strategy Set under Dijkstra Algorithm

Abstract:

The best itinerary problem has been a heat topic for several decades. Among those sophisticated methods used for choosing paths, Dijkstra algorithm is a simple but powerful method. However, Dijkstra algorithm is restricted because of 3 reasons. Firstly, the weight of each path must be a constant value. Secondly, the algorithm only represents the best path, disregards the second and third best paths. Thirdly, the weights only represent a single variable, which cannot be used to represent two different variables simultaneously. In this paper, we use a Filtering Algorithm based on Lagrange relaxation method and ordinal selection to overcome these weaknesses. In our OLR Dijkstra algorithm, strategy set of choosing paths shows a strong stability and reliability facing different probabilities situations. Only 13.2% diversity degree was found when path efficiency varied from 100% to 11.1%. Smallest time complexity of the OLR Dijkstra algorithm is 2 times than normal Dijsktra, which is .

• Periodical: Applied Mechanics and Materials (Volumes 333-335)
• Pages: 1442-1445
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.333-335.1442
• Online since: July 2013
• Authors: Nan Chu Guo
• Keywords: Dijkstra Algorithm, Itinerary Problem, Strategy

References

[1] Apt, k.R. (2002). Edsger Wybe Dijkstra (1930–2002): A Portrait of a Genius. Formal Aspects of Computing, Vol. 14, 92-98.

DOI: 10.1007/s001650200029

[2] Chamero, J. (2006). Dijkstra's Algorithm As a Dynamic Programming Strategy. Available from : http: /www. intag. org/downloads/ds_006. pdf [Accessed 20 Dec 2011].

[3] Dijkstra, E.W. ( 1995). Go to Statement Considered Harmful. Communications of the ACM, Vol. 11, 147-148.

[4] Gao, W. and Zhang, J.B. (2004). The Analysis and Realization of The Optimum Route Algorithm Base on Grid Data Modeling. Journal of Heilongjiang Institute of Technology , Vol. 3, 22-24.

[5] Jorgen, B. and Gregory, G. (2002). Theories, Algorithm and Applications of Directed Graph. London: Springer.

[6] Le, Y. and Gong, J. Y. (1999). Algorithm of Dijkstra the shortest route is realized high-efficiently. Journal of Wuhan University of Survey and drawing, 24(3), 209-212.

[7] Ni, Z. and Wu, S. (2007). Alternate Integral-formulation Method for Predicting Acoustic Radiation. Journal of Computational Acoustics, vol. 15, 81-93.

DOI: 10.1142/s0218396x07003226

[8] Wu, X. (2002), Principle and method of Geographical Information System. Beijing Electronic Industry Press.