Dynamical System Framework
Loading...
Searching...
No Matches
dsf::mobility::Router Class Reference

Plans routes on a road network with the A* algorithm. More...

#include <Router.hpp>

Public Types

using EdgeWeight = std::function<double(Street const&)>
 A street cost function.

Public Member Functions

void setEdgeWeight (std::string_view name, double distanceCost=0.1)
 Set the street costs of the routes.
double distanceCost () const noexcept
 Get the distance cost of the routes, in s/m (0 unless "datt").
void setPathRandomness (double sigma)
 Set the path randomness.
double pathRandomness () const noexcept
 Get the path randomness (see setPathRandomness).
void setAlgorithm (RouteAlgorithm const algorithm) noexcept
 Set the search algorithm.
auto algorithm () const noexcept
 Get the search algorithm.
void build (RoadNetwork const &network)
 Build the routing graph of a network.
void updateCurrentWeights ()
 Take a snapshot of the current street weights (see setEdgeWeight).
std::vector< Id > route (Id fromStreetId, Id goalStreetId, RouteWeights weights, std::uint64_t agentKey=0) const
 Plan a route from a street to the end of a street.
std::vector< Id > routeFromNode (Id fromNodeId, Id goalStreetId, RouteWeights weights, std::uint64_t agentKey=0) const
 Plan a route from a node to the end of a street.
double routeCost (std::span< Id const > route, RouteWeights weights, std::uint64_t agentKey=0) const
 Get the cost of a route.
bool isTurnAllowed (Id fromStreetId, Id toStreetId) const
 Check whether the routing graph allows a turn.
bool isBuilt () const noexcept
 Check whether the router has been built.
std::size_t nEdges () const noexcept
 Get the number of streets of the routing graph.
bool hasHeuristic () const noexcept
 Check whether the coordinates allow the straight-line distance heuristic.

Static Public Member Functions

static EdgeWeight edgeWeightFunction (std::string_view name, double distanceCost=0.1)
 Get a street cost function by name.
static double noise (std::uint64_t agentKey, Id streetId, double sigma)
 Get the noise an agent perceives on a street cost.

Detailed Description

Plans routes on a road network with the A* algorithm.

The search runs on the streets (the dual graph), so that forbidden turns and the U-turn rule of RoadNetwork::isTurnAllowed are honoured. A route ends with the goal street, entered by an allowed turn: it reaches the end of it. The router holds a compact copy of the network's topology and of the street costs: it must be rebuilt (see build) whenever streets are added, opened or closed, or their turns or speeds change. Route queries are const and thread-safe, as each thread searches with its own buffers; building and taking snapshots are not.

The heuristic is the straight-line distance to the goal street's target node, scaled by the lowest cost per unit of distance over all streets, which makes it admissible and consistent for any non-negative costs and any coordinate system. Without coordinates on every node touching a street the heuristic is zero, i.e. the search is Dijkstra's.

With "datt" (the detour-avoiding travel time, see setEdgeWeight) every street also costs distanceCost · length. With path randomness (see setPathRandomness) each agent perceives each street cost multiplied by its own log-normal noise (see noise), so that agents with the same trip spread over more routes, whatever the weight.

Member Function Documentation

◆ build()

void dsf::mobility::Router::build ( RoadNetwork const & network)

Build the routing graph of a network.

Parameters
networkThe road network

Also takes a snapshot of the current weights (see updateCurrentWeights)

◆ edgeWeightFunction()

Router::EdgeWeight dsf::mobility::Router::edgeWeightFunction ( std::string_view name,
double distanceCost = 0.1 )
static

Get a street cost function by name.

Parameters
nameOne of:
  • "traveltime": the street's estimated travel time plus the time needed to clear its exit queues, i.e. estimatedTravelTime() + nExitingAgents(ANY, true) / min(1, transportCapacity())
  • "length": the street's length
  • "uniform": 1 for every street
  • "datt" (detour-avoiding travel time): "traveltime" plus distanceCost · length
  • any other value is used as the name of a numeric custom attribute of the streets
distanceCostThe cost of a unit of length of "datt", in time per unit of length (s/m): 0.1 makes a metre cost as much as driving it at 10 m/s
Returns
EdgeWeight The cost function

◆ isTurnAllowed()

