Elsevier

Biosystems

Volume 105, Issue 3, September 2011, Pages 225-232
Biosystems

Traffic optimization in railroad networks using an algorithm mimicking an amoeba-like organism, Physarum plasmodium

https://doi.org/10.1016/j.biosystems.2011.05.001Get rights and content

Abstract

Traffic optimization of railroad networks was considered using an algorithm that was biologically inspired by an amoeba-like organism, plasmodium of the true slime mold, Physarum polycephalum. The organism developed a transportation network consisting of a tubular structure to transport protoplasm. It was reported that plasmodium can find the shortest path interconnecting multiple food sites during an adaptation process (Nakagaki et al., 2001. Biophys. Chem. 92, 47–52). By mimicking the adaptation process a path finding algorithm was developed by Tero et al. (2007). In this paper, the algorithm is newly modified for applications of traffic distribution optimization in transportation networks of infrastructure such as railroads under the constraint that the network topology is given. Application of the algorithm to a railroad in metropolitan Tokyo, Japan is demonstrated. The results are evaluated using three performance functions related to cost, traveling efficiency, and network weakness. The traffic distribution suggests that the modified Physarum algorithm balances the performances under a certain parameter range, indicating a biological process.

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)

  • J. Jones

    Approximating the behaviors of Physarum polycephalum for the construction and minimisation of synthetic trasport networks

    Lect. Notes Comput. Sci.

    (2009)
  • J. Jones

    Influences on the formation and evolution of Physarum polycephalum inspired emergent transport networks

    Nat. Comput.

    (2010)
  • N. Kamiya et al.

    Studies on the velocity distribution of the protoplasmic streaming in the myxomycete plasmodium

    Protoplasma

    (1958)
  • J.P. Keener et al.

    Mathematical Physiology

    (1998)
  • Cited by (58)

    • Physarum-inspired multi-commodity flow dynamics

      2022, Theoretical Computer Science
      Citation 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.

    View all citing articles on Scopus
    View full text