Package org.matsim.core.router
Contains different routing algorithms and PlanAlgorithms
to use the routing algorithms on plans.
The routing algorithms, responsible for finding the least-cost-path between two nodes in the network, all implement the interface
As the routing algorithms are all time-dependent, they need not only weights on the links, but time-dependent weights and additionally the (estimated) travel times on these links. This data is provided by the interfaces
All modes are not necessarily routed on the network; moreover, a trip may consist in a series of stages (movements with one vehicle, reprensented by legs), which may be separated by "dummy" activities ("stage activities"). A trip is defined as the longest sequence of consecutive plan elements consisting only of legs and stage activities. For this, the following three layer architecture is provided:
The previous behavior was based on legs rather than trips: the corresponding classes are temporarily kept in the
Note that the routing algorithms are generally seen as not thread-safe! If threads are used, one must ensure that each thread uses its own instance of a routing algorithm.
The routing algorithms, responsible for finding the least-cost-path between two nodes in the network, all implement the interface
LeastCostPathCalculator. Currently implemented are
Dijkstra's shortest path algorithm and some optimizing variants of it
(e.g. A* with Landmarks).
As the routing algorithms are all time-dependent, they need not only weights on the links, but time-dependent weights and additionally the (estimated) travel times on these links. This data is provided by the interfaces
TravelTime, TravelDisutility and
org.matsim.core.router.util.TravelMinDisutility. A few commonly used implementations of these interfaces can
be found in the subpackage costcalculators.
All modes are not necessarily routed on the network; moreover, a trip may consist in a series of stages (movements with one vehicle, reprensented by legs), which may be separated by "dummy" activities ("stage activities"). A trip is defined as the longest sequence of consecutive plan elements consisting only of legs and stage activities. For this, the following three layer architecture is provided:
- the
RoutingModules are responsible for computing trips between individual O/D couples, for a given mode. - the
TripRouterregistersRoutingModules for each mode, and allows to route between O/D pairs for any (registered) mode. It does not modify the plan, but provides convenience methods to identify trips and easily insert a trip between two activities in a plan.
- the
PlanRouterprovides aPlanAlgorithmto route all trips in a plan.
RoutingModules.
The previous behavior was based on legs rather than trips: the corresponding classes are temporarily kept in the
org.matsim.core.router.old
package for backward compatibility.
Note that the routing algorithms are generally seen as not thread-safe! If threads are used, one must ensure that each thread uses its own instance of a routing algorithm.
-
Interface Summary Interface Description AnalysisMainModeIdentifier Marker interface for MainModeIdentifier intended to be used in analysis code (e.g.FallbackRoutingModule Interface that exists so that implementations of this interface can be replaced via injection.FastRouterDelegateFactory MainModeIdentifier MultiNodePathCalculator Marker interface so that one can program against an interface rather than against a very specific implementation.RoutingModule Defines classes responsible for routing for a given (main)-mode. -
Class Summary Class Description ArrayFastRouterDelegateFactory AStarEuclidean Implements the A* router algorithm for a given NetworkLayer by using the euclidean distance divided by the maximal free speed per length unit as the heuristic estimate during routing.AStarEuclideanFactory AStarLandmarks Implements the A* router algorithm for a given NetworkLayer using some so called landmark nodes that are used to get a better estimation of the remaining travel cost.AStarLandmarksFactory DefaultRoutingModules Dijkstra Implementation of Dijkstra's shortest-path algorithm on a time-dependent network with arbitrary non-negative cost functions (e.g.DijkstraFactory FacilityWrapperActivity FastAStarEuclidean Performance optimized version of the AStarEuclideanAStarEuclideanleast cost path router which uses its own network to route within.FastAStarEuclideanFactory FastAStarLandmarks Performance optimized version of the DijkstraFastAStarLandmarksleast cost path router which uses its own network to route within.FastAStarLandmarksFactory FastDijkstra Performance optimized version of the DijkstraDijkstraleast cost path router which uses its own network to route within.FastDijkstraFactory FastMultiNodeDijkstra Performance optimized version of the MultiNodeDijkstra least cost path router which uses its own network to route within.FastMultiNodeDijkstraFactory FreespeedFactorRoutingModule ImaginaryNode Used by the MultiNodeDijkstra for backwards compatibility with default Dijkstra.InitialNode Used by the MultiNodeDijkstra to store initial time and cost.LeastCostPathCalculatorModule LinkToLinkRouting LinkWrapperFacility MainModeIdentifierImpl MultiNodeDijkstra An extended implementation of the Dijkstra algorithm that supports multiple start- and/or end nodes.MultiNodeDijkstraFactory NetworkRoutingInclAccessEgressModule This wraps a "computer science"LeastCostPathCalculator, which routes from a node to another node, into something that routes from aFacilityto anotherFacility, as we need in MATSim.NetworkRoutingModule This wraps a "computer science"LeastCostPathCalculator, which routes from a node to another node, into something that routes from aFacilityto anotherFacility, as we need in MATSim.NetworkRoutingProvider PlanRouter PlanAlgorithmresponsible for routing all trips of a plan.RoutingModeMainModeIdentifier RoutingNetworkImaginaryNode A subclass of ImaginaryNode for fast routers (FastMultiNodeDijkstra and BackwardFastMultiNodeDijkstra).SingleModeNetworksCache StageActivityTypeIdentifier It is used by theTripRouterto detect trips, and can be used by replanning modules as a "black list" of activities not to touch.TeleportationRoutingModule Transit TransitRouterWrapper Wraps aTransitRouter.TripRouter Class acting as an intermediate between clients needing to compute routes and all registeredRoutingModules.TripRouter.Builder TripRouterFactoryBuilderWithDefaults TripRouterModule TripStructureUtils Helps to work on plans with complex trips.TripStructureUtils.Subtour TripStructureUtils.Trip Represents a trip, that is, the longest sequence ofPlanElements consisting only of legs and "dummy" activities. -
Enum Summary Enum Description FastRouterType Type Pointer is no longer supported.TripStructureUtils.StageActivityHandling -
Exception Summary Exception Description TripRouter.UnknownModeException