Inheritance diagram for org.matsim.core.router.speedy.SpeedyALT:

Public Member Functions
	SpeedyALT (SpeedyALTData astarData, TravelTime tt, TravelDisutility td)

double	getCost (int nodeIndex)

Path	calcLeastCostPath (Node startNode, Node endNode, double startTime, Person person, Vehicle vehicle)

Private Member Functions
double	getTimeRaw (int nodeIndex)

double	getDistance (int nodeIndex)

void	setData (int nodeIndex, double cost, double time, double distance)

double	estimateMinTravelcostToDestination (int nodeIdx, int destinationIdx)

double	estimateMinTravelcostToDestinationForLandmark (int nodeIdx, int destinationIdx, int landmarkIdx)

Path	constructPath (int endNodeIndex, double startTime)

Private Attributes
final SpeedyGraph	graph

final SpeedyALTData	astarData

final TravelTime	tt

final TravelDisutility	td

final double []	data

int	currentIteration = Integer.MIN_VALUE

final int []	iterationIds

final int []	comingFrom

final int []	usedLink

final SpeedyGraph.LinkIterator	outLI

final DAryMinHeap	pq

Static Private Attributes
static final Logger	LOG = LogManager.getLogger(SpeedyALT.class)

Detailed Description

A very fast implementation of the ALT algorithm (A*-search with Landmarks and Triangle Inequality).

Based on "Computing the Shortest Path: A* Search Meets Graph Theory" by Andrew V. Goldberg and Chris Harrelson, 2005.

This implementation always looks at all landmarks and does not filter them, as performance measurements suggest that selecting and re-selecting landmarks regularly actually results in an overhead compared to just calculate the values for each landmark in each step (using a typical value of 16 landmarks). This might be due to the fact that all values for each landmark are just next to each other in the memory, so when accessing the travelcosts to/from one landmark basically already loads the values of all landmarks in the CPU cache, making the calculation for the remaining landmarks very fast.

This implementation is not thread-safe. In the case of multi-threading, every thread should use a separate instance. (But the used SpeedyALTData is thread-safe and can be shared by multiple instances).

Author: mrieser / Simunto, sponsored by SBB Swiss Federal Railways

Definition at line 36 of file SpeedyALT.java.

Constructor & Destructor Documentation

◆ SpeedyALT()

org.matsim.core.router.speedy.SpeedyALT.SpeedyALT	(	SpeedyALTData	astarData,
		TravelTime	tt,
		TravelDisutility	td
	)

Definition at line 52 of file SpeedyALT.java.

References org.matsim.core.router.speedy.SpeedyALT.astarData, org.matsim.core.router.speedy.SpeedyGraph.getOutLinkIterator(), org.matsim.core.router.speedy.SpeedyALT.outLI, org.matsim.core.router.speedy.SpeedyALT.td, and org.matsim.core.router.speedy.SpeedyALT.tt.

                                                                                   {
         this.graph = astarData.graph;
         this.astarData = astarData;
         this.tt = tt;
         this.td = td;
         this.data = new double[this.graph.nodeCount * 3];
         this.iterationIds = new int[this.graph.nodeCount];
         this.comingFrom = new int[this.graph.nodeCount];
         this.usedLink = new int[this.graph.nodeCount];
         this.pq = new DAryMinHeap(this.graph.nodeCount, 6);
         this.outLI = this.graph.getOutLinkIterator();
         Arrays.fill(this.iterationIds, this.currentIteration);
     }

Here is the call graph for this function:

Member Function Documentation

◆ getCost()

double org.matsim.core.router.speedy.SpeedyALT.getCost ( int nodeIndex )

Definition at line 66 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath(), and org.matsim.core.router.speedy.SpeedyALT.constructPath().

                                          {
         return this.data[nodeIndex * 3];
     }

◆ getTimeRaw()

double org.matsim.core.router.speedy.SpeedyALT.getTimeRaw ( int nodeIndex )

private

Definition at line 70 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath(), and org.matsim.core.router.speedy.SpeedyALT.constructPath().

                                              {
         return this.data[nodeIndex * 3 + 1];
     }

◆ getDistance()

double org.matsim.core.router.speedy.SpeedyALT.getDistance ( int nodeIndex )

private

Definition at line 74 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath().

                                               {
         return this.data[nodeIndex * 3 + 2];
     }

◆ setData()

void org.matsim.core.router.speedy.SpeedyALT.setData	(	int	nodeIndex,
		double	cost,
		double	time,
		double	distance
	)

private

Definition at line 78 of file SpeedyALT.java.

References org.matsim.core.router.speedy.SpeedyALT.currentIteration.

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath().

                                                                                    {
         int index = nodeIndex * 3;
         this.data[index] = cost;
         this.data[index + 1] = time;
         this.data[index + 2] = distance;
         this.iterationIds[nodeIndex] = this.currentIteration;
     }

◆ calcLeastCostPath()

Path org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath	(	Node	startNode,
		Node	endNode,
		double	startTime,
		Person	person,
		Vehicle	vehicle
	)

Implements org.matsim.core.router.util.LeastCostPathCalculator.

