Biological and Shortest-Path Routing Procedures for Transportation
Network Design

arXiv:1803.03528v1 [physics.soc-ph] 7 Mar 2018

François Queyroi∗
CNRS, UMR8504 Géographie-cités (CNRS/Université, Paris-1,
Panthéon-Sorbonne/Université Paris Diderot)

Abstract
Background. The design of efficient transportation networks is an important challenge in
many research areas. Among the most promising recent methods, biological routing mimic local
rules found in nature. However comparisons with other methods are rare.
Methods. In this paper we define a common framework to compare network design method. We
use it to compare biological and a shortest-path routing approaches.
Results. We find that biological routing explore a more efficient set of solution when looking
to design a network for uniformly distributed transfers. However, the difference between the two
approaches is not as important for a skewed distribution of transfers.

1

Introduction

Transportation networks. The transportation network design corresponds to the problem of selecting a set of possible links between locations (for example cities) in order for transfers (for example
of goods, people, etc.) to be made possible [8]. The automated design of transportation network has
a range of applications going from solving transshipment problems [9] to the computation of space
trajectories [17]. In the social sciences, researchers want to compare efficient simulated networks with
the real ones (railroads, railways, etc.) in order to assess the existence and nature of suboptimal
choices [18]. Transportation networks are also important for the simulation of the development of a
city system [23].
The design of transportation networks as a computational problem is part of a large domain of inquiry
which is known as network flow problems [1]. Transportation network design can be here described
as a multi-objective variant of the multi-commodity flow problem [10] with unlimited edge capacities.
While most analytical research focus on cost minimisation, we are looking for transportation
networks that are efficient with respect to multiple criteria. The choice therefore often involves a
cost/benefits analysis. The most common criteria are the time performance (how quickly can we
travel using the network), the cost (the size or total length of the network) and the tolerance to fault
(how travel is affected by random perturbations). Obviously, finding a good balance between these
∗

francois.queyroi@parisgeo.cnrs.fr

criteria make the problem hardly solvable analytically and solutions are often explored using heuristics.
Networks computation models. Several computation models can be used to explore potential
solutions. The first approach is what we call the biological approach. The reason for this name is
that those methods are derived from actual natural phenomena and the most cited one is probably
the behaviour of the Physarum polycephalum organism [27]. This slime mould development is indeed
capable to solving mazes or discover shortest-paths in a difficult terrain [25]. Experiments involving
this organism caught a lot of attention in the scientific press. One important achievement was the
simulation of the Greater Tokyo Area transportation network [26] where the authors introduce an algorithm replicating the behaviour of the organism. It should be noted however that similar behaviours
can be found in other natural phenomena such as ant colonies [7] or current in an electrical network [16].
The second possible approach to the problem of network design is what we call the shortest-path
routing method. We should stress out the fact that this category has known less extensions and led
to less applications than the previous one. To the best of our knowledge, Levinson and Yerra [14] are
the first to study this model of computation. Their objective was to show that a hierarchy of routes
can emerge in the transportation network from a uniform distribution of transfers [28]. This method
has been rediscovered by others in the domain of Information Visualisation [13].
Others methods such as greedy algorithms could be used. The idea is here to incrementally
build a network by adding at each iteration the links that contribute the most to the performance of
the network [5, 22]. A common variant is to start from a minimum cost spanning tree covering all
transfers and then iteratively adding the best alternative routes. The Physarium simulation was actually compared to this approach in [26]. It is also possible to start with a more complete network and
prune the least used paths. This last method actually mimics the development of neural networks [21].
Routing and Reinforcement. Both the biological and shortest-path approaches actually rely
on two common mechanisms. First, the routing of goods (food in the case of the slime mould) is
done by assigning them to paths depending of their “attractiveness” (the diameter of the tubes for
the slime mould). Then, paths attractiveness is updated according to the amount of goods using these
paths (the slime mould’s tubes expand or shrink due to the pressure). We call this second phase reinforcement. By repeating those steps we can mimic a continuous process where the network gradually
appears from a starting grid as least used paths in the grid gradually disappear while others gather
more and more transfers.
Biological routing uses local rules of dispersion. Transfers will be assumed to behave like a liquid
flowing through pipes of various size to reach a sink. On the other hand, the shortest-path method
routes the transfers along the shortest-path between their source and destination. Biological routing
therefore explores different paths even if there are longer while the shortest-path routing only selects
the best paths.
Contribution. The aim of this study is to analyse the differences between biological and shortestpath approaches. We introduce a common framework for the two algorithms. Most of the previous
studies (in particular with the biological models) focus on uniform transfers between locations (either
there is an exchange of commodities or not). However this setting may not be appropriate for different
applications (in urban planning for example) since locations may differ in term of attraction potential.
2

