Research Of Urban Transit Routing Problem Based On An Improved Elitism-based Wolf Colony Algorithm

With the development of urbanization,there are more and more population and vehicles in cities,and now congestion occurs frequently in lots of countries around the world.Congested traffic brings a lot of inconvenience to the life of people,for example,congested traffic increases travel time,travel costs,the incidence of traffic accidents and air pollution,etc.So efficient public transit network,which can bring a lot of convenience to the life of people,are urgently needed and the design problem is also one of the most meaningful problems faced by bus operators and city authorities in the world.But public transit network design problem is one of difficult combinatorial optimization problems and has been proved to be NP-complete problem while its optimal solution is difficult to obtain,it is also a hot research problem in the field of operational research and combinatorial optimization,so it has a strong practical significance to research the problem.Sometimes,the urban transit routing problem(UTRP)can be abstracted to a classical combinatorial optimization problem-TSP problem.Therefore,nowadays,more and more researchers apply the methods which are used for TSP problems to solve urban transit routing problems,such as swarm intelligence algorithm.Wolf colony algorithm,which is proposed according to wolves’ predatory behavior,is an emerging swarm intelligence algorithm,and because of its advantages of high precision,fast convergence and strong robustness,it has attracted many researchers’ attention since it was proposed.But wolf colony algorithm also has some shortcomings,such as the algorithm is too complex and needs too many parameters.In this paper,an improved wolf colony algorithm based on elitism is proposed(EWCA),it has simplified the process and decreased the control parameters of wolf colony algorithm and is used to solve the TSP problem.Then,the paper proposes a humanized model which focuses more on the passenger experience after careful study on the urban transit routing problem,and applies the improved wolf colony algorithm to solve this model.The main work of this paper is summarized as follows:1.In order to overcome the shortcomings of the complicated process and too many control parameters of wolf colony algorithm,in this paper,the summoning behavior and siege behavior of wolf colony algorithm is abstracted as an aggregation behavior,because these two behaviors both aim to let other individuals in the wolf colony close to the best individual essentially.This not only simplifies the process of the original wolf colony algorithm but also removes the siege step and the attack step in the original wolf colony algorithm,so reducing the control parameters of the algorithm.2.The improved wolf colony algorithm is applied to solve the TSP problem.In the process of implementation,a new local optimization operator is proposed based on the 2-opt operator and the new operator is used in the process of aggregation behavior to optimize the solution sequence.In the wandering behavior of wolves,the solution sequence is optimized by 2-opt operator.In order to prove the effectiveness of the algorithm proposed in this paper,14 data sets in TSPLIB library are simulated and the results are compared with other 7 algorithms in the references.3.Propose a new urban transit routing model which pays more attention to the feeling of passengers,this model not only considers the passenger’s journey time,transfer time,transfer times but also considers passenger’s disgust feeling as to transfer.According to this model,the paper designs the implementation of improved wolf colony algorithm to solve the urban transit routing problem;the implementation includes the process of routes initialization,wandering behavior and aggregation behavior of wolves.At last,the simulation experiments are carried out on Mandl traffic network,and the conditions of 4 routes,6 routes,7 routes and 8 routes are discussed.The experiment results show the feasibility and effectiveness of the proposed algorithm comparing with other 13 algorithms in the references.