bool dsf::mobility::Router::isTurnAllowed ( Id fromStreetId,
Id toStreetId ) const

Check whether the routing graph allows a turn.

Parameters
fromStreetIdThe street the agent is on
toStreetIdThe street the agent would take next
Returns
true if toStreetId is open and the turn is allowed (see RoadNetwork::isTurnAllowed), false otherwise or if a street is unknown

◆ noise()

double dsf::mobility::Router::noise ( std::uint64_t agentKey,
Id streetId,
double sigma )
static

Get the noise an agent perceives on a street cost.

Parameters
agentKeyA key identifying the agent
streetIdThe street id
sigmaThe spread of the noise
Returns
double exp(sigma · Z - sigma² / 2), i.e. log-normal of mean 1 as in MATSim, with Z standard normal, drawn from a hash of the agent key and the street id (so the same at every call) and clamped to [-3, 3]; 1 if sigma is 0

◆ route()

std::vector< Id > dsf::mobility::Router::route ( Id fromStreetId,
Id goalStreetId,
RouteWeights weights,
std::uint64_t agentKey = 0 ) const

Plan a route from a street to the end of a street.

Parameters
fromStreetIdThe street the route starts with: its own cost is not counted
goalStreetIdThe street to reach and travel: its cost is counted
weightsThe street costs to plan on
agentKeyA key identifying the agent, for its noise (see setPathRandomness)
Returns
std::vector<Id> The ids of the streets to travel, from fromStreetId to goalStreetId, or an empty vector if goalStreetId cannot be reached. It is fromStreetId alone if the two are the same
Exceptions
std::out_of_rangeif a street is not in the routing graph

◆ routeCost()

double dsf::mobility::Router::routeCost ( std::span< Id const > route,
RouteWeights weights,
std::uint64_t agentKey = 0 ) const

Get the cost of a route.

Parameters
routeThe ids of the streets of the route
weightsThe street costs to use
agentKeyA key identifying the agent, for its noise (see setPathRandomness)
Returns
double The sum of the costs of the streets of the route, but the first, as the agent perceives them
Exceptions
std::out_of_rangeif a street is not in the routing graph

◆ routeFromNode()

std::vector< Id > dsf::mobility::Router::routeFromNode ( Id fromNodeId,
Id goalStreetId,
RouteWeights weights,
std::uint64_t agentKey = 0 ) const

Plan a route from a node to the end of a street.

Parameters
fromNodeIdThe node the route starts from: the cost of the first street counts
goalStreetIdThe street to reach and travel: its cost is counted
weightsThe street costs to plan on
agentKeyA key identifying the agent, for its noise (see setPathRandomness)
Returns
std::vector<Id> The ids of the streets to travel, from an open outgoing street of fromNodeId to goalStreetId, or an empty vector if goalStreetId cannot be reached
Exceptions
std::out_of_rangeif the node or the street is not in the routing graph

◆ setAlgorithm()

void dsf::mobility::Router::setAlgorithm ( RouteAlgorithm const algorithm)
inlinenoexcept

Set the search algorithm.

Parameters
algorithmThe algorithm (A* by default)

◆ setEdgeWeight()

void dsf::mobility::Router::setEdgeWeight ( std::string_view name,
double distanceCost = 0.1 )

Set the street costs of the routes.

Parameters
nameThe name of the cost function (see edgeWeightFunction), "traveltime" by default. It sets the current weights; "datt" also adds distanceCost · length to every street of every route, free-flow ones included
distanceCostThe cost of a unit of length of "datt", in s/m

The current weights change at the next snapshot (see updateCurrentWeights)

Exceptions
std::invalid_argumentif distanceCost is negative

◆ setPathRandomness()

void dsf::mobility::Router::setPathRandomness ( double sigma)

Set the path randomness.

Parameters
sigmaThe spread of the log-normal noise each agent perceives on each street cost (see noise), 0 (the default) to plan without noise
Exceptions
std::invalid_argumentif sigma is negative

◆ updateCurrentWeights()

void dsf::mobility::Router::updateCurrentWeights ( )

Take a snapshot of the current street weights (see setEdgeWeight).

The streets are evaluated in parallel: no street may change meanwhile.


The documentation for this class was generated from the following files:
  • src/dsf/mobility/Router.hpp
  • src/dsf/mobility/Router.cpp