We therefore expand previous definitions of the algorithms in order to take into account arbitrary
transfers distributions between several sources and destinations.
This common framework allows us to compare biological and shortest-path routing only focusing on
the way transfers are routed without the interference of other minor differences. Moreover, we use as
experiments a random generated set of grid-embedded locations and transfers while previous studies
use a few small toy examples or real world configurations.
Biological network design such as the one simulating the Physarum polycephalum organism has
been shown to produce efficient network but was never, to the best of our knowledge, compared to the
shortest-path approach. Our hypothesis is that the shortest-path method while not being as popular
as biologically based approaches in the literature may be worthwhile to pursue if the transfers between
location are modelled according to distributions found in human mobility (such as the gravity model).

2

Reinforced Routing Procedure Overview

Notations. Throughout this paper, we call the support graph G = (V, E, l) a graph (or network)
with nodes (or vertices) set V , edge set E and edge length l : E → R+ . Let n = |V | the number of
nodes and m = |E| the number of edges. We call F : V × V → R+ the transfer matrix between nodes
in G and we call Q : E → R+ a flow distributionPon the network (i.e. the way transfers in F are
distributed along the edges of G). We have F = s,t F (s, t) the total amount of transfers between
the nodes of G. A transportation network on the support graph G is simply a subgraph N = (V, E 0 , l)
of G with E 0 ⊆ E. For edge defined functions such as Q or l and an edge e = (u, v), we may write
Q(u, v) or l(u, v) to refer to Q(e) or l(e).
Networks flows are mostly defined for transfers between a source node and one or several destination nodes. Here Q corresponds to the distribution of the total F units among E i.e. if all units
transferred travel through the network G to reach their destination according to F then Q corresponds
to the number of units that went through each edge. Notice that, for a given G and F , there are
multiple possible values of Q. Although we use the same terminology of flow, we do not expect Q to
respect to classic networks flow rules [1] and we consider G to be undirected without a loss of generality.
Main procedure backbone. We design the procedure so that the differences between biological
and shortest-path approaches only rest on the way transfers are routed. As previously explained, the
procedure can be divided into two parts: the routing of the transfers in F (which gives Q) and the
adaptation of edge length according to the flow Q. The routing depends on the length of the edges of
the network l. Algorithm 1 details this generic procedure. Here, the reinforcement modifies the length
of network edges by modifying σ which can be interpreted as edges’ “diameter” of tubes in the slime
mould organism, the “speed” in a railway network or the “resistance” in an electrical circuit. Notice
that Algorithm 1 does not directly produce a transportation network. Rather, the σ values indicate
whether an edge is likely to be part of an efficient transportation network. For the experiments, we
create a network by selecting edges with a σ value higher than .
Flow routing. The function FlowRouting (line 5) will depend on the chosen method (Biological
or Shortest-Paths routing). We assume that, in both cases, the result Q is a normalized flow i.e. such
3

Algorithm 1: Reinforced Routing of flow F along network G
Input: G = (V, E, l), F : V × V → R+ , α > 0, µ > 1, δ ∈]0, 1],  > 0
Output: σ : E → [0, 1]
1 σ 0 (e) ← 1, e ∈ E;
2 n ← 0;
3 do


l
0
4
G ← G V, E, n ;
σ
5
Q ← FlowRouting(G0 , F );
6
σ n+1 ← δf (Q; µ, α) + (1 − δ)σ n ;
7
n ← n + 1;
8 while max |σ n+1 − σ n | > ;
9 return σ n ;