Definition at line 87 of file SpeedyALT.java.

                                                                                                                   {
         this.currentIteration++;
         if (this.currentIteration == Integer.MAX_VALUE) {
             // reset iteration as we overflow
             Arrays.fill(this.iterationIds, this.currentIteration);
             this.currentIteration = Integer.MIN_VALUE;
         }
         boolean hasTurnRestrictions = this.graph.hasTurnRestrictions();
         int startNodeIndex = startNode.getId().index();
         int endNodeIndex = endNode.getId().index();
 
         int startDeadend = this.astarData.getNodeDeadend(startNodeIndex);
         int endDeadend = this.astarData.getNodeDeadend(endNodeIndex);
 
         double estimation = estimateMinTravelcostToDestination(startNodeIndex, endNodeIndex);
 
         this.comingFrom[startNodeIndex] = -1;
         setData(startNodeIndex, 0, startTime, 0);
         this.pq.clear();
         this.pq.insert(startNodeIndex, 0 + estimation);
         boolean foundEndNode = false;
 
         while (!this.pq.isEmpty()) {
             final int nodeIdx = this.pq.poll();
             if (nodeIdx == endNodeIndex) {
                 foundEndNode = true;
                 break;
             }
             // if turn restrictions are used, we might be on a colored node, so check for the original node
             if (hasTurnRestrictions && this.graph.getNode(nodeIdx).getId().index() == endNodeIndex) {
                 foundEndNode = true;
                 endNodeIndex = nodeIdx;
                 break;
             }
 
             // ignore dead-ends
             int deadend = this.astarData.getNodeDeadend(nodeIdx);
             if (deadend >= 0 && deadend != startDeadend && deadend != endDeadend) {
                 continue; // it's a dead-end we're not interested in
             }
 
             double currTime = getTimeRaw(nodeIdx);
             double currCost = getCost(nodeIdx);
             double currDistance = getDistance(nodeIdx);
 
             this.outLI.reset(nodeIdx);
             while (this.outLI.next()) {
                 int linkIdx = this.outLI.getLinkIndex();
                 Link link = this.graph.getLink(linkIdx);
                 int toNode = this.outLI.getToNodeIndex();
 
                 double travelTime = this.tt.getLinkTravelTime(link, currTime, person, vehicle);
                 double newTime = currTime + travelTime;
                 double travelCost = this.td.getLinkTravelDisutility(link, currTime, person, vehicle);
                 double newCost = currCost + travelCost;
 
                 if (this.iterationIds[toNode] == this.currentIteration) {
                     // this node was already visited in this route-query
                     double oldCost = getCost(toNode);
                     if (newCost < oldCost) {
                         estimation = estimateMinTravelcostToDestination(toNode, endNodeIndex);
                         this.pq.decreaseKey(toNode, newCost + estimation);
                         setData(toNode, newCost, newTime, currDistance + link.getLength());
                         this.comingFrom[toNode] = nodeIdx;
                         this.usedLink[toNode] = linkIdx;
                     }
                 } else {
                     estimation = estimateMinTravelcostToDestination(toNode, endNodeIndex);
                     setData(toNode, newCost, newTime, currDistance + link.getLength());
                     this.pq.insert(toNode, newCost + estimation);
                     this.comingFrom[toNode] = nodeIdx;
                     this.usedLink[toNode] = linkIdx;
                 }
             }
         }
 
         if (foundEndNode) {
             return constructPath(endNodeIndex, startTime);
         }
         LOG.warn("No route was found from node " + startNode.getId() + " to node " + endNode.getId() + ". Some possible reasons:");
         LOG.warn("  * Network is not connected.  Run NetworkCleaner().") ;
         LOG.warn("  * Network for considered mode does not even exist.  Modes need to be entered for each link in network.xml.");
         LOG.warn("  * Network for considered mode is not connected to starting or ending point of route.  Setting insertingAccessEgressWalk to true may help.");
         LOG.warn("This will now return null, but it may fail later with a NullPointerException.");
         return null;
     }

Here is the call graph for this function:

◆ estimateMinTravelcostToDestination()

double org.matsim.core.router.speedy.SpeedyALT.estimateMinTravelcostToDestination	(	int	nodeIdx,
		int	destinationIdx
	)

private

Definition at line 174 of file SpeedyALT.java.

References org.matsim.core.router.speedy.SpeedyALT.estimateMinTravelcostToDestinationForLandmark().

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath().

                                                                                        {
         /* The ALT algorithm uses two lower bounds for each Landmark:
          * given: source node S, target node T, landmark L
          * then, due to the triangle inequality:
          *  1) ST + TL >= SL --> ST >= SL - TL
          *  2) LS + ST >= LT --> ST >= LT - LS
          * The algorithm is interested in the largest possible value of (SL-TL) and (LT-LS),
          * as this gives the closest approximation for the minimal travel time required to
          * go from S to T.
          */
         double best = 0;
         for (int i = 0, n = this.astarData.getLandmarksCount(); i < n; i++) {
             double estimate = estimateMinTravelcostToDestinationForLandmark(nodeIdx, destinationIdx, i);
             if (estimate > best) {
                 best = estimate;
             }
         }
         return best;
     }

