BasePlanner.java (4493B) download
1package osm.planner;
2
3import java.util.Collection;
4import java.util.HashMap;
5import java.util.List;
6import java.util.Map;
7import java.util.Stack;
8import java.util.concurrent.atomic.AtomicReference;
9
10import osm.planner.TargetIterable.TargetSet;
11import osm.routing.RoutingEdge;
12import osm.routing.RoutingGraph;
13import osm.routing.RoutingNode;
14import osm.routing.RoutingStrategy;
15import osm.routing.RoutingGraph.Route;
16import 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 */
25public 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}