that Q ∈ [0, 1]m . To do this we simply divide the number of units transferred going through a given
edge by F. The two following sections will describe each routing procedure in details.
Reinforcement. First, notice Q is an aggregation of transfers with different sources and destinations. Previous works [26] used to adapt network edges after the routing of a single line of F (the
transfers connecting a single node s) or a single exchange in F (the transfers between s and t). This
obviously requires to take lines or elements of F in a random order. This approach may speed up
the convergence of the procedure but we believe this addition of randomness is of little interest in the
context of our study.
In Algorithm 1, support network’s edges’ resistance σ is modified according to a reinforcement
function f and an update rate δ (line 6). The latter is a parameter that influences the convergence
rate of the algorithm. In previous studies, this parameter was often implicit: the reinforcement is
defined as a change in resistance over time in a continuous fashion so the convergence speed is given
by the way time is split into steps.
The reinforcement function (sometimes called “value function”) f we use is a logit-like function frequently used in the literature [25].

f (Q; µ, α) =

(1 + α)Qµ
1 + αQµ

(1)

Function f is a response function where parameter µ > 1 controls the slope of the curve while
parameter α > 0 controls the inflection point of the function. Indeed the higher α is the greater is
the response value of small signals (see examples of curves with various values of α in Fig. 1). In the
biology analogy, this function models the responses to the flow going through the Physarium tubes.
We initialize σ 0 (e) = 1, ∀e ∈ E (line 1) and, since f is dimensionless with f (0) = 0 and f (1) = 1, we
have σ n ∈ [0, 1]m at each iteration of the algorithm. The length edges of the modified support graph
G0 will increase (line 4) which will affect the next routing phase.
Running time. The stopping condition of the algorithm (line 8) depends of the difference in the
4

Figure 1: f (q; µ, α) for µ = 1.8 and different values of α

distribution of σ values between successive steps. The parameter  is used to set the precision of the
algorithm (in this study we used  = 5.10−4 ). Previous definition of the Physarium algorithm uses a
arbitrary number of iterations instead.
The convergence of resistance σ to a stable solution has been studied in the case of the Physarium
solver [19, 11]. In our case, Algorithm 1 seems to always converge to a solution whether we use biological or shortest-path routing although the number of steps required for the shortest path routing
procedure is lower.
The running time of function FlowRouting may also be affected by the ordering of the vertices.
This is true whether we adopt the biological or the shortest-path routing procedure (described below).
In both cases, we only need to route the transfers connected to the minimal vertex cover of the graph
formed with the transfers in F higher than 0. The reason is that the flow we compute is an aggregation
of different “commodities” (we can not exchange a person travelling from a to b with one going from c
to d). Both routing procedure will route one “commodity” (the people travelling from a to b or from
a to c) at a time. We can find a small enough vertex cover by taking vertices in decreasing order of
their number of strictly positive transfers.
An implementation of the two procedures is available at https://github.com/fqueyroi/tulip_
plugins/tree/master/TransportationNetworks as plugins for the Tulip software [2] http://tulip.
labri.fr.

2.1

Shortest-path routing

Using the shortest-path model, the flow going through support network’s edges is given by what we
call the flow betweenness. Informally, flow betweenness corresponds to the total number of travellers
going through a given edge if the travellers choose the fastest (shortest) route. In the general case, we
5

should therefore have:
X

Q(e) =

(s,t)∈V ×V

πe (s, t)
F (s, t)
π(s, t)

(2)

where πe (s, t) is the number of shortest-paths from node s to t going through edge e and π(s, t) is the
total number of shortest paths from node s to t. In practice, if we use continuous edge length on a
connected network, we can assume that πe (s, t) ∈ {0, 1} and π(s, t) = 1 for all pairs (s, t). This means
that there is only one shortest-path between each pair of nodes in G.
On way to compute Eq. 2 is therefore to compute all pairwise shortest-paths between the locations
evolved in the transfers using a shortest-path algorithm such as Dijkstra’s algorithm [6]. However,
notice that if F (s, t) = 1 for all (s, t) ∈ V × V then Eq. 2 corresponds to the betweenness centrality
measure [3]. This measure is well-known in network analysis as it allows to identify vital elements of
the network (hubs). It is possible to generalize the algorithm proposed in [3] in order to take account of
transfer values different than 1. The computation of FlowRouting therefore runs in O(nm + n log m).
In practice it involves computing as many shortest-path tree as the size of the minimal vertex cover
of transfers higher than 0 (which is at most n).

