Simulation/Routing

generated on 2018-12-14 00:24:44.848545 from the wiki page for Simulation/Routing for SUMO git

Features that cause rerouting

There are multiple simulation features that allow routing at simulation time. They are described in the following:

Routing triggered by the vehicle

This type of routing works by assigning a rerouting device to some or all vehicles. Details are given at Demand/Automatic_Routing.

Incomplete Trips and Flows

This is a special case of the above method. Vehicles with incomplete routes automatically receive a rerouting device and are rerouted once when entering the network. In some scenarios this is a practical one-shot-approach to route assignment that avoids time-consuming iterative assignment.

Alternative Route Signage

This is a location based method for triggering rerouting and is described at Simulation/Rerouter.

TraCI

Using the methods traci.vehicle.changeTarget or traci.vehicle.rerouteTraveltime rerouting is triggered for the specified vehicle. Alternatively, routes can be computed using traci.simulation.findRoute and applied using traci.vehicle.setRoute.

Alternative Destinations

By using <rerouter>-definitions, vehicles can be routed to alternative destinations. A different method is to use traffic assignment zones (TAZ). This allows vehicles to change their destination to the best alternative from a list of potential destinations.

Travel-time values for routing

By default, the route with the least travel time is chosen. The travel time depends on the current routinng mode (configurable via traci.vehicle.setRoutingMode).

Routing Mode traci.constants.ROUTING_MODE_DEFAULT

The following order of steps is taken to retrieve the travel time for each edge (If one step fails due to lack of data, the next step is taken):

  1. The vehicle retrieves it's individual data storage. This can be set and retrieved using the TraCI vehicle methods change edge travel time information and edge travel time information.
  2. The global edge weights loaded using option --weight-files are retrieved.
  3. The global edge weights (set and retrieved via TraCI) using the TraCI edge methods change edge travel time information and edge travel time information.
  4. The minimum travel time (length/allowedSpeed) is used.
Note:
The edge weights for cases 1-3 support modeling time-dependent variations in edge travel time. This means future changes in travel time along a vehicles route can be taking into account when routing.

Routing Mode traci.constants.ROUTING_MODE_AGGREGATED

The smoothed travel times computed for the rerouting device are used.

Special cases

  • When rerouting with the rerouting device the travel time always comes from another data storage which is updated continuously with a configurable averaging procedure. The parameters for this updating strategy are user definable. It is also possible to set the device travel time directly via TraCI.
  • When using the TraCI method rerouteTraveltime from the python TraCI library, the command supports an additional boolean parameter currentTravelTime (default True). When this parameter is set to True, the global edge weights are replaced by to the currently measured travel times before rerouting. To replicate this behavior with other TraCI clients, all edges in the network must be called with change global travel time information using the value of current travel time. Note that the travel time values which are set in this way are used for the full duration of the simulation unless updated again.

Routing by effort

When setting the options --weight-file and --weight-attribute, additional routing efforts are read according to the specified attribute. These are only used when calling the TraCI function reroute by effort. The assumed efforts along a vehicles route are are time-based values and the time is computed based on the travel time values described above. The effort can also be set using traci.edge.setEffort.

Caution:
The default effort value is -1 which causes detour routes to be preferred when not loading sensible effort values.

Routing Algorithms

Applications that perform routing (SUMO, SUMO-GUI, DUAROUTER, MAROUTER) support the option --routing.algorithm for selecting among the following values:

  • dijkstra: (default) Dijkstras algorithm is the simplest and slowest of routing algorithms. It is well suited to routing in time-dependent networks (i.e. when the travel time on an edge depends on the time of day)
  • astar: The A* routing algorithm uses a metric for bounding travel time to direct the search and is often faster than dijkstra. Here, the metric euclidean distance / maximumVehicleSpeed) is used.
    • by using astar together with the option --astar.landmark-distance <FILE> the ALT-Algorithm is activated (A*, Landmarks, triangle inequality). It uses a precomputed distance table to selected network edges (so-called landmarks) to speed up the search, often by a significant factor.
    • by using astar together with the option --astar.all-distances <FILE> the A* algorithm is used together with a complete (and often huge) distance table to allow for blazing fast search.
  • CH: Contraction Hierarchies is preprocessing-based routing algorithm. This is very efficient when a large number of queries is expected. The algorithm does consider time-dependent weights. Instead, new preprocessing can be performed for time-slices of fixed size by setting the option --weight-period <TIME>. The preprocessing is done without restrictions on vehicle class which reduces efficiency in multi-modal networks.
  • CHWrapper: This works like CH but performs separate preprocessing for every vehicle class that is encountered, thereby increasing routing efficiency.

This page was last modified on 13 November 2018, at 20:13.