- 1 Features that cause rerouting
- 2 Alternative Destinations
- 3 Travel-time values for routing
- 4 Routing by effort
- 5 Routing by distance
- 6 Routing Algorithms
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.
Using the methods traci.vehicle.changeTarget or traci.vehicle.rerouteTraveltime rerouting is triggered for the specified vehicle.
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) or via the explicit routingMode argument to traci.simulation.findRoute.
Routing Mode traci.constants.ROUTING_MODE_DEFAULT
The following order of steps is taken to retrieve the travel time for each edge. If a step provides data, this is used, otherwise the next step is attempted:
- 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.
- The global edge weights loaded using option --weight-files are retrieved.
- The global edge weights (set and retrieved via TraCI) using the TraCI edge methods change edge travel time information and edge travel time information.
- The minimum travel time (length/allowedSpeed) is used.
Routing Mode traci.constants.ROUTING_MODE_AGGREGATED
The smoothed travel times computed for the rerouting device are used.
- 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.
Routing by distance
Finding the shortest route rather than the fastests can be achieved by loading suitable effort-data (see #Routing_by_effort) or by setting the speed for all network edges to the same value.
A simpler solution is to define a vehicle type that travels with the same speed on all edges:
<vType id="routeByDistance" maxSpeed="1"/>
and then using that type to find the fastest route:
stageResult = traci.simulation.findRoute(fromEdge, toEdge, "routeByDistance") shortestDistance = stage.length
- 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.