The Urban Path Routing Adjustable Optimization by Means of Wavelet Transform and Multistage Genetic Algorithm

Document Type : Research Paper


1 Department of Aerospace Engineering, Sharif University of Technology, 1458889694 Tehran, Iran

2 Department of Mechanical Engineering, Ramsar Branch, Islamic Azad University, Ramsar, Iran

3 Department of Physics, Neka Branch, Islamic Azad University, Neka, Iran


This paper introduces the optimization algorithm to improve search rate in urban path routing problems using viral infection and local search in urban environment. This algorithm operates based on two different approaches including wavelet transform and genetic algorithm. The variables proposed by driver such as degree of difficulty and difficulty traffic are of the essence in this technique. Wavelet transform as the first part of proposed algorithm derives edges risk. Finally, multistage genetic algorithm operates to find the optimal solution which is defined as the shortest path. The proposed algorithm is applied to the case study. The performances of the algorithm is investigated by comparing with other methods.


Main Subjects

[1] McQuillan, J., Richer, I., & Rosen, E., The new routing algorithm for the ARPANET, IEEE Transactions on Communications28(5), 1980, 711-719.
[2] Frank, H., Shortest paths in probabilistic graphs, Operations Research17(4), 1969, 583-599.
[3] Beigy, H., & Meybodi, M. R., Utilizing distributed learning automata to solve stochastic shortest path problems, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems14(05), 2006, 591-615.
[4] Misra, S., & Oommen, B. J., Dynamic algorithms for the shortest path routing problem: learning automata-based solutions, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)35(6), 2005, 1179-1192.
[5] Burton, D., On the inverse shortest path problem, Département de Mathématique, Faculté des Sciences, Facultés Universitaires Notre-Dame de la Paix de Namur, 1993.
[6] Waller, S. T., & Ziliaskopoulos, A. K., On the online shortest path problem with limited arc cost dependencies, Networks: An International Journal40(4), 2002, 216-227.
[7] Pritchard, D., & Thurimella, R., Fast computation of small cuts via cycle space sampling, ACM Transactions on Algorithms (TALG)7(4), 2011, 46.
[8] T. time-volume function Studies, Tehran Comprehensive Transportation and Traffic Studies (TCTTS), a division of the Municipality of Tehran, Tehran, 1995.
[9] Zitzler, E., Evolutionary algorithms for multiobjective optimization: Methods and applications, ed. 63, Ithaca: Shaker, 1999.
[10] Satoh, H., Minimal generation gap model for GAs considering both exploration and exploitation, In Proc. of the 4th International Conference on Fuzzy Logic, Neural Nets and Soft Computing, 1996, 494-497.
[11] Pourtakdoust, S. H., & Zandavi, S. M., A hybrid simplex non-dominated sorting genetic algorithm for multi-objective optimization, International Journal of Swarm Intelligence & Evolutionary Computation5(3), 2016, 1-11.
[12] Gouveia, L., Simonetti, L., & Uchoa, E., Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs, Mathematical Programming128(1-2), 2011, 123-148.
[13] Hao, H., & Barooah, P., Stability and robustness of large platoons of vehicles with doubleā€integrator models and nearest neighbor interaction, International Journal of Robust and Nonlinear Control23(18), 2013, 2097-2122.
[14] Alam, A., Fuel-efficient heavy-duty vehicle platooning, Doctoral dissertation, KTH Royal Institute of Technology, 2014. 
[15] Lenzen, C., & Patt-Shamir, B., Fast routing table construction using small messages, In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, 381-390.