Difference between revisions of "Demand/Dynamic User Assignment"

From Sumo
Jump to navigation Jump to search
(note on convergence and results)
(restructured page)
Line 1: Line 1:
 +
= Introduction =
 +
For a given set of vehicles with of origin-destination relations (trips), the simulation must determine routes through the network (list of edges) that are used to reach the destination from the origin edge. The simples method find these routes is by computing shortest or fastest routes through the network using a routing algorithm such as Djikstra or A*. These algorithms require assumptions regarding the travel time for each network edge which is commonly not known before running the simulation due to the fact that travel times depend on the number of vehicles in the network.
 +
{{Caution|A frequent problem with naive user assignment is that all vehicles take the fastest path under the assumption that they are alone in the network and are then jammed at bottlenecks due to the sheer amount of traffic.}}.
 +
 +
The problem of determining suitable routes that take into account travel times in a traffic-loaded network is called ''user assignment''.
 +
SUMO provides different tools to solve this problem and they are described below.
 +
 +
 +
= Iterative Assignment ('''D'''ynamic '''U'''ser '''E'''quilibrium) =
 
The tool '' {{SUMO}}/tools/assign/duaIterate.py '' can be used to compute the (approximate) dynamic user equilibrium.
 
The tool '' {{SUMO}}/tools/assign/duaIterate.py '' can be used to compute the (approximate) dynamic user equilibrium.
 
{{Caution|This script will require copious amounts of disk space}}
 
{{Caution|This script will require copious amounts of disk space}}
Line 6: Line 15:
 