2.2

Biological routing

As previously explained, “biological” routing is designed to mimic several known physical phenomena
that can be found in biological organisms such as the slime mould Physarum Polycephalum. As such,
the routing of flow in biological models corresponds to a flow Q that respects classic flow constraints
and minimizes the total energy of the model:
ξσ (Q) =

X l(e)
Q(e)
σ(e)

(3)

e∈E

This biological routing of flow is also commonly introduced as a solution of a linear equation system:
Q(u, v) =

l(u, v)
(p(u) − p(v))
σ(u, v)

(4)

l(u, v)
is the conductance of edge (u, v).
σ(u, v)
This routing is therefore also close to other network analysis measures such as Eigenvector centrality
or PageRank [4]. The potential p(u) of a node u to attract flows depends on u’s neighbours’ potential
w. r. t. the conductance (speed or diameter) of adjacent edges. However, in our case, we are not
interested in the potential value of nodes but only by the flow going through each edge.

Eq. 4 corresponds to Ohm’s law for electrical circuit where

The computation of the flow Q in the biological model corresponds to a solution of a linear
equation system. This computation can be cumbersome due to the number of variables. We adopt
the approximation algorithm described in [12]. It starts with a suboptimal solution where the flows
are routed on a low-stretch spanning tree (distance preserving tree). Then, we randomly select a
“short-cut” edge (a, b) that does not belong to that tree and send a portion of the flow going from
6

a to b in the tree through that short-cut. Those modifications are called “cycle updates”. The
number of cycle updates performed is set so that the distribution of flow is a -approximation of
the solution of the linear equation system. This approach leads to a near-linear time computation
of O(m log2 n log log n log(−1 )). Note however that a solution Q to Eq. 3 can only be found if all
transfers in F have for source a single unique vertex (in order to respect flow constraints). Again,
we need to find as many solutions the size of the minimal vertex cover of non-null transfers (which
is at most n). The running time of the biological routing therefore highly depends on the density of
transfers.

3

Experiment details

We present in this section the choices made for comparing the two transportation network construction
models described above.
Fitness Measures. We introduce here the fitness measures used. We use concepts found previously in the literature [26] (the three dimensions: performance, fault-tolerance and cost). The
differences with previous definitions of performance or fault-tolerance come from the fact that we
consider arbitrary transfers distributions.
Even though Algorithm 1 outputs a real vector of speed/diameter σ, we take as transportation net¯
work N = (V, {e ∈ E : σ(e) > },
Pl) for simplicity sake. We call dN the diameter of N (length of the
longest shortest-path) and F = s,t F (s, t) the total amount of transfers on the network. We define
the following indicators:
1. Performance P corresponds to the total time taken for units to go from their source to their
destination in N .
1 X
P (N, F ) = 1 − ¯
F (s, t)dN (s, t)
(5)
F dN s,t
where dN (s, t) is the distance between s and t in N (i.e. the sum of the length of the edges
along the shortest-path from s to t). Notice we have P (N ) ∈ [0, 1] and we say the network N
has good performance when P (N ) is close to 1. The main difference with previous definitions of
performance is that the amount of transfers is taken into account. Indeed, the measure P corresponds to the mean time taken by travellers to reach there destination while previous definition
(using uniform transfers) correspond to the mean time of travel for each pair of locations.
2. Fault Tolerance F T corresponds to the proportion of transfers still able to reach destination
after the removal of a random edge in N .
X 1
X
1
F T (N, F ) = 1 −
F (s, t)1PN \e (s,t)6=∅
(6)
|E(N )|
F
e∈E(N )

(s,t)∈V ×V

