基于精英策略的改进狼群算法在城市公交路线问题中的研究

发布时间：2018-06-18 08:44

本文选题：城市公交路线问题 + 群智能　；参考：《吉林大学》2017年硕士论文

【摘要】：随着城市化的发展,城市人口和车辆也越来越多,不管在世界的哪个城市,交通堵塞现象发生的都越来越频繁。拥挤的交通给人们生活带来很多不便,如人们在路上花费的时间增多、交通事故发生的几率增大,大气污染越发严重等。所以各个城市均亟需一个可以给人们生活带来便利的高效交通系统,同时设计一个高效的公交路线对于运营商和当地政府来说也是一件具有现实意义的事情。但是城市公交路线设计问题是一个很难求得最优解的NP难问题,同时也是运筹学领域和组合优化领域的热点研究问题,具有很强的现实研究意义。城市公交路线设计问题在一定程度上可以抽象为经典的组合优化问题-旅行商问题(TSP),所以近年来许多研究者纷纷利用求解TSP问题的方法,如群智能优化算法,对城市公交路线设计问题进行求解。狼群算法作为一种模拟狼群捕食行为的新兴群智能优化算法,具有寻优精度高,收敛速度快和鲁棒性强等优点,所以一经提出便受到众多研究者的关注。但是狼群算法也存在一些自身的缺陷,如算法复杂,参数过多等。本文主要对狼群算法进行了改进,简化了狼群算法的流程和控制参数从而提出了一种基于精英策略的改进狼群算法,并利用该算法对经典组合优化问题TSP问题进行了求解。然后在认真研究城市公交路线设计问题之后提出了更关注乘客乘车感受的人性化模型,并将改进的狼群算法应用于城市公交路线设计优化问题中。本文的主要研究工作概述如下:1、针对狼群算法过程复杂难以理解和控制参数过多等缺点,本文将狼群算法的召唤行为和围攻行为抽象为一种聚集行为,因为这两种行为本质上都是让狼群中的其他个体向最优个体靠拢。这样不仅简化了原始狼群算法的过程而且还去掉了狼群算法中的围攻步长和奔袭步长等参数,减少了算法的控制参数。2、利用改进的狼群算法求解TSP问题,在求解过程中本文提出了一种新的局部优化算子即聚集优化算子。该算子是基于2-opt算子实现的,并在狼群的聚集行为中对解序列进行优化,而在狼群的游走行为中主要通过2-opt算子对解序列进行优化。为了证明该算法在求解TSP问题中的有效性,本文对TSPLIB库中的12个数据集进行了仿真实验,并将实验结果与文献中的其他8种算法进行对比。3、提出了一种更加关注乘客乘车感受的城市公交路线设计模型,该模型不仅考虑了乘客的乘车时间、转车时间、转车次数还考虑了转乘给乘客带来的烦感。针对该模型本文设计了利用改进狼群算法求解城市公交路线设计问题的具体实现方法,主要包括路线初始化、狼群算法的游走行为和聚集行为。最后本文在Mandl交通网络上进行了仿真实验,并分别对4条路线、6条路线、7条路线和8条路线的情况进行了讨论,并将实验结果与文献中的其他13种算法进行了对比,结果证明了算法的可行性和有效性。
[Abstract]:With the development of urbanization, there are more and more urban population and vehicles, no matter which city in the world, traffic jams occur more and more frequently. The crowded traffic brings a lot of inconvenience to people's life, such as the increase of time spent on the road, the increase of the probability of traffic accidents, the more serious the air pollution and so on. Therefore, every city needs an efficient transportation system which can bring convenience to people's life, and it is also of practical significance to design an efficient bus route for operators and local governments. However, the problem of urban bus route design is a NP-hard problem which is difficult to find the optimal solution, and it is also a hot research problem in the field of operational research and combinatorial optimization, which has a strong practical significance. To some extent, the urban bus route design problem can be abstracted as a classical combinatorial optimization problem-traveling salesman problem (TSPP). So in recent years, many researchers have used methods to solve tsp, such as swarm intelligence optimization algorithm. The problem of urban bus route design is solved. As a new intelligent optimization algorithm for simulating predation behavior of wolves, wolf swarm algorithm has many advantages, such as high precision, fast convergence and strong robustness, so it has attracted many researchers' attention once it is proposed. But the wolf swarm algorithm also has some defects, such as complex algorithm, too many parameters and so on. In this paper, we improve the wolf swarm algorithm, simplify the flow and control parameters of the algorithm, and then propose an improved wolf swarm algorithm based on elitist strategy, and use this algorithm to solve the tsp problem of the classical combinatorial optimization problem. Then the humanized model of paying more attention to the passenger's experience is put forward after studying the problem of urban bus route design seriously, and the improved wolf swarm algorithm is applied to the optimization problem of urban bus route design. The main research work of this paper is summarized as follows: 1. In view of the complexity of the wolf swarm algorithm and the complexity of control parameters, this paper abstracts the call behavior and besieging behavior of the wolf swarm algorithm as a kind of aggregation behavior. Because both actions essentially bring the rest of the pack closer to the optimal individual. This not only simplifies the process of the original wolf swarm algorithm, but also removes the parameters such as the besieged step size and the running step size of the wolf swarm algorithm, reduces the control parameter of the algorithm, and uses the improved wolf swarm algorithm to solve the tsp problem. In this paper, a new local optimization operator, aggregative optimization operator, is proposed. This operator is based on the 2-opt operator and optimizes the solution sequence in the aggregation behavior of the wolves, while the 2-opt operator is used to optimize the solution sequence in the walk behavior of the wolves. In order to prove the effectiveness of the algorithm in solving tsp problem, this paper makes a simulation experiment on 12 datasets in TSPLIB database. By comparing the experimental results with the other eight algorithms in the literature, a new urban bus route design model is proposed, which not only considers the passenger's travel time and transit time, but also puts forward a city bus route design model, which pays more attention to the passenger's experience. The number of transfers also takes into account the annoyance of passengers. According to the model, this paper designs a method to solve the problem of urban bus route design using improved wolf swarm algorithm, which mainly includes route initialization, walk-away behavior and aggregation behavior of wolf swarm algorithm. Finally, the simulation experiments are carried out on Mandl traffic network, and the cases of 4 routes, 6 routes, 7 routes and 8 routes are discussed, and the experimental results are compared with the other 13 algorithms in the literature. The results show that the algorithm is feasible and effective.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U491.17;TP18

【相似文献】