''duaIterate.py'' supports many of the same options as [[SUMO]]. Any options not listed when calling ''duaIterate.py {{Option|--help}}'' can be passed to [[SUMO]] by adding {{Option|sumo--long-option-name arg}} after the regular options (i.e. {{Option|sumo--step-length 0.5}}.
 
''duaIterate.py'' supports many of the same options as [[SUMO]]. Any options not listed when calling ''duaIterate.py {{Option|--help}}'' can be passed to [[SUMO]] by adding {{Option|sumo--long-option-name arg}} after the regular options (i.e. {{Option|sumo--step-length 0.5}}.
  
= General behavior =
+
 
 
This script tries to calculate a user equilibrium, that is, it tries to find a route for each vehicle (each trip from the trip-file above) such that each vehicle cannot reduce its travel cost (usually the travel time) by using a different route. It does so iteratively (hence the name) by  
 
This script tries to calculate a user equilibrium, that is, it tries to find a route for each vehicle (each trip from the trip-file above) such that each vehicle cannot reduce its travel cost (usually the travel time) by using a different route. It does so iteratively (hence the name) by  
  
Line 20: Line 29:
 
The two methods which are implemented are called [[Publications#Traffic_Assignment|Gawron]] and Logit (reference needed!!!) in the following. The input for each of the methods is a weight or cost function <math>w</math> on the edges of the net, coming from the simulation or default costs (in the first step or for edges which have not been traveled yet), and a set of routes <math>R</math> where each route <math>r</math> has an old cost <math>c_r</math> and an old probability <math>p_r</math> (from the last iteration) and needs a new cost <math>c_r'</math> and a new probability <math>p_r'</math>.
 
The two methods which are implemented are called [[Publications#Traffic_Assignment|Gawron]] and Logit (reference needed!!!) in the following. The input for each of the methods is a weight or cost function <math>w</math> on the edges of the net, coming from the simulation or default costs (in the first step or for edges which have not been traveled yet), and a set of routes <math>R</math> where each route <math>r</math> has an old cost <math>c_r</math> and an old probability <math>p_r</math> (from the last iteration) and needs a new cost <math>c_r'</math> and a new probability <math>p_r'</math>.
  
= Logit =
+
== Logit ==
 
The Logit mechanism applies a fixed formula to each route to calculate the new probability. It ignores old costs and old probabilities and takes the route cost directly as the sum of the edge costs from the last simulation.
 
The Logit mechanism applies a fixed formula to each route to calculate the new probability. It ignores old costs and old probabilities and takes the route cost directly as the sum of the edge costs from the last simulation.
  
Line 29: Line 38:
 
<math>p_r' = \frac{\exp(\theta c_r')}{\sum_{s\in R}\exp(\theta c_s')}</math>
 
<math>p_r' = \frac{\exp(\theta c_r')}{\sum_{s\in R}\exp(\theta c_s')}</math>
  
= Gawron =
+
== Gawron ==
= Parameters =
+
 
 
= oneShot-assignment =
 
= oneShot-assignment =
An alternative to the iterative user assignment above is incremental assignment. This happens automatically when using {{XML|<trip>}} input directly in [[SUMO]] instead of {{XML|<vehicle>}}s with pre-defined routes. In this case each vehicle will compute a fastest-path computation at the time of departure which prevents all vehicles from driving blindly into the same jam and works pretty well empirically (for larger scenarios). See also [[Tools/Assign#one-shot.py]].
+
An alternative to the iterative user assignment above is incremental assignment. This happens automatically when using {{XML|<trip>}} input directly in [[SUMO]] instead of {{XML|<vehicle>}}s with pre-defined routes. In this case each vehicle will compute a fastest-path computation at the time of departure which prevents all vehicles from driving blindly into the same jam and works pretty well empirically (for larger scenarios).  
 +
 
 +
The routes for this incremental assignment are computed using the [[Demand/Automatic_Routing|Automatic Routing / Routing Device]] mechanism. Since this device allows for various configuration options, the script [[Tools/Assign#one-shot.py]] may be used to automatically try different parameter settings.
 +
 
 +
= [[MAROUTER]] =
 +
The [[MAROUTER]] application computes a ''classic'' macroscopic assignment. It employs mathematical functions (resistive functions) that approximate travel time increases when increasing flow. This allows to compute an iterative assignment without the need for time-consuming microscopic simulation.

Revision as of 05:54, 26 October 2017

Introduction

For a given set of vehicles with of origin-destination relations (trips), the simulation must determine routes through the network (list of edges) that are used to reach the destination from the origin edge. The simples method find these routes is by computing shortest or fastest routes through the network using a routing algorithm such as Djikstra or A*. These algorithms require assumptions regarding the travel time for each network edge which is commonly not known before running the simulation due to the fact that travel times depend on the number of vehicles in the network.

Caution:
A frequent problem with naive user assignment is that all vehicles take the fastest path under the assumption that they are alone in the network and are then jammed at bottlenecks due to the sheer amount of traffic.

.

The problem of determining suitable routes that take into account travel times in a traffic-loaded network is called user assignment. SUMO provides different tools to solve this problem and they are described below.


Iterative Assignment (Dynamic User Equilibrium)

The tool <SUMO_HOME>/tools/assign/duaIterate.py can be used to compute the (approximate) dynamic user equilibrium.

Caution:
This script will require copious amounts of disk space
python duaIterate.py -n <network-file> -t <trip-file> -l <nr-of-iterations>

duaIterate.py supports many of the same options as SUMO. Any options not listed when calling duaIterate.py --help can be passed to SUMO by adding sumo--long-option-name arg after the regular options (i.e. sumo--step-length 0.5.


This script tries to calculate a user equilibrium, that is, it tries to find a route for each vehicle (each trip from the trip-file above) such that each vehicle cannot reduce its travel cost (usually the travel time) by using a different route. It does so iteratively (hence the name) by

  1. calling DUAROUTER to route the vehicles in a network with the last known edge costs (starting with empty-network travel times)
  2. calling SUMO to simulate "real" travel times result from the calculated routes. The result edge costs are used in the net routing step.

The number of iterations may be set to a fixed number of determined dynamically depending on the used options. In order to ensure convergence there are different methods employed to calculate the route choice probability from the route cost (so the vehicle does not always choose the "cheapest" route). In general, new routes will be added by the router to the route set of each vehicle in each iteration (at least if none of the present routes is the "cheapest") and may be chosen according to the route choice mechanisms described below.

Between successive calls of DUAROUTER, the .rou.alt.xml format is used to record not only the current best route but also previously computed alternative routes. These routes are collected within a route distribution and used when deciding the actual route to drive in the next simulation step. This isn't always the one with the currently lowest cost but is rather sampled from the distribution of alternative routes by a configurable algorithm described below.

The option --max-convergence-deviation may be used to detect convergence and abort iterations automatically. Otherwise, a fixed number of iterations is used. Once the script finishes any of the resulting .rou.xml files may be used for simulation but the last one(s) should be the best.

The two methods which are implemented are called Gawron and Logit (reference needed!!!) in the following. The input for each of the methods is a weight or cost function on the edges of the net, coming from the simulation or default costs (in the first step or for edges which have not been traveled yet), and a set of routes where each route has an old cost and an old probability (from the last iteration) and needs a new cost and a new probability .

Logit

The Logit mechanism applies a fixed formula to each route to calculate the new probability. It ignores old costs and old probabilities and takes the route cost directly as the sum of the edge costs from the last simulation.

The probabilities are calculated from an exponential function with parameter scaled by the sum over all route values:

Gawron

oneShot-assignment

An alternative to the iterative user assignment above is incremental assignment. This happens automatically when using <trip> input directly in SUMO instead of <vehicle>s with pre-defined routes. In this case each vehicle will compute a fastest-path computation at the time of departure which prevents all vehicles from driving blindly into the same jam and works pretty well empirically (for larger scenarios).

The routes for this incremental assignment are computed using the Automatic Routing / Routing Device mechanism. Since this device allows for various configuration options, the script Tools/Assign#one-shot.py may be used to automatically try different parameter settings.

MAROUTER

The MAROUTER application computes a classic macroscopic assignment. It employs mathematical functions (resistive functions) that approximate travel time increases when increasing flow. This allows to compute an iterative assignment without the need for time-consuming microscopic simulation.