Here is the call graph for this function:

◆ estimateMinTravelcostToDestinationForLandmark()

double org.matsim.core.router.speedy.SpeedyALT.estimateMinTravelcostToDestinationForLandmark	(	int	nodeIdx,
		int	destinationIdx,
		int	landmarkIdx
	)

private

Definition at line 194 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.estimateMinTravelcostToDestination().

                                                                                                                    {
         double sl = this.astarData.getTravelCostToLandmark(nodeIdx, landmarkIdx);
         double ls = this.astarData.getTravelCostFromLandmark(nodeIdx, landmarkIdx);
         double tl = this.astarData.getTravelCostToLandmark(destinationIdx, landmarkIdx);
         double lt = this.astarData.getTravelCostFromLandmark(destinationIdx, landmarkIdx);
         double sltl = sl - tl;
         double ltls = lt - ls;
         return Math.max(sltl, ltls);
     }

◆ constructPath()

Path org.matsim.core.router.speedy.SpeedyALT.constructPath	(	int	endNodeIndex,
		double	startTime
	)

private

Definition at line 204 of file SpeedyALT.java.

References org.matsim.core.router.speedy.SpeedyALT.getCost(), and org.matsim.core.router.speedy.SpeedyALT.getTimeRaw().

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath().

                                                                    {
         double travelCost = getCost(endNodeIndex);
         double arrivalTime = getTimeRaw(endNodeIndex);
         if (Double.isInfinite(arrivalTime)) {
             throw new RuntimeException("Undefined time on end node");
         }
         double travelTime = arrivalTime - startTime;
 
         List<Node> nodes = new ArrayList<>();
         List<Link> links = new ArrayList<>();
 
         int nodeIndex = endNodeIndex;
 
         nodes.add(this.graph.getNode(nodeIndex));
 
         int linkIndex = this.usedLink[nodeIndex];
         nodeIndex = this.comingFrom[nodeIndex];
 
         while (nodeIndex >= 0) {
             nodes.add(this.graph.getNode(nodeIndex));
             links.add(this.graph.getLink(linkIndex));
 
             linkIndex = this.usedLink[nodeIndex];
             nodeIndex = this.comingFrom[nodeIndex];
         }
 
         Collections.reverse(nodes);
         Collections.reverse(links);
 
         return new Path(nodes, links, travelTime, travelCost);
     }

Here is the call graph for this function:

Member Data Documentation

◆ LOG

final Logger org.matsim.core.router.speedy.SpeedyALT.LOG = LogManager.getLogger(SpeedyALT.class)

staticprivate

Definition at line 38 of file SpeedyALT.java.

◆ graph

final SpeedyGraph org.matsim.core.router.speedy.SpeedyALT.graph

private

Definition at line 40 of file SpeedyALT.java.

◆ astarData

final SpeedyALTData org.matsim.core.router.speedy.SpeedyALT.astarData

private

Definition at line 41 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.SpeedyALT().

◆ tt

final TravelTime org.matsim.core.router.speedy.SpeedyALT.tt

private

Definition at line 42 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.SpeedyALT().

◆ td

final TravelDisutility org.matsim.core.router.speedy.SpeedyALT.td

private

Definition at line 43 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.SpeedyALT().

◆ data

final double [] org.matsim.core.router.speedy.SpeedyALT.data

private

Definition at line 44 of file SpeedyALT.java.

◆ currentIteration

int org.matsim.core.router.speedy.SpeedyALT.currentIteration = Integer.MIN_VALUE

private

Definition at line 45 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.setData().

◆ iterationIds

final int [] org.matsim.core.router.speedy.SpeedyALT.iterationIds

private

Definition at line 46 of file SpeedyALT.java.

◆ comingFrom

final int [] org.matsim.core.router.speedy.SpeedyALT.comingFrom

private

Definition at line 47 of file SpeedyALT.java.

◆ usedLink

final int [] org.matsim.core.router.speedy.SpeedyALT.usedLink

private

Definition at line 48 of file SpeedyALT.java.

◆ outLI

final SpeedyGraph.LinkIterator org.matsim.core.router.speedy.SpeedyALT.outLI

private

Definition at line 49 of file SpeedyALT.java.

Referenced by org.matsim.core.router.speedy.SpeedyALT.calcLeastCostPath(), and org.matsim.core.router.speedy.SpeedyALT.SpeedyALT().

◆ pq

final DAryMinHeap org.matsim.core.router.speedy.SpeedyALT.pq

private

Definition at line 50 of file SpeedyALT.java.

The documentation for this class was generated from the following file:

core/router/speedy/SpeedyALT.java

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SpeedyALT()

Member Function Documentation

◆ getCost()

◆ getTimeRaw()

◆ getDistance()

◆ setData()

◆ calcLeastCostPath()

◆ estimateMinTravelcostToDestination()

◆ estimateMinTravelcostToDestinationForLandmark()

◆ constructPath()

Member Data Documentation

◆ LOG

◆ graph

◆ astarData

◆ tt

◆ td

◆ data

◆ currentIteration

◆ iterationIds

◆ comingFrom

◆ usedLink

◆ outLI

◆ pq