where 1PN \e 6=∅ (s, t) is equal to 1 if there is still a path between s et t in N after the removal
of edge e or 0 otherwise. Using this normalisation, we have F T (N ) ∈ [0, 1] and we say that N
is highly tolerant to fault when F T (N ) is close to 1. Notice that F T is a generalisation of the
classic metric that just focused on whether the network is disconnected or not (a measure used
in [26]). If an area is loosely connected to the network, it may not affect F T much if the amount
of transfers with this area is relatively low.
7

3. Cost C corresponds to the normalized sum of the length of edges in N
P
e∈E(N ) l(e)
C(N ) = P
e∈E(G) l(e)

(7)

Using this normalisation, we have C(N ) ∈ [0, 1] and we say that N is a costly network when
C(N ) is close to 1.
Obviously, a costly network is more likely to have a higher tolerance to fault and performance.
Therefore it is interesting to look at the ratio P/C and F T /C for comparison purpose.
Samples. In order to compare the two algorithms, we first use synthetic data generated randomly.
We sample a set of 150 points in the [0, 1]2 plain and connect the points using a standard Delaunay
triangulation. This random grid corresponds to the possible adjacencies of the future network (the
support graph G). We then select a subset of 8 points that will correspond to the sources and
destinations of transfers. The matrix F is then generated using two different models:
1. Uniform distribution: set F (s, t) = 1 for all (s, t). It is the same as in [26].
P (s)P (t)
where P : V → R is the population of the nodes and
dE (s, t)γ
dE (s, t) is the euclidean distance between s and t. Here we set γ = 1.2. This model is often used
in urban geography to model human mobility [24]. The population P is generated using an Zipf
exponential model i.e. the population exponentially decreases with the rank of the points by
a factor of 1.5 (the ranks of the 8 locations being chosen randomly). This model produces few
important centres of attractions and isolated areas.

2. Gravity model: set F (s, t) =

The way transfers are distributed corresponds to two experimental settings. In addition, we develop
a third and a forth using as locations cities of the French region Pays-de-la-Loire (West of France).
The resulting grid can be seen in Fig. 4 (red nodes represent important cities in the region). We
also analyse the difference between a uniform and a gravity-like distribution of transfers. For the latter, we use as locations weight the actual population of the cities according to the 1999 national census.
Parameters choices. Algorithm 1 has many different parameters. The most influential however
is the parameter α. For the experiments, we take for α values powers of 2 (see the different behaviour
of f in Fig. 1). In [26], the authors choose to modify the total amount of transfers (which here corresponds to F) since their reinforcement function does not include a parameter similar to α. The effect
is however similar. Indeed, the higher α is, the more the route that are less used are given a high
weight. In [26], the more transfers amount there is, the more those routes are likely to be used. The
α value can be used to influence the final cost of the network. Small α values are likely to result in a
tree-like organisation of the transportation network while higher α values are more likely to produce
to a grid-like organisation [15].
Regarding the other parameters we use an update rate γ = 0.5, a slope of reinforcement µ = 1.8
(similar to the one in Fig. 1) and a precision of  = 5.10−4 (i.e. the algorithm will stop when the
greatest difference in σ values is smaller than 5.10−4 ).
Hypothesis on the difference between the two approaches. Previous studies show that the
biological routing is efficient when compared for example to greedy approaches [26]. The efficiency here
8

involves finding a good compromise between performance and fault tolerance. These results where
made using uniformly distributed transfers between locations. Using the same distribution, we expect
shortest-path routing to perform worst than biological routing. The reason is that shortest-paths
explore fewer solutions and the procedure could quickly fall in a local minima. However, we could
expect the results to be different when modifying the distribution of transfers. A skewed distribution
of transfers should favour the shortest-path routing approach since the direct routing of the most
important transfers along the fastest route will have the most impact.

4

Results

