Researches On Physarum Polycephalum Inspired Algorithms For Traffic Network Design Problems

The transportation networks play a vital role in people’s lives. In recent years, with the expansion of many cities, more and more people come into these cities, which leads to bigger and bigger traffic demand. In addition, with the increase of people’s income, there are more and more activities among these cities. As both the population and private cars increase rapidly, the traffic is faced with unprecedented difficulties and challenges. Traffic jam not only leads to the waste of resources, but also the serious pollution to the environment. In the transportation system, the design, construction and use of each road has an important influ-ence on people’s behavior. Reasonable transportation system can alleviate the phenomenon of road congestion to some extent. As a consequence, how to design a network with high efficiency, low cost, and good fault tolerance has become a serious problem to be settled.Recent studies show us that a single cell organism, called Physarum polycephalum, dis-plays its amazing intelligence in network design, analysis and optimization. In biology exper-iments, the foraging tube network connecting each food sources that emphPhysarum forms, is comparable to real-world Tokyo rail network in cost, efficiency and fault tolerance. Thus, a new idea for addressing the network design problem has been proposed in this paper, which is based on the network optimizing mechanisms of Physarum.In this paper, we first extend the original Physarum model into directed networks. Based on this model, we take into consideration the demand existing in the users and build a math-ematical model to deal with the network design problem based on Physarum. Furthermore, we have implemented it into Mexico highways, China highways and the supply chain network design. Finally, we evaluate the performance of these generated networks according to several specific parameters. Specifically, our work can be divided into the following parts:(1) Extending the original Physarum model into directed networksAs extend the original Physarum model is only designed to solve the shortest path prob-lem in undirected networks, we extend its application fields. By modifying Kirchhoff’s law and inserting a check procedure (if the direction of the edge is not in consistent with the pressures associated with the corresponding nodes, then the flux of this edge will be0). By this way, we build the Physarum’s model for directed networks. Besides, we have proved the convergence of the proposed method and compared it with Dijkstra algorithm.(2) Building the model for solving the shortest path tree problem based on Physarum modelBased on the modified model, we have modified the model further. We regard the root node in the shortest path tree as the source node and the other nodes as the ending nodes. Then we make full use of Physarum model to deal with this problem. By testing on the networks with different sizes, we have verified the efficiency of the proposed Physarum model.(3) Constructing the mathematical model for the shortest path tree problem in dynamic graphsIn practical environments, the weight related with each edge will vary with time, under this circumstance, how to reconstruct the shortest path tree become a worthwhile problem. As the traditional algorithms have many disadvantages, we have verified the adaptivity of the Physarum from the view of weight increase, weight decrease, and mixed weight change. By testing on the networks with different sizes and topologies, we have proved the effectiveness of the proposed model.(4) Establishing the Physarum-inspired model for network designDuring Physarum’s foraging for food, it consumes its energy while it also absorb energy from around environment. During this process, it adapt itself to the optimal network struc-ture. By making full use of this mechanism, based on the O-D demand, we run Physarum algorithm for one iteration, record the flux at this moment, and employ Physarum to optimize the network. We have successfully applied this model into Mexican highways and China high-ways. By filtering out the edges with flux less than a fixed threshold value, we can generate many networks. In addition, we have analyzed the pros and cons of these networks according to some parameters.(5) Applying Physarum model into the supply chain network designIn the supply chain network, the weight of each edge will happen to change with the time. Here, we make full use of the continuity of the flow lying in the Physarum and its adaptivity to solve this problem.