Package org.goplanit.algorithms.shortest

Class ShortestPathAStar

  • All Implemented Interfaces:
    ShortestPathOneToOne
    public class ShortestPathAStar
extends Object
implements ShortestPathOneToOne
    A* shortest path algorithm A* shortest path is a one-to-one implementation of the shortest path algorithm based on the generalized costs on each link segment (edge). The costs should be provided upon instantiation and are reused whenever a One-To-One execution conditional on the chosen source node is performed. In its current form, it assumes a macroscopic network and macroscopic link segments to operate on
    Author:
    markr

    • Field Detail

      • edgeSegmentCosts

        protected final double[] edgeSegmentCosts
        The cost for each edge to determine shortest paths

      • numberOfEdgeSegments

        protected final int numberOfEdgeSegments
        The number of edge segments considered

      • numberOfVertices

        protected final int numberOfVertices
        The number of vertices in the network

      • geoUtils

        protected final PlanitJtsCrsUtils geoUtils
        CRS based utility class to interpret the position information of vertices

      • heuristicDistanceMultiplier

        protected final double heuristicDistanceMultiplier
        conversion multiplier to convert distance (km) to cost

      • pairSecondComparator

        protected static final Comparator<Pair<DirectedVertex,​Double>> pairSecondComparator
        Comparator to sort based on the second elements minimum value (ascending order)

    • Constructor Detail

      • ShortestPathAStar

        public ShortestPathAStar​(double[] edgeSegmentCosts,
                         int numberOfVertices,
                         org.opengis.referencing.crs.CoordinateReferenceSystem crs,
                         double heuristicDistanceMultiplier)
        Constructor for an edge cost based A* algorithm for finding shortest paths.
        Parameters:
        edgeSegmentCosts - Edge segment costs
        numberOfVertices - number of vertices in the network
        crs - the coordinate reference system used in the network, i.e., we can draw upon the geo information of the vertices to compute our heuristic component
        heuristicDistanceMultiplier - used to convert the distance between two vertices to a cost, in transport context this would generally be the 1/(maximum speed (km/h)), e.g. pace to convert a heuristic distance (km) into travel time (h) since (km* h/km = h).

    • Method Detail

      • executeOneToOne

        public ShortestPathResult executeOneToOne​(DirectedVertex origin,
                                          DirectedVertex destination,
                                          Set<? extends EdgeSegment> bannedSegments)
        Construct shortest paths from source node to all other nodes in the network based on directed LinkSegment edges while imposing custom constraints on certain edge segments not being allowed to be used We create the heuristic costs on-the-fly based on the coordinates of the vertex and computing the as-the-crow-flies lower bound cost. Can only be used when instance was created by providing ${code CRS} and ${codeheuristicDistanceMultiplier} in constructor. Also, all network entities should hold geo positions otherwise the execution will fail with a nullpointer.
        Specified by:
        executeOneToOne in interface ShortestPathOneToOne
        Parameters:
        origin - vertex of source node
        destination - vertex of sink node
        bannedSegments - segments not allowed to be used
        Returns:
        shortest path result of the execution