Traffic optimization in railroad networks using an algorithm mimicking an amoeba-like organism, Physarum plasmodium
Introduction
Most biological organisms have transportation networks used to distribute oxygen, nutrients, waste materials, etc. throughout the body. Animals including humans have blood-vessel networks. Plants have leaf veins and vessels (Nelson and Dengler, 1997). By expanding this to populations of insects, human beings, and vehicles, ant-foraging trails (Deneubourg et al., 1989) and road grids (Barthelemy and Flammini, 2008) can be included as examples of the transportation networks. This study investigates traffic optimization problems in transportation networks such as railroads using an algorithm that was biologically inspired by an amoeba-like organism, plasmodium of true slime mold Physarum polycephalum.
The plasmodium is a multinucleated unicellular organism, namely, it includes thousands of nuclei. Consequently, it can be large, with size ranging from 10 μm to 1 m. To distribute nutrients, oxygen, organelles, etc. throughout the cell body, the organism has developed an extraordinary cell system: the cell itself is a transportation network consisting of a tubular structure. Inside of the tubes, protoplasmic shuttle streaming transports the substances (Kamiya and Kuroda, 1958).
It was reported that the plasmodium can solve a maze by finding the shortest path linking two food sites set as a start and a goal through the adaptation process of the transportation network (Nakagaki et al., 2000, Nakagaki et al., 2008). This finding has attracted a lot of theoreticans by a possibility of Physarum computing (Adamatzky, 2007, Adamatzky, 2008, Adamatzky, 2010, Adamatzky and Jones, 2008, Jones, 2009, Jones, 2010, Miyaji and Ohnishi, 2008, Miyaji et al., 2008). Tero et al., 2007, Tero et al., 2010a developed a shortest path finding algorithm mimicking that adaptation process. In this application, a network topology of a maze was given. A start and a goal were set as two food sites as well as the experimental setup. Finally, a solution was obtained as the shortest path connecting the two food sites.
The Physarum algorithm was also applied to a network design for a newly established railroad network (Tero et al., 2008, Tero et al., 2010b). They started from a random mesh network. Food sites were set at station locations, whose quantities were set as equivalent. Finally, the solution was obtained as the optimized design of the network under the condition that the locations of the stations were given.
This study examines a traffic optimization problem under the constraint that the network topology including locations of stations and the connections is given. Food sites were also set at stations, but the food quantities were set as proportional to the passenger number, which is useful for practical problems such as assessment of already established infrastructure such as railroad, highway roads, and power grid. For this, the algorithm is newly modified. Then it is applied to a practical problem of the railroad network in the Tokyo metropolitan area, Japan. Finally, the results are evaluated with three performance functions related to cost, traveling efficiency, and network weakness.
Section snippets
Model
The shortest path finding algorithm mimicking Physarum plasmodium developed by Tero et al. (2007) was modified to calculate the traffic distribution in a network. Then the modified Physarum algorithm was applied to a railroad network in metropolitan Tokyo, Japan. A simple method using Dijkstra's algorithm was also introduced for comparison with the modified Physarum algorithm. Numerical calculations were performed using an iMac personal computer (Apple Computer Inc.) (CPU: Core 2 Duo; Intel
Results
First, the modified Physarum algorithms were tested in simple networks for evaluation of the three selection methods—TPS, MPS, and CMPS—in Section 3.1. Second, the most practical method was applied to JR lines in Section 3.2. Then, Dijkstra's algorithm was also applied to JR lines to compared with the modified Physarum algorithm in Section 3.3. Finally, the algorithm was evaluated using performance functions in Section 3.4.
Discussion
The modified Physarum algorithms were applied to the simple networks in Section 3.1. Although CMPS is the most stable method to calculate the traffic distribution, MPS(10) is expected to be a more practical method considering the calculation time for larger networks such as practical railroad networks.
The traffic distribution was calculated using MPS(10) for JR lines in Section 3.2. The correlation coefficient between the practical systems and the calculation result was obtained under various
Conclusion
The traffic optimization problem for existing infrastructure was investigated using the modified Physarum algorithm. Calculation results were evaluated using three performance functions related to cost, traveling efficiency, and network weakness. It was elucidated that the traffic distribution suggested by the Physarum algorithm balances the performance under a certain range of parameters used in the growth function of tube thickness. Surprisingly, in the same parameter range, which indicates
Acknowledgments
The authors thank Dr. K. Ito, Hiroshima University, and Mr. M. Yamaguchi, Meiji University, for helpful discussion. This work is partly supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan awarded to A.T.
References (28)
- et al.
Towards Physarum robots: computing and manipulating on water surface
J. Bion. Eng.
(2008) - et al.
Putative graviperception mechanisms of protists
Adv. Space Res.
(1999) - et al.
A mathematical model for adaptive transport network in path finding by true slime mold
J. Theor. Biol.
(2007) Physarum machines: encapsulating reaction-diffusion to compute spanning tree
Naturwissenschaften
(2007)Growing spanning trees in plasmodium machines
Kybernetes
(2008)Physarum Machines: Computers From Slime Mold
(2010)- et al.
Modeling urban street patterns
Phys. Rev. Lett.
(2008) - et al.
The blind leading the blind: modeling chemically mediated army ant raid patterns
J. Insect Behav.
(1989) - East Japan Railway Company, Passengers at Stations. East Japan Railway Company. URL...
Toshi Kotsu Nenpo H19
(2008)
Approximating the behaviors of Physarum polycephalum for the construction and minimisation of synthetic trasport networks
Lect. Notes Comput. Sci.
Influences on the formation and evolution of Physarum polycephalum inspired emergent transport networks
Nat. Comput.
Studies on the velocity distribution of the protoplasmic streaming in the myxomycete plasmodium
Protoplasma
Mathematical Physiology
Cited by (58)
PANDA: A physarum-inspired algorithm to solve the multi-objective discrete network design problem
2024, Expert Systems with ApplicationsFlow-network adaptation and behavior in slime molds
2024, Fungal EcologyFlow modes provide a quantification of Physarum network peristalsis
2023, Fungal EcologyPhysarum-inspired multi-commodity flow dynamics
2022, Theoretical Computer ScienceCitation Excerpt :We will see that the dynamics forms nice networks similar to the networks in [42]. This paper is inspired by [41], [45], and [42]. We already explained the connection to these papers in detail in the previous sections.
An adaptive amoeba algorithm for shortest path tree computation in dynamic graphs
2017, Information Sciences