基于多头绒泡菌的交通网络设计算法的研究

发布时间：2018-11-16 18:31

【摘要】：交通网络在人们的日常生活中发挥着重要的作用。近几年,随着城市的扩张,越来越多的人涌入城市,城市内部的交通需求越来越大。另外,随着居民收入的升高,城市之间的社会活动日渐频繁。随着城市人口与私家车的迅速增加,城市交通遇到了前所未有的困难与挑战。交通拥堵现象日益严重,不仅造成了资源的浪费,同时对环境产生了严重的污染。在交通系统中,道路的设计、建设和使用,对用户行为有着重要的影响。合理的交通系统能够在一定程度上减轻道路拥堵现象。因此,如何设计高效,费用低,容错率高的网络成为摆在我们面前的一个亟待解决的问题。根据最近的研究发现,一种名为多头绒泡菌(Physarum polycephalum)的单细胞生物在网络设计、分析与优化方面展现出了惊人的智能特性。在生物实验中,它所设计出的连接各食物源的觅食管道网络在成本、效率和容错性等方面都堪比实际的东京铁路网络。因此,本文提出了基于智能仿生对象-多头绒泡菌的网络优化机理,构提出了构建交通网络的模型。本文首先对多头绒泡菌路径寻优模型进行了拓展,提出了有向网络中的多头绒泡菌路径寻优模型。基于此模型,结合用户的需求情况,建立了路网设计模型,并且将其应用到Mexio路网,中国高速路网以及供应链网络的设计当中。最后,通过具体的参数指标对构建的网络进行了评估。具体来说,本文的工作可以分为以下几个部分：(1)将多头绒泡菌路径寻优模型扩展到有向网络中针对原有模型仅仅适用于无向网络的缺陷,我们对其进行了拓展。通过修改基尔霍夫定律,嵌入检查程序(一旦发现边的方向信息与对应的节点压力信息不符时,我们将这条边的流量修改为0),我们建立了多头绒泡菌解决有向网络路径寻优的模型。同时,我们证明了该模型的收敛性,并且与Dijkstra算法进行了对比。(2)基于多头绒泡菌的最短路径树算法基于有向网络中的多头绒泡菌模型,我们进一步进行了改进。我们将最短路径树中的根节点当作起点,其他的节点当作终点,利用多头绒泡菌算法解决了最短路径树问题。通过在网络上的测试,多头绒泡菌模型得到的结果有效。(3)在动态网路中,基于多头绒泡菌的最短路径树模型在实际中,网络的权重会随着时间而发生变化,因此,在这种情况下,如何重建最短路径树成为一个值得研究的问题。针对传统算法的缺陷,我们从权重增加、权重减少以及权重混合变化三个方面研究了多头绒泡菌算法的自适应性。我们通过在不同的网络上测试之后并且与其他算法相比较,实验结果表明我们提出的算法准确有效。(4)基于多头绒泡菌的路网设计模型多头绒泡菌在觅食的过程中,既要消耗能量,又会从周围的环境中摄取能量,因此,它在不断调整自身的网络结构使之达到最优。利用该机制,我们基于初始的O-D需求,我们通过多头绒泡菌算法迭代一次,记录此时的流量矩阵,再利用多头绒泡菌模型进行优化。我们成功的将该模型应用到Mexico路网以及中国高速路网,通过过滤流量阈值的方式构建了不同的网络拓扑结构。另外,我们通过相关的参数分析了这些网络的优劣。(5)将多头绒泡菌应用到供应链网络设计在供应链网络中,网络中边的花费会随着流量的大小而变化。我们充分利用了多头绒泡菌流量变化的连续性以及多头绒泡菌的自适应性来求解该问题。
[Abstract]:The traffic network plays an important role in people's daily life. In recent years, with the expansion of the city, more and more people have poured into the city, and the traffic demand inside the city is getting more and more large. In addition, with the rise of the income of the residents, the social activities among the cities are becoming more and more frequent. With the rapid increase of the urban population and the private car, the urban traffic has encountered an unprecedented difficulty and challenge. The phenomenon of traffic congestion is becoming more and more serious, which not only causes the waste of resources, but also has serious pollution to the environment. In the traffic system, the design, construction and use of the road have an important influence on the user's behavior. A reasonable transportation system can reduce the road congestion to a certain extent. Therefore, how to design a network with high efficiency, low cost and high fault tolerance becomes an urgent problem to be solved before us. According to a recent study, a single-cell organism called Physarum polyphylum has shown an amazing intelligence in the design, analysis and optimization of the network Characteristics. In a biological experiment, the network of feed-feed pipelines to which each food source is designed is comparable to the actual Tokyo railway in terms of cost, efficiency, and fault tolerance. Therefore, this paper puts forward the network optimization mechanism based on the intelligent bionic object-multi-head velour, and put forward the construction of the traffic network. In this paper, the paper first on the development of the optimal model of the multi-head corduroy, and put forward the multi-head velvet-producing way in the network. Based on this model, the road network design model is established and applied to the Mexio road network, China's high-speed road network and the supply chain network. and finally, through the specific parameter index to the constructed network, In particular, the work of this paper can be divided into the following parts: (1). to a defect that is only available to the network for the original model in the network, I By modifying the Kirchhoff's law, the embedded check program (once the direction of the discovery edge does not match the corresponding node pressure information, we change the flow of this edge to 0), and we have set up a multi-headed pile to solve the problem In the same time, we prove the convergence of the model, and it is related to Dijkstr. a. The algorithm is compared. (2) Based on the multi-head fleece The shortest path tree algorithm of the bacteria is based on the multi-head-pile-cell model in the network We have further improved. We use the root node in the shortest path tree as the starting point, and the other nodes are used as the end points. The method solves the problem of the shortest path tree. and (3) in a dynamic network, In practice, the shortest path tree model of the head-pile bacteria is in practice, and the weight of the network changes over time, so how to rebuild the shortest path in this case The path tree becomes a problem worthy of study. For the defects of the traditional algorithm, I the weights are increased, the weight is reduced, and the weight mixing changes three In this paper, the self-adaptation of the multi-head velour algorithm is studied in this paper. sex. By testing on different networks and with other algorithms The results show that the proposed algorithm is accurate and effective. Energy, in turn, takes energy from the surrounding environment, so it makes it the most important to constantly adjust its network structure Excellent. With this mechanism, we are based on the initial O-D requirements, we have passed through a multi-head pile-bubble algorithm to iterate one step. times, Record the flow matrix at this time, and then use the multi-head velvet model for optimization. We successfully applied the model to the Mx ico road network and medium The country's high-speed road network is constructed differently by filtering the flow threshold In addition, we analyzed the advantages and disadvantages of these networks through related parameters. The design of the chain network in the supply chain network In the network, the cost of the edge in the network varies with the size of the traffic. We make full use of
【学位授予单位】：西南大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：U491.1;TP301.6

【参考文献】