persolijn

an efficient router for busses
Log | Files | Refs

BasePlanner.java (4493B)

      1 package osm.planner;
      2 
      3 import java.util.Collection;
      4 import java.util.HashMap;
      5 import java.util.List;
      6 import java.util.Map;
      7 import java.util.Stack;
      8 import java.util.concurrent.atomic.AtomicReference;
      9 
     10 import osm.planner.TargetIterable.TargetSet;
     11 import osm.routing.RoutingEdge;
     12 import osm.routing.RoutingGraph;
     13 import osm.routing.RoutingNode;
     14 import osm.routing.RoutingStrategy;
     15 import osm.routing.RoutingGraph.Route;
     16 import osm.routing.entity.Passenger;
     17 
     18 /**
     19  * An abstract base class implementing the {@link PlannerFunction} interface for
     20  * planning routes in a routing graph.
     21  *
     22  * @param <N> The type of nodes in the graph.
     23  * @param <E> The type of edges connecting the nodes.
     24  */
     25 public abstract class BasePlanner<N extends RoutingNode<N>, E extends RoutingEdge<N>> implements PlannerFunction<N, E> {
     26 
     27     /**
     28      * Plans a route based on the specified routing graph, distance function,
     29      * estimate function, garage node, and targets.
     30      *
     31      * @param router           The routing graph.
     32      * @param distanceFunction The strategy for calculating distance between nodes.
     33      * @param estimateFunction The strategy for estimating remaining distance to
     34      *                         targets.
     35      * @param garage           The starting node representing the garage or initial
     36      *                         location.
     37      * @param targets          The collection of passengers with their destination
     38      *                         nodes.
     39      * @return A list of nodes representing the planned route.
     40      */
     41     @Override
     42     public List<N> plan(
     43             RoutingGraph<N, E> router,
     44             RoutingStrategy<N, E> distanceFunction,
     45             RoutingStrategy<N, E> estimateFunction,
     46             N garage, Collection<Passenger<N>> targets) {
     47 
     48         Stack<N> path = new Stack<>();
     49 
     50         path.push(garage);
     51 
     52         long pathLength = 0;
     53         TargetIterable<Passenger<N>, N> targetIterable = new TargetIterable<>(garage, targets, path::peek,
     54                 p -> p.startPoint, p -> p.targetPoint);
     55 
     56         for (TargetSet<Passenger<N>, N> currentTargets : targetIterable) {
     57             Map<N, Long> targetEstimate = new HashMap<>();
     58 
     59             for (N target : currentTargets.targets)
     60                 targetEstimate.put(target, estimateLength(router, estimateFunction, currentTargets, target));
     61 
     62             Route<N> subPath = distanceFunction.route(router, targetEstimate, path.peek(), pathLength);
     63             if (subPath == null) {
     64                 System.out.println("nothing found searching for " + currentTargets);
     65                 return null;
     66             }
     67 
     68             path.addAll(List.of(subPath.getPath()));
     69             pathLength += subPath.getLength();
     70         }
     71 
     72         return path;
     73     }
     74 
     75     /**
     76      * Estimates the length of a route based on the specified routing graph,
     77      * estimate function, entry, and current node.
     78      *
     79      * @param router           The routing graph.
     80      * @param estimateFunction The strategy for estimating remaining distance to
     81      *                         targets.
     82      * @param entry            The set of current targets and their visitation
     83      *                         states.
     84      * @param current          The current node.
     85      * @return The estimated length of the route.
     86      */
     87     protected long estimateLength(RoutingGraph<N, E> router,
     88             RoutingStrategy<N, E> estimateFunction,
     89             TargetSet<Passenger<N>, N> entry, N current) {
     90         long pathLength = 0;
     91 
     92         AtomicReference<N> currentRef = new AtomicReference<>();
     93         currentRef.set(current);
     94 
     95         for (TargetSet<Passenger<N>, N> currentTargets : entry.doContinue(currentRef::get)) {
     96             Route<N> subPath = estimateFunction.route(router, currentTargets.targets, currentRef.get(), 0);
     97 
     98             currentRef.set(subPath.getTarget());
     99             pathLength += subPath.getLength();
    100         }
    101 
    102         return pathLength;
    103     }
    104 
    105     /**
    106      * Calculates the path score based on the specified routing graph, route length,
    107      * and passenger distances.
    108      *
    109      * @param router     The routing graph.
    110      * @param length     The length of the calculated route.
    111      * @param passengers A map containing passengers and their respective distances.
    112      * @return The calculated path score, considering the average passenger distance
    113      *         and the total route length.
    114      */
    115     protected abstract long getPathScore(RoutingGraph<N, E> router, long length, Map<Passenger<N>, Long> passengers);
    116 }