In this section, we discuss the results of the various experiments using the indicators of performance
(P ), fault tolerance (F T ) and cost (C). We first look at the statistical results for the synthetic experiments then we discuss some qualitative aspect of the results in the case of the geographical grid.
For clarity purpose, we use SP and BIO to refer to the shortest-path routing and biological routing
respectively. The two types of transfers distribution are referred as U M for the uniformly distributed
transfers and GM for the gravity model.
We generated 200 instances of random grid and applied the transfers distribution models described
above. We shall first stress out the fact that BIO computation is very slow. It requires several minutes
when SP only takes a second.
The distributions of the indicators according to α can be found in Fig. 2. Note that we do not have
to compare each algorithm using the same α value. Therefore, the evolution of the ratio P/C and
F T /C can be found in Fig. 3. For the geographical grid, we report the statistics computed for some
values of α for U M (Table 1) and GM (Table 2). A representation of the computed networks can be
seen in Figures 4 and 5.
Here are the conclusions that can be drawn from these results:
1. BIO seems to achieve better results than SP if we look at the ratio. In the U M
experiments and for α ∈ [1, 4], the ratio P/C and F T /C are both greater for BIO than for
SP with any α values. The same can be said in GM with α < 4. However, the variation of
the indicators is important (height of the boxplots in Fig. 2). It means there are configurations
when SP routing may find a better network. It is actually the case for the geographical grid
with both U M and GM .
2. BIO explores a broader set of results. A trade-off between performance and fault-tolerance
is clearly visible in U M with both BIO and SP . This phenomenon was already observed for BIO
in [26] using different fitness indicators. One important difference between the two procedures
is that the set of networks that can be found using BIO corresponds to a wide range of cost.
This is more limited for SP as the networks found for various value of α may not differ a lot.
3. There is important difference in the results between the two transfers distribution
models. The trade-off between perf6ormance and fault-tolerance is not clearly apparent in
the GM case. We can observe that the behaviour of the ratio P/C and F T /C is similar for
BIO and SP . It can be explained by the fact that the simulated transfers create a single
9

Figure 2: Distribution of the various indicators according to α values (x-axis) for the four experimental
settings (see Legend). Bottom-right plot: similarity between the results of SP and BIO routing
procedures (proportion of edges found in both networks).

10

Table 1: Results for the geographical grid (with a uniform distribution of transfers)
Routing
SP

BIO

α
2
16
64
2
16
64

Perf
.469
.479
.489
.471
.487
.548

FT
.793
.797
.822
.782
.956
.998

Cost
.034
.035
.035
.035
.042
.054

Perf/Cost
13.794
13.686
13.971
13.457
11.595
10.148

FT/Cost
23.324
22.771
23.486
22.343
22.762
18.481

important centre of attraction in the grid (the most “populated” location). In this context,
achieving good performance and fault-tolerance is not hard: we just need to connect this centre
to the periphery. Accordingly, we observe that the networks found with BIO and SP are more
similar in this model (see Fig. 2). Moreover, the value of the ratio P/C and F T /C is higher for
both algorithms. Still, further expansions of the network (using higher α values) are less and
less cost-effective since they connect locations whose transfers between them are exponentially
smaller.
4. The differences in performance or fault tolerance seems to correspond to different
behaviours when looking at the geographical example (Figs. 4 and 5).
In the U M case, networks found using SP have a tree-like structure for most values of α. BIO
finds similar networks using small α value. However, it can also find more costly networks
with higher α value such as a grid-like network (see Fig. 4b). Table 1 shows this trade-off
between P/C and F T /C. Notice however that BIO produces a lot of alternative paths that are
actually parallel routes going between the same locations. This type of behaviour can explain
the important increase of cost for higher α values.
In the GM case, the result are very different. Small α values still correspond to tree-like structure
for both BIO and SP . For higher α values however, SP produces alternative paths. This is
also the case for BIO but again with redundant routes. This apparently strange behaviour from
BIO could be traced back to the “double edges” often found in experimental settings using a
real Physarum polycephalum organism [20]. In our case, it seems that the redundant edges do
not add much in term of fault-tolerance since alternatives (but longer) routes already exist.

5

Conclusion and Related Questions

In this paper we compared two different approaches of transportation network design. We provide a
common analysis framework and an implementation of the algorithms. The methods were compared
based on synthetic random grids using statistical indicators. From a quantitative point-of-view, we
can conclude that the biological inspired approach is overall better than the routing of flows based on
shortest-paths. However, the difference between the two is not always significant. The biologicallyinspired model can be used to explore a wider range of solution. Contrary to our hypothesis, those
observations are still valid when using a more realistic non-uniform model of transfers even though
the difference in terms of performance and fault-tolerance is even smaller than in the uniform case.

