ScienceDirect
Available online at www.sciencedirect.com
Procedia Computer Science 109C (2017) 648–655
1877-0509 © 2017 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
10.1016/j.procs.2017.05.371
10.1016/j.procs.2017.05.371
1877-0509 © 2017 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Available online at www.sciencedirect.com
Procedia Computer Science 00 (2016) 000–000
www.elsevier.com/locate/procedia
The 8th International Conference on Ambient Systems, Networks and Technologies
(ANT 2017)
The structure of user equilibria: Dynamic coevolutionary
simulations vs. cyclically expanded networks
Theresa Thuniga,∗, Kai Nagela
aTechnische Universit¨at Berlin, Transport Systems Planning and Transport Telematics, Salzufer 17-19, 10587 Berlin, Germany
Abstract
A variety of approaches exist that model traffic time-dependently. While all approaches have their advantages and disadvantages
but have to find a balance between modeling traffic as realistic as possible and being still manageable in combinational terms. While
transport simulations are efficient in evaluating user equilibria in large scale scenarios, their potential to be used for optimization
is limited. On the other hand, analytical formulations like models based on cyclically time-expanded networks can be used to
optimize traffic flow, but are not suitable for large scale scenarios. By optimizing the network structure in a mathematical model
and evaluating its effect in a more realistic transport simulation, two models can benefit from each other. Detailed knowledge
about model properties and differences in traffic flow behavior help to understand results and potential difficulties of such a model
combination. In this paper, properties of two such models are compared regarding traffic flow modeling. It is shown that the set of
user equilibria in both models and, therefore, the resulting route distributions can be structurally different.
c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Keywords: transport modeling, transport simulation, cyclically time expanded networks, user behavior, user equilibria, system optimum
1. Introduction
In times were congestion levels are growing in many urban areas, there is a need to improve and refine transporta-
tion networks. Traffic models provide assistance with predicting traffic patterns and designing and evaluating traffic
policies. A variety of modeling approaches exist. All of them have to make compromises between capturing the
reality as good as possible and keeping the model complexity at a manageable level. Because of their simplicity, static
flow models are widely used to optimize traffic management schemes like tolls, traffic signal plans, or other network
adaptions. These models’ theory is well established, e.g. in terms of the effect of selfish users on the system welfare.1
Despite their time independence, static flow models can be used to model traffic of specific, fixed points in time where
traffic flow can be assumed to be constant for a while, e.g. during rush hours.
In reality, however, traffic is not time-independent and travel times and demand change over time. There are
approaches to translate static flow models into more realistic ones, capture time dependency but keep some of the
∗Corresponding author. Tel.: +49-30-31478783 ; fax: +49-30-31426269.
1877-0509 c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Available online at www.sciencedirect.com
Procedia Computer Science 00 (2016) 000–000
www.elsevier.com/locate/procedia
The 8th International Conference on Ambient Systems, Networks and Technologies
(ANT 2017)
The structure of user equilibria: Dynamic coevolutionary
simulations vs. cyclically expanded networks
Theresa Thuniga,∗, Kai Nagela
aTechnische Universit¨at Berlin, Transport Systems Planning and Transport Telematics, Salzufer 17-19, 10587 Berlin, Germany
Abstract
A variety of approaches exist that model traffic time-dependently. While all approaches have their advantages and disadvantages
but have to find a balance between modeling traffic as realistic as possible and being still manageable in combinational terms. While
transport simulations are efficient in evaluating user equilibria in large scale scenarios, their potential to be used for optimization
is limited. On the other hand, analytical formulations like models based on cyclically time-expanded networks can be used to
optimize traffic flow, but are not suitable for large scale scenarios. By optimizing the network structure in a mathematical model
and evaluating its effect in a more realistic transport simulation, two models can benefit from each other. Detailed knowledge
about model properties and differences in traffic flow behavior help to understand results and potential difficulties of such a model
combination. In this paper, properties of two such models are compared regarding traffic flow modeling. It is shown that the set of
user equilibria in both models and, therefore, the resulting route distributions can be structurally di
ff
erent.
c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Keywords: transport modeling, transport simulation, cyclically time expanded networks, user behavior, user equilibria, system optimum
1. Introduction
In times were congestion levels are growing in many urban areas, there is a need to improve and refine transporta-
tion networks. Traffic models provide assistance with predicting traffic patterns and designing and evaluating traffic
policies. A variety of modeling approaches exist. All of them have to make compromises between capturing the
reality as good as possible and keeping the model complexity at a manageable level. Because of their simplicity, static
flow models are widely used to optimize traffic management schemes like tolls, traffic signal plans, or other network
adaptions. These models’ theory is well established, e.g. in terms of the effect of selfish users on the system welfare.1
Despite their time independence, static flow models can be used to model traffic of specific, fixed points in time where
traffic flow can be assumed to be constant for a while, e.g. during rush hours.
In reality, however, traffic is not time-independent and travel times and demand change over time. There are
approaches to translate static flow models into more realistic ones, capture time dependency but keep some of the
∗Corresponding author. Tel.: +49-30-31478783 ; fax: +49-30-31426269.
1877-0509 c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
2Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000
properties to benefit from its simplicity. One idea is to expand the network over time by creating copies of every node
and link per time step2(see section 2.1 for a detailed explanation of time-expansion). With this, flow travels over time
in a static network. Time-expansion only works for constant, i.e. flow-independent link travel times. Otherwise, the
properties of links in the time-expanded network would depend on route decisions of travelers. Constant link travel
times seem to give realistic results in urban areas, where links are short, speed limits exist, and platoons of vehicles
drive with a similar speed as single vehicles. Congestion occurs while waiting at signals or crossings and is modeled
by waiting links at nodes. Route travel times then arise as the sum of constant link travel times and waiting times,
which renders them non-constant again.3Hence, time-expanded models can capture dynamic flows with constant link
travel times in a static network and at least some results on static flows are transferable.4A major disadvantage of
time expansion is that the size of the network increases immensely compared to the size of the original network. Thus,
applying optimization algorithms from static flow theory directly to time-expanded networks is no suitable approach
in general. Still, it is possible to construct other algorithms using properties of time-expanded networks.4
An approach to handle the size of time-expanded networks is to expand the network only for a fixed, short time
interval and cyclically combine the interval boundaries. This results in a manageable network size, but limited time
dependency. Like in static flow models only stationary demand patterns are representable. At least, demand repeats
in each cycle and does not have to be constant all the time.
In contrast to time-expanded networks where link travel times have to be constant, there are also approaches for
flows over time with flow-dependent transit times. These lead to more realistic results, but also to mathematical
difficulties.5Due to the lack of well-defined analytical models for this kind of flows, few results are known for them.
Another approach omits the analytical part and instead uses simulation tools. Transport simulation may capture
a lot of the complex, realistic behavior of traffic flows like time-dependent demand and travel times, spill back to
upstream parts of the network, and a more detailed user behavior that includes not only route, but also time and mode
choice. This is done by an iterative approach that simulates agents traveling through the network and performing their
daily activities. The daily plans of agents are then evaluated and some agents are allowed to re-plan their day until the
iterations reach a stable state, i.e. no agent wants to change their plan anymore. Hence, transport simulation tools find
user equilibria for complex systems where not all relations are known in terms of closed mathematical formulations.
They result as fixed points of the iterative routing and assignment process.6,7,8 On the other hand, simulation tools
miss the optimization potential because of the complex system they capture.
Knowing the properties of the different models, one can try to find a combination of the different approaches which
benefits from the advantages of the models while overcoming their specific weaknesses: While transport simulations
are efficient in evaluating user equilibria in large scale scenarios, their potential to be used for optimization is limited.
On the other hand, analytical formulations like models based on cyclically time-expanded networks can be used to
optimize traffic flow, but are not suitable for large scale and highly time-dependent scenarios. By optimizing the
network structure in the mathematical model and evaluating its effect in the more realistic transport simulation, both
models can benefit from each other. Detailed knowledge about model properties and differences in traffic flow behavior
helps to understand results and potential difficulties of such a model combination.
This paper compares two of the discussed approaches to model traffic in a time-dependent way: A cyclically
time-expanded network model and a dynamic coevolutionary transport simulation. For the time-expanded model an
approach by K¨
ohler and Strehler at BTU Cottbus, which was developed for fixed-time traffic signal optimization, is
considered.3On the other side, the transport simulation MATSim is used.9Both models have already been coupled
to optimize fixed-time traffic signal plans in a real world scenario. For this, the scenario is provided by the transport
simulation and converted into a cyclically time-expanded network. The static model then approximates optimal fixed-
time signal plans for all signalized intersections by solving a mixed integer program (MIP) with the high performance
solver CPLEX. These optimized signal plans are returned to the transport simulation to evaluate travel time effects in
a more realistic model. Initial results have been presented by Grether10.
The structure of this paper is the following: The two models are introduced in the next section and compared in
section 2.3 regarding their model properties. Resulting flow patterns, i.e. user behavior of both models are compared
in section 3. Conclusions are drawn in Section 4.
Theresa Thunig et al. / Procedia Computer Science 109C (2017) 648–655 649
Available online at www.sciencedirect.com
Procedia Computer Science 00 (2016) 000–000
www.elsevier.com/locate/procedia
The 8th International Conference on Ambient Systems, Networks and Technologies
(ANT 2017)
The structure of user equilibria: Dynamic coevolutionary
simulations vs. cyclically expanded networks
Theresa Thuniga,∗, Kai Nagela
aTechnische Universit¨at Berlin, Transport Systems Planning and Transport Telematics, Salzufer 17-19, 10587 Berlin, Germany
Abstract
A variety of approaches exist that model traffic time-dependently. While all approaches have their advantages and disadvantages
but have to find a balance between modeling traffic as realistic as possible and being still manageable in combinational terms. While
transport simulations are efficient in evaluating user equilibria in large scale scenarios, their potential to be used for optimization
is limited. On the other hand, analytical formulations like models based on cyclically time-expanded networks can be used to
optimize traffic flow, but are not suitable for large scale scenarios. By optimizing the network structure in a mathematical model
and evaluating its effect in a more realistic transport simulation, two models can benefit from each other. Detailed knowledge
about model properties and differences in traffic flow behavior help to understand results and potential difficulties of such a model
combination. In this paper, properties of two such models are compared regarding traffic flow modeling. It is shown that the set of
user equilibria in both models and, therefore, the resulting route distributions can be structurally different.
c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Keywords: transport modeling, transport simulation, cyclically time expanded networks, user behavior, user equilibria, system optimum
1. Introduction
In times were congestion levels are growing in many urban areas, there is a need to improve and refine transporta-
tion networks. Traffic models provide assistance with predicting traffic patterns and designing and evaluating traffic
policies. A variety of modeling approaches exist. All of them have to make compromises between capturing the
reality as good as possible and keeping the model complexity at a manageable level. Because of their simplicity, static
flow models are widely used to optimize traffic management schemes like tolls, traffic signal plans, or other network
adaptions. These models’ theory is well established, e.g. in terms of the effect of selfish users on the system welfare.1
Despite their time independence, static flow models can be used to model traffic of specific, fixed points in time where
traffic flow can be assumed to be constant for a while, e.g. during rush hours.
In reality, however, traffic is not time-independent and travel times and demand change over time. There are
approaches to translate static flow models into more realistic ones, capture time dependency but keep some of the
∗Corresponding author. Tel.: +49-30-31478783 ; fax: +49-30-31426269.
1877-0509 c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Available online at www.sciencedirect.com
Procedia Computer Science 00 (2016) 000–000
www.elsevier.com/locate/procedia
The 8th International Conference on Ambient Systems, Networks and Technologies
(ANT 2017)
The structure of user equilibria: Dynamic coevolutionary
simulations vs. cyclically expanded networks
Theresa Thuniga,∗, Kai Nagela
aTechnische Universit¨at Berlin, Transport Systems Planning and Transport Telematics, Salzufer 17-19, 10587 Berlin, Germany
Abstract
A variety of approaches exist that model traffic time-dependently. While all approaches have their advantages and disadvantages
but have to find a balance between modeling traffic as realistic as possible and being still manageable in combinational terms. While
transport simulations are efficient in evaluating user equilibria in large scale scenarios, their potential to be used for optimization
is limited. On the other hand, analytical formulations like models based on cyclically time-expanded networks can be used to
optimize traffic flow, but are not suitable for large scale scenarios. By optimizing the network structure in a mathematical model
and evaluating its effect in a more realistic transport simulation, two models can benefit from each other. Detailed knowledge
about model properties and differences in traffic flow behavior help to understand results and potential difficulties of such a model
combination. In this paper, properties of two such models are compared regarding traffic flow modeling. It is shown that the set of
user equilibria in both models and, therefore, the resulting route distributions can be structurally different.
c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Keywords: transport modeling, transport simulation, cyclically time expanded networks, user behavior, user equilibria, system optimum
1. Introduction
In times were congestion levels are growing in many urban areas, there is a need to improve and refine transporta-
tion networks. Traffic models provide assistance with predicting traffic patterns and designing and evaluating traffic
policies. A variety of modeling approaches exist. All of them have to make compromises between capturing the
reality as good as possible and keeping the model complexity at a manageable level. Because of their simplicity, static
flow models are widely used to optimize traffic management schemes like tolls, traffic signal plans, or other network
adaptions. These models’ theory is well established, e.g. in terms of the effect of selfish users on the system welfare.1
Despite their time independence, static flow models can be used to model traffic of specific, fixed points in time where
traffic flow can be assumed to be constant for a while, e.g. during rush hours.
In reality, however, traffic is not time-independent and travel times and demand change over time. There are
approaches to translate static flow models into more realistic ones, capture time dependency but keep some of the
∗Corresponding author. Tel.: +49-30-31478783 ; fax: +49-30-31426269.
1877-0509 c
2016 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
2Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000
properties to benefit from its simplicity. One idea is to expand the network over time by creating copies of every node
and link per time step2(see section 2.1 for a detailed explanation of time-expansion). With this, flow travels over time
in a static network. Time-expansion only works for constant, i.e. flow-independent link travel times. Otherwise, the
properties of links in the time-expanded network would depend on route decisions of travelers. Constant link travel
times seem to give realistic results in urban areas, where links are short, speed limits exist, and platoons of vehicles
drive with a similar speed as single vehicles. Congestion occurs while waiting at signals or crossings and is modeled
by waiting links at nodes. Route travel times then arise as the sum of constant link travel times and waiting times,
which renders them non-constant again.3Hence, time-expanded models can capture dynamic flows with constant link
travel times in a static network and at least some results on static flows are transferable.4A major disadvantage of
time expansion is that the size of the network increases immensely compared to the size of the original network. Thus,
applying optimization algorithms from static flow theory directly to time-expanded networks is no suitable approach
in general. Still, it is possible to construct other algorithms using properties of time-expanded networks.4
An approach to handle the size of time-expanded networks is to expand the network only for a fixed, short time
interval and cyclically combine the interval boundaries. This results in a manageable network size, but limited time
dependency. Like in static flow models only stationary demand patterns are representable. At least, demand repeats
in each cycle and does not have to be constant all the time.
In contrast to time-expanded networks where link travel times have to be constant, there are also approaches for
flows over time with flow-dependent transit times. These lead to more realistic results, but also to mathematical
difficulties.5Due to the lack of well-defined analytical models for this kind of flows, few results are known for them.
Another approach omits the analytical part and instead uses simulation tools. Transport simulation may capture
a lot of the complex, realistic behavior of traffic flows like time-dependent demand and travel times, spill back to
upstream parts of the network, and a more detailed user behavior that includes not only route, but also time and mode
choice. This is done by an iterative approach that simulates agents traveling through the network and performing their
daily activities. The daily plans of agents are then evaluated and some agents are allowed to re-plan their day until the
iterations reach a stable state, i.e. no agent wants to change their plan anymore. Hence, transport simulation tools find
user equilibria for complex systems where not all relations are known in terms of closed mathematical formulations.
They result as fixed points of the iterative routing and assignment process.6,7,8 On the other hand, simulation tools
miss the optimization potential because of the complex system they capture.
Knowing the properties of the different models, one can try to find a combination of the different approaches which
benefits from the advantages of the models while overcoming their specific weaknesses: While transport simulations
are efficient in evaluating user equilibria in large scale scenarios, their potential to be used for optimization is limited.
On the other hand, analytical formulations like models based on cyclically time-expanded networks can be used to
optimize traffic flow, but are not suitable for large scale and highly time-dependent scenarios. By optimizing the
network structure in the mathematical model and evaluating its effect in the more realistic transport simulation, both
models can benefit from each other. Detailed knowledge about model properties and differences in traffic flow behavior
helps to understand results and potential difficulties of such a model combination.
This paper compares two of the discussed approaches to model traffic in a time-dependent way: A cyclically
time-expanded network model and a dynamic coevolutionary transport simulation. For the time-expanded model an
approach by K¨
ohler and Strehler at BTU Cottbus, which was developed for fixed-time traffic signal optimization, is
considered.3On the other side, the transport simulation MATSim is used.9Both models have already been coupled
to optimize fixed-time traffic signal plans in a real world scenario. For this, the scenario is provided by the transport
simulation and converted into a cyclically time-expanded network. The static model then approximates optimal fixed-
time signal plans for all signalized intersections by solving a mixed integer program (MIP) with the high performance
solver CPLEX. These optimized signal plans are returned to the transport simulation to evaluate travel time effects in
a more realistic model. Initial results have been presented by Grether10.
The structure of this paper is the following: The two models are introduced in the next section and compared in
section 2.3 regarding their model properties. Resulting flow patterns, i.e. user behavior of both models are compared
in section 3. Conclusions are drawn in Section 4.
650 Theresa Thunig et al. / Procedia Computer Science 109C (2017) 648–655
Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000 3
Fig. 1. Cyclically time-expanded network with waiting links: Expand the network over time (top right); cyclically combine it (bottom left); add
waiting links (bottom right).3
2. Model properties
Both approaches studied in this paper – the cyclically time-expanded network model by K¨
ohler and Strehler and
the transport simulation MATSim – model traffic in a time-dependent way. In this section, the models are introduced
and relevant model properties are compared in detail.
2.1. The cyclically time-expanded network model
The model of K¨
ohler and Strehler was developed to optimize traffic signal coordination and traffic assignment
simultaneously in an urban road network.3It is based on a time-expanded network, which uses the periodicity of
traffic signals to limit the time horizon and, therefore, restrict computation time. In the following, it is called the
cyclically time-expanded network model.
Time-expanded networks can model traffic in a time-dependent manner. Figure 1 illustrates time-expansion: Con-
sider a static network with constant link travel times like in the upper left part of figure 1 with four nodes and four
links. Choose a time step size (e.g. one second, as in figure 1) and create a (vertically) copy of each node for each time
step. For every link in the static network, connect copies of the origin and destination node in the expanded network
according to the constant travel time in the static network. This step can be seen in the upper right part of figure 1.
When flow travels on one link in a time-expanded network, it automatically reaches the next node by the copy of the
correct time step. In such a network, link flow values may differ for different time steps. Also demand values do not
have to be stationary anymore in contrast to static networks. But the network size increases significantly. Therefore,
the considered model limits the time horizon by taking advantage of the periodicity of traffic signals: The network is
only expanded for a time interval of the size of the signal cycle time. Links are then added according to travel times
modulo the number of time steps. This step is visualized in the lower left part of figure 1. A disadvantage of this
cyclical concatenation is that some time dependency gets lost: Demand and link flow pattern have to be cyclically
repeated. As a last step, waiting links, which allow flow particles to wait in front of intersections, are added to the
network. This may be necessary because of link capacities that restrict inflow values per time step. Waiting links in
the cyclically time-expanded network are illustrated in the lower right part of figure 1.
Although link travel times are constant, resulting route travel times of travelers behave not constant for increasing
demand values. This is because more and more waiting arcs have to be used – i.e. waiting times increase – with
increasing demand. (See K¨
ohler and Strehler3for a detailed study on travel times in this model.)
4Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000
The multi-commodity traffic assignment problem in the cyclically time-expanded network is analytically formu-
lated together with signal coordination constraints in a corresponding mixed integer program (MIP). The program has
a linear objective function that minimizes total travel time and, therefore, results in a system optimum (SO). To solve
the mixed integer program, the high performance solver CPLEX is used. CPLEX iteratively calculates primal and
dual bounds to search for a good solution of the problem and, on the other hand, to prove its optimality by closing the
gap between primal and dual solutions. In some scenarios with many conflicting streams and high demand values, the
gap can not be closed at all by CPLEX.3
2.2. The dynamic coevolutionary transport simulation
In contrast to static models and models that are based on time-expanded networks, a dynamic transport simulation
is not based on a closed mathematical formulation that minimizes an objective, but simulates single agents traveling
through a network and selfishly minimizing their travel time. It is, therefore, able to simulate traffic demand and travel
times that changes over time.
The multi-agent transport simulation MATSim9considered in this paper belongs to the class of dynamic coevo-
lutionary transport simulations. It is based on a network with free-speed travel times and link lengths, i.e. constant
free-flow travel times for links like in the time-expanded network. Outflow rates are restricted by link flow capacities.
Additionally, links have storage capacities that restrict the number of vehicles that can queue on a link. MATSim
links are modeled as queues: Vehicles that enter a link queue up and are finally allowed to exit the link when they
have reached the front of the queue, their free flow link travel time is reached, and flow capacity of the current link
and storage capacity of the next link are not exceeded. Agents, i.e. synthetic travelers, depart and arrive on arbitrary
links at arbitrary times which is modeled by daily plans. Plans contain a schedule of activities, including times and
locations, along with the travel modes. Routes are also assigned to plans.
MATSim iterates between two major components: At first, the demand is simulated on the physical network
(called mobsim for mobility simulation in figure 2), i.e. every agent executes its selected plan. Travel times and,
therefore, activity durations of the executed activity travel pattern differ from times and durations in the plan because
of congestion. The second major component of the iterative process is the mental simulation: Agents evaluate their
decisions (called scoring in figure 2) and eventually replan them (called replanning in figure 2). Plans are evaluated
based on their performance, which is quantified by a score. Scores sum up as utilities for all activity participations
and times spent in traffic. Agents are allowed to select a plan for the next iteration. A certain percentage of agents
is chosen to generate a new plan by modifying an existing plan. Possible modification strategies are e.g. route, time,
or mode choice. The remaining agents select one of their already existing plans through probabilistic selection by a
multinomial logit model, where the selection probability of a plan is related to its score.
Over the iterations, agents intend to maximize their score. The iterative process is repeated until agent scores do not
vary, i.e. agents do not want to change their strategy, anymore. If scores converge, the process leads to a (stochastic)
user equilibrium (UE), i.e. no user may improve his score by unilaterally changing his strategy. MATSim’s learning
dynamics, i.e. finding user equilibria as fixed points of the iterative routing and assignment process, are very similar
to the approach presented by Cominetti. He proved that such learning dynamics converge almost surely towards a
stationary state, which can be characterized as a user equilibrium.8
To be able to compare both models, this paper confines on situations where maximizing individual scores is similar
to minimizing individual travel times in MATSim. Furthermore, stochasticity that comes from the probability of plan
selection is significantly reduced.
2.3. Comparing both models
The models described in the two previous subsections – the cyclically time-expanded network model and the
dynamic coevolutionary transport simulation – both aim to predict traffic flow with more or less aspects of time
dependence, link travel times that are flow-independent and the possibility of waiting in front of intersections. Besides
these aspects, there are many differences in both models (see Table 1). While comparing solution structures of both
models and before coupling them to construct and evaluate traffic policies for real-world scenarios, it is important to
analyze the properties and behavior of both models, along with underlying assumptions and their capabilities. This
aims at better understanding coherences and consequences of coupling both models.
Theresa Thunig et al. / Procedia Computer Science 109C (2017) 648–655 651
Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000 3
Fig. 1. Cyclically time-expanded network with waiting links: Expand the network over time (top right); cyclically combine it (bottom left); add
waiting links (bottom right).3
2. Model properties
Both approaches studied in this paper – the cyclically time-expanded network model by K¨
ohler and Strehler and
the transport simulation MATSim – model traffic in a time-dependent way. In this section, the models are introduced
and relevant model properties are compared in detail.
2.1. The cyclically time-expanded network model
The model of K¨
ohler and Strehler was developed to optimize traffic signal coordination and traffic assignment
simultaneously in an urban road network.3It is based on a time-expanded network, which uses the periodicity of
traffic signals to limit the time horizon and, therefore, restrict computation time. In the following, it is called the
cyclically time-expanded network model.
Time-expanded networks can model traffic in a time-dependent manner. Figure 1 illustrates time-expansion: Con-
sider a static network with constant link travel times like in the upper left part of figure 1 with four nodes and four
links. Choose a time step size (e.g. one second, as in figure 1) and create a (vertically) copy of each node for each time
step. For every link in the static network, connect copies of the origin and destination node in the expanded network
according to the constant travel time in the static network. This step can be seen in the upper right part of figure 1.
When flow travels on one link in a time-expanded network, it automatically reaches the next node by the copy of the
correct time step. In such a network, link flow values may differ for different time steps. Also demand values do not
have to be stationary anymore in contrast to static networks. But the network size increases significantly. Therefore,
the considered model limits the time horizon by taking advantage of the periodicity of traffic signals: The network is
only expanded for a time interval of the size of the signal cycle time. Links are then added according to travel times
modulo the number of time steps. This step is visualized in the lower left part of figure 1. A disadvantage of this
cyclical concatenation is that some time dependency gets lost: Demand and link flow pattern have to be cyclically
repeated. As a last step, waiting links, which allow flow particles to wait in front of intersections, are added to the
network. This may be necessary because of link capacities that restrict inflow values per time step. Waiting links in
the cyclically time-expanded network are illustrated in the lower right part of figure 1.
Although link travel times are constant, resulting route travel times of travelers behave not constant for increasing
demand values. This is because more and more waiting arcs have to be used – i.e. waiting times increase – with
increasing demand. (See K¨
ohler and Strehler3for a detailed study on travel times in this model.)
4Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000
The multi-commodity traffic assignment problem in the cyclically time-expanded network is analytically formu-
lated together with signal coordination constraints in a corresponding mixed integer program (MIP). The program has
a linear objective function that minimizes total travel time and, therefore, results in a system optimum (SO). To solve
the mixed integer program, the high performance solver CPLEX is used. CPLEX iteratively calculates primal and
dual bounds to search for a good solution of the problem and, on the other hand, to prove its optimality by closing the
gap between primal and dual solutions. In some scenarios with many conflicting streams and high demand values, the
gap can not be closed at all by CPLEX.3
2.2. The dynamic coevolutionary transport simulation
In contrast to static models and models that are based on time-expanded networks, a dynamic transport simulation
is not based on a closed mathematical formulation that minimizes an objective, but simulates single agents traveling
through a network and selfishly minimizing their travel time. It is, therefore, able to simulate traffic demand and travel
times that changes over time.
The multi-agent transport simulation MATSim9considered in this paper belongs to the class of dynamic coevo-
lutionary transport simulations. It is based on a network with free-speed travel times and link lengths, i.e. constant
free-flow travel times for links like in the time-expanded network. Outflow rates are restricted by link flow capacities.
Additionally, links have storage capacities that restrict the number of vehicles that can queue on a link. MATSim
links are modeled as queues: Vehicles that enter a link queue up and are finally allowed to exit the link when they
have reached the front of the queue, their free flow link travel time is reached, and flow capacity of the current link
and storage capacity of the next link are not exceeded. Agents, i.e. synthetic travelers, depart and arrive on arbitrary
links at arbitrary times which is modeled by daily plans. Plans contain a schedule of activities, including times and
locations, along with the travel modes. Routes are also assigned to plans.
MATSim iterates between two major components: At first, the demand is simulated on the physical network
(called mobsim for mobility simulation in figure 2), i.e. every agent executes its selected plan. Travel times and,
therefore, activity durations of the executed activity travel pattern differ from times and durations in the plan because
of congestion. The second major component of the iterative process is the mental simulation: Agents evaluate their
decisions (called scoring in figure 2) and eventually replan them (called replanning in figure 2). Plans are evaluated
based on their performance, which is quantified by a score. Scores sum up as utilities for all activity participations
and times spent in traffic. Agents are allowed to select a plan for the next iteration. A certain percentage of agents
is chosen to generate a new plan by modifying an existing plan. Possible modification strategies are e.g. route, time,
or mode choice. The remaining agents select one of their already existing plans through probabilistic selection by a
multinomial logit model, where the selection probability of a plan is related to its score.
Over the iterations, agents intend to maximize their score. The iterative process is repeated until agent scores do not
vary, i.e. agents do not want to change their strategy, anymore. If scores converge, the process leads to a (stochastic)
user equilibrium (UE), i.e. no user may improve his score by unilaterally changing his strategy. MATSim’s learning
dynamics, i.e. finding user equilibria as fixed points of the iterative routing and assignment process, are very similar
to the approach presented by Cominetti. He proved that such learning dynamics converge almost surely towards a
stationary state, which can be characterized as a user equilibrium.8
To be able to compare both models, this paper confines on situations where maximizing individual scores is similar
to minimizing individual travel times in MATSim. Furthermore, stochasticity that comes from the probability of plan
selection is significantly reduced.
2.3. Comparing both models
The models described in the two previous subsections – the cyclically time-expanded network model and the
dynamic coevolutionary transport simulation – both aim to predict traffic flow with more or less aspects of time
dependence, link travel times that are flow-independent and the possibility of waiting in front of intersections. Besides
these aspects, there are many differences in both models (see Table 1). While comparing solution structures of both
models and before coupling them to construct and evaluate traffic policies for real-world scenarios, it is important to
analyze the properties and behavior of both models, along with underlying assumptions and their capabilities. This
aims at better understanding coherences and consequences of coupling both models.
652 Theresa Thunig et al. / Procedia Computer Science 109C (2017) 648–655
Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000 5
Fig. 2. The iterative transport simulation MATSim.
The most important difference is related to the way of capturing time dependency: In the cyclically time-expanded
network, demand has to be the same for every cycle. In contrast to static flow models, at least variations in demand
can be modeled, which cause variations in waiting times because of congestion and, therefore, variations in travel
times. These variations are the same every cycle. In the dynamic coevolutionary transport simulation, demand and
therefore travel times may vary arbitrarily over the day.
Although link travel times in both models are constant and flow dependency arises by link capacities that cause
waiting in front of intersections, one can observe a small, but important difference here: Because of the cyclic struc-
ture, waiting times for flow particles, i.e. synthetic travelers, are bounded by one cycle length in the analytical model.
The reason is that after one cycle the following copy of the synthetic traveler, belonging to the next cycle, arrives.
If the former traveler was still there, delay would be accumulated, which is not manageable in a cyclical model. In
MATSim, vehicles can wait unboundedly if necessary. Daily plans with long waiting times are then scored poorly and
users try to find better ones.
When modeling vehicles that queue on a link, one usually distinguishes between models with point queues and
spatial queues. In a model with point queues, queuing vehicles do not occupy space and, thus, do not influence whether
following vehicles may enter the link or not. The cyclically time-expanded network model introduced in section 2.1
belongs to the class of point queue models: The waiting links with unbounded capacity exactly represent point queues
at nodes; following vehicles are not influenced by the number of vehicles on the waiting link belonging to the link.
In a model with spatial queues, queuing vehicles occupy space and can, therefore, spill back to upstream links. The
transport simulation MATSim belongs to this class of models: The interplay between link length and vehicle size
results in a maximum number of vehicles that fit on a link. If this number is exceeded, following vehicles have to wait
on upstream links before they are allowed to enter the observed link.
Both models respect link flow capacities in terms of the maximum flow that can be processed by a link in a time
period. The cyclically time-expanded network model uses link capacities as an entering restriction for links while the
dynamic coevolutionary transport simulation uses them as exiting restrictions. So, in the analytical model congestion
builds up upstream of the bottleneck whereas in MATSim it occurs on the actual bottleneck and directly upstream of
it because of the spill back effects discussed in the last paragraph.1
Another difference is related to the way traffic flow is handled physically: In the time-expanded network model,
no vehicles are considered. Flow values may split up in arbitrarily small flow particles to different routes. To ensure
flow preservation in every node, the sum of all entering flow values (from links and from the node itself as an origin)
has to be equal to the sum of all exiting flow values (to links and to the node itself as destination). In MATSim, this
condition is not required. Flow is the sum of all individual vehicles, which cannot disappear or split, but have to travel
from their start to their end link.
In the time-expanded network queuing takes place at the waiting links and not on the links that cover a distance.
Because of this, passing of flow particles becomes possible: Following flow particles from another origin-destination
pair may directly cross the intersection, while previous flow particles use the waiting link. In the agent-based simula-
tion MATSim, links are directly represented by queues and therefore fulfill the first-in-first-out (FIFO) property. So,
no passing is possible in the simulation.
1One could also model inflow capacities in MATSim. In urban networks with short link lengths this will not give a structurally different solution.
This is due to the fact that MATSim simulates spill back effects. It would, by contrast, result in a totally different traffic flow pattern if one switches
between inflow and outflow capacities in a scenario with long link lengths.11 The reason is that spill back effects are disabled with long link lengths.
6Thunig, Nagel /Procedia Computer Science 00 (2016) 000–000
Table 1. Overview on similarities and differences of both models. The left column belongs to the cyclically time-expanded network model (named
KS model here), the right one to the dynamic coevolutionary transport simulation MATSim.
KS model MATSim
Demand stationary time-dependent
Link travel times constant constant
Waiting times bounded (cycle time) unbounded
Queues point (waiting links) spatial
Capacities inflow outflow
Physical model flow preservation mass preservation
Priority passing possible FIFO
Optimum SO =UE SO ≤UE
A final difference in between the two models consists in the applied objective function. The cyclically time-
expanded network model determines a route distribution that minimizes total travel time, which means that it finds
the system optimum. In the model, this route distribution constitutes a user equilibrium (See section 3.1. Other user
equilibria with higher travel times may exist, however. The dynamic coevolutionary transport simulation, on the other
hand, iteratively maximizes individual scores and results in a (stochastic) user equilibrium which does not necessarily
minimize total travel time, even if score only includes travel times. (See the following section for a detailed discussion
on this difference.)
Route distributions resulting from the models are mainly influenced by the fact that one model minimizes total
travel time and the other individual travel time. But all other model properties discussed before also influence the
solution properties. The next section uses knowledge about all properties and directly compares the outcome, i.e. the
traffic pattern the models result in.
3. System optima and user equilibria
Selfish user behavior does not necessarily lead to a minimal total travel time, i.e. the system optimum, neither in
theory nor in reality. For static flow models it has been shown that the difference of total travel time in user equilibrium
and system optimum may become arbitrarily large even in small networks.12 Also in a transport simulation, total
travel times of user equilibrium and system optimum may differ unboundedly.11. A typical goal is to improve the
travel time of user equilibria. As it is not possible to directly force the users to follow the system optimal routes, one
could try to indirectly force them by modifying parts of the network or designing traffic policies. By optimizing the
network structure in the mathematical model and evaluating its effect in the more realistic transport simulation, this
can be modeled. But what impact does it have that optimization assumes a system-optimal route distribution whereas
simulation evaluates it with the assumption of selfish users? This section compares properties of system optima and
user equilibria in cyclically time-expanded network models and dynamic coevolutionary transport simulations.
3.1. System optima and user equilibria in the cyclically time-expanded network model
The cyclically time-expanded network model of Strehler and K¨
ohler assumes travelers to follow the system-optimal
routes. Due to constant link travel times, the system optimum is always a user equilibrium in their model in the sense
that no user can improve their travel time by changing their route. To prove this, consider a system-optimal route
distribution and an arbitrary infinitesimal user that considers changing their route. Link travel times are constant and,
therefore, independent of the amount of flow particles using it. Changing the user’s route would therefore not change
any link travel times and by association not affect other users. It will also not improve travel time of the specific user;
otherwise, total travel time would also improve, which is a contradiction to the system optimality of the considered
distribution. Hence, no user can decrease their travel time by changing their route.3
Although the system optimum in this model is a user equilibrium, not every user equilibrium is system-optimal.
In contrast to static models without capacity restrictions, multiple user equilibria may exist in capacitated networks.
Users can occupy links and restrict the route choice for other users. The travel time of the worst user equilibrium can
Loading more pages...