INTRODUCING A NOVEL METHOD TO SOLVE SHORTEST PATH PROBLEMS BASED ON STRUCTURE OF NETWORK USING GENETIC ALGORITHM
- 1Faculty of Civil Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
- 2The Ministry of Interior of the Islamic Republic of Iran
Keywords: Genetic Algorithm, Shortest path, Network design, multistage process planning, directed acyclic network
Abstract. The shortest path problem is widely applied in transportation, communication and computer networks. It addresses the challenges of determining a path with minimum distance, time or cost from a source to the destination. Network analysis provides strong decision support for users in searching shortest path. A lot of algorithms are designed for solving shortest path but most of them did not considered the conditions of the networks. Genetic Algorithm is a kind of Algorithm that has a lot of efficiency and it can be used for solving many kinds of problems. It also can be used based on the condition of the problems.
In this paper, Genetic Algorithm is used for solving shortest path in multistage process planning (MPP) problem. New mutations as well as crossover parameters are defined for each network based on the conditions of them. The results of our experimental demonstrate the effectiveness of the models.