11

Figure 3: Evolution of the median value of the ratio Perf/Cost and FT/Cost (middle of the corresponding boxplots in Fig. 2) according α values (points labels).

Table 2: Results for the geographical network (with a gravity model distribution of transfers)
Routing

SP

BIO

α
0
128
256
512
1024
0
128
256
512
1024

Perf
.644
.661
.661
.677
.689
.578
.578
.627
.637
.689

FT
.851
.928
.928
.981
.987
.831
.831
.938
.967
.987

12

Cost
.031
.034
.034
.04
.053
.033
.033
.037
.045
.053

Perf/Cost
20.799
19.369
19.161
16.734
12.968
17.343
17.343
16.743
14.15
10.759

FT/Cost
27.483
27.201
26.913
24.242
18.559
24.914
24.914
25.05
21.469
15.398

(a) Bio routing – α = 4

(b) Bio routing – α = 64

(c) SP routing – α = 4

(d) SP routing – α = 64

Figure 4: Comparison of the result on the geographical example with uniform transfers. Red nodes
correspond to major cities in the regions (préfecture and sous-préfecture).

Our experiments still have important limitations since there are numerous dimensions still unexplored. One could access, for example, the influence of the size of the grid. First results tend to reveal
a similar behaviour but the discrepancy between the two methods may be amplified. The influence
of others parameters such as the decay rate γ or the reinforcement curve gradient µ should also be
investigated but we expect they will have less of an impact.
Our study is also limited by the fact that our evaluation relies on objectives functions related to performance, fault-tolerance and cost. However, geographers, biologists or urban planners might want
to know whether or not simulated networks are close to real-world networks. In this context, the
objective functions are useful but it is not possible to infer the closeness between two networks based
on the proximity in these functions values.
What we learn from this study is that biologically-inspired routing may be better suited for the
researcher since it allows an exploration of a broader set of solutions. However, taking into account
13

(a) Bio routing – α = 0

(b) Bio routing – α = 512

(c) SP routing – α = 0

(d) SP routing – α = 512

Figure 5: Comparison of the result on the geographical example with transfers following a gravity
model. Red nodes correspond to major cities in the regions (préfecture and sous-préfecture). Node
size is proportional to the population of the cities.

smaller and smaller flows (with increasing α value) leads to networks with high cost but without much
additional performance or fault-tolerance. One of our experiment reveals for example that biological
routing may produce parallel short routes that are not efficient.

References
[1] Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows. Elsevier, 2014.
[2] David Auber, Romain Bourqui, Maylis Delest, Antoine Lambert, Patrick Mary, Guy Melançon,
Bruno Pinaud, Benjamin Renoust, and Jason Vallet. TULIP 4. Research report, LaBRI - Laboratoire Bordelais de Recherche en Informatique, September 2016.
14

[3] Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology,
25(2):163–177, 2001.
[4] Fan Chung and Wenbo Zhao. Pagerank and random walks on graphs. In Fete of combinatorics
and computer science, pages 43–62. Springer, 2010.
[5] Erik D Demaine and Morteza Zadimoghaddam. Minimizing the diameter of a network using
shortcut edges. In Algorithm Theory-SWAT 2010, pages 420–431. Springer, 2010.
[6] Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik,
1(1):269–271, 1959.
[7] Audrey Dussutour, Vincent Fourcassie, Dirk Helbing, and Jean-Louis Deneubourg. Optimal
traffic organization in ants under crowded conditions. Nature, 428(6978):70, 2004.
[8] Terry L. Friesz. Transportation network equilibrium, design and aggregation: Key developments
and research opportunities. Transportation Research Part A: General, 19(5):413 – 427, 1985.
Special Issue Transportation Research: The State of the Art and Research Opportunities.
[9] Cai Gao, Chao Yan, Daijun Wei, Yong Hu, Sankaran Mahadevan, and Yong Deng. A biologically
inspired model for transshipment problem. arXiv preprint arXiv:1401.2181, 2014.
[10] Andrew V Goldberg, Jeffrey D Oldham, Serge Plotkin, and Cliff Stein. An implementation of a
combinatorial approximation algorithm for minimum-cost multicommodity flow. In International
Conference on Integer Programming and Combinatorial Optimization, pages 338–352. Springer,
1998.
[11] Kentaro Ito, Anders Johansson, Toshiyuki Nakagaki, and Atsushi Tero. Convergence properties
for the physarum solver. arXiv preprint arXiv:1101.5249, 2011.
[12] Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. In Proceedings of the forty-fifth
annual ACM symposium on Theory of computing, pages 911–920. ACM, 2013.
[13] Antoine Lambert, Romain Bourqui, and David Auber. Winding roads: Routing edges into bundles. In Computer Graphics Forum, volume 29, pages 853–862. Wiley Online Library, 2010.
[14] David Levinson and Bhanu Yerra. Self-organization of surface transportation networks. Transportation Science, 40(2):179–188, 2006.
[15] Rémi Louf, Pablo Jensen, and Marc Barthelemy. Emergence of hierarchy in cost-driven growth
of spatial networks. Proceedings of the National Academy of Sciences, 110(22):8824–8829, 2013.
[16] Qi Ma, Anders Johansson, Atsushi Tero, Toshiyuki Nakagaki, and David JT Sumpter. Currentreinforced random walks for constructing transport networks. Journal of the Royal Society Interface, 10(80):20120864, 2013.
[17] Luca Masi and Massimiliano Vasile. A multidirectional physarum solver for the automated design
of space trajectories. In Evolutionary Computation (CEC), 2014 IEEE Congress on, pages 2992–
2999. IEEE, 2014.
15

[18] Christophe Mimeur, François Queyroi, Arnaud Banos, and Thomas Thévenin. Revisiting the
structuring effect of transportation infrastructure: an empirical approach with the French Railway
Network from 1860 to 1910. Historical Methods: A Journal of Quantitative and Interdisciplinary
History, 2017.
[19] Tomoyuki Miyaji and Isamu Ohnishi. Physarum can solve the shortest path problem on riemannian surface mathematically rigourously. International Journal of Pure and Applied Mathematics,
47(3):353–369, 2008.
[20] Tomoyuki Miyaji, Isamu Ohnishi, Atsushi Tero, and Toshiyuki Nakagaki. Failure to the shortest path decision of an adaptive transport network with double edges in plasmodium system.
International Journal of Dynamical Systems and Differential Equations, 1(3):210–219, 2008.
[21] Saket Navlakha, Alison L Barth, and Ziv Bar-Joseph. Decreasing-rate pruning optimizes
the construction of efficient and robust distributed networks. PLoS computational biology,
11(7):e1004347, 2015.
[22] N Parotisidis, Evaggelia Pitoura, and Panayiotis Tsaparas. Selecting shortcuts for a smaller
world. In SIAM International Conference on Data Mining (SDM), 2015.
[23] Juste Raimbault, Arnaud Banos, and René Doursat. A hybrid network/grid model of urban
morphogenesis and optimization. CoRR, abs/1612.08552, 2016.
[24] Jean-Paul Rodrigue, Claude Comtois, and Brian Slack. The geography of transport systems.
Routledge, 2009.
[25] Atsushi Tero, Ryo Kobayashi, and Toshiyuki Nakagaki. A mathematical model for adaptive
transport network in path finding by true slime mold. Journal of theoretical biology, 244(4):553–
564, 2007.
[26] Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P Bebber, Mark D Fricker, Kenji
Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki. Rules for biologically inspired adaptive network
design. Science, 327(5964):439–442, 2010.
[27] David Vogel and Audrey Dussutour. Direct transfer of learned behaviour via cell fusion in nonneural organisms. In Proc. R. Soc. B, volume 283, page 20162382. The Royal Society, 2016.
[28] Bhanu M Yerra and David M Levinson. The emergence of hierarchy in transportation networks.
The Annals of Regional Science, 39(3):541–553, 2005.

16

