View Javadoc
1   package org.opentrafficsim.road.gtu.generator.od;
2   
3   import java.util.ArrayList;
4   import java.util.Arrays;
5   import java.util.Comparator;
6   import java.util.LinkedHashMap;
7   import java.util.LinkedHashSet;
8   import java.util.List;
9   import java.util.Map;
10  import java.util.Map.Entry;
11  import java.util.Set;
12  import java.util.stream.Collectors;
13  
14  import org.djunits.unit.FrequencyUnit;
15  import org.djunits.value.vdouble.scalar.Duration;
16  import org.djunits.value.vdouble.scalar.Frequency;
17  import org.djunits.value.vdouble.scalar.Length;
18  import org.djunits.value.vdouble.scalar.Time;
19  import org.djutils.exceptions.Throw;
20  import org.opentrafficsim.base.parameters.ParameterException;
21  import org.opentrafficsim.core.distributions.Generator;
22  import org.opentrafficsim.core.distributions.ProbabilityException;
23  import org.opentrafficsim.core.dsol.OTSSimulatorInterface;
24  import org.opentrafficsim.core.gtu.GTUDirectionality;
25  import org.opentrafficsim.core.gtu.GTUException;
26  import org.opentrafficsim.core.gtu.GTUType;
27  import org.opentrafficsim.core.idgenerator.IdGenerator;
28  import org.opentrafficsim.core.math.Draw;
29  import org.opentrafficsim.core.network.Link;
30  import org.opentrafficsim.core.network.LinkType;
31  import org.opentrafficsim.core.network.NetworkException;
32  import org.opentrafficsim.core.network.Node;
33  import org.opentrafficsim.road.gtu.generator.GeneratorPositions;
34  import org.opentrafficsim.road.gtu.generator.GeneratorPositions.LaneBiases;
35  import org.opentrafficsim.road.gtu.generator.LaneBasedGTUGenerator;
36  import org.opentrafficsim.road.gtu.generator.LaneBasedGTUGenerator.RoomChecker;
37  import org.opentrafficsim.road.gtu.generator.MarkovCorrelation;
38  import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGTUCharacteristics;
39  import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGTUCharacteristicsGenerator;
40  import org.opentrafficsim.road.gtu.generator.headway.Arrivals;
41  import org.opentrafficsim.road.gtu.generator.headway.ArrivalsHeadwayGenerator;
42  import org.opentrafficsim.road.gtu.generator.headway.ArrivalsHeadwayGenerator.HeadwayDistribution;
43  import org.opentrafficsim.road.gtu.generator.headway.DemandPattern;
44  import org.opentrafficsim.road.gtu.strategical.od.Categorization;
45  import org.opentrafficsim.road.gtu.strategical.od.Category;
46  import org.opentrafficsim.road.gtu.strategical.od.ODMatrix;
47  import org.opentrafficsim.road.network.OTSRoadNetwork;
48  import org.opentrafficsim.road.network.lane.CrossSectionLink;
49  import org.opentrafficsim.road.network.lane.DirectedLanePosition;
50  import org.opentrafficsim.road.network.lane.Lane;
51  import org.opentrafficsim.road.network.lane.object.sensor.DestinationSensor;
52  import org.opentrafficsim.road.network.lane.object.sensor.Sensor;
53  
54  import nl.tudelft.simulation.dsol.SimRuntimeException;
55  import nl.tudelft.simulation.dsol.logger.SimLogger;
56  import nl.tudelft.simulation.dsol.simulators.DEVSSimulatorInterface;
57  import nl.tudelft.simulation.jstats.streams.MersenneTwister;
58  import nl.tudelft.simulation.jstats.streams.StreamInterface;
59  
60  /**
61   * Utility to create vehicle generators on a network from an OD.
62   * <p>
63   * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
64   * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
65   * <p>
66   * @version $Revision$, $LastChangedDate$, by $Author$, initial version 30 nov. 2017 <br>
67   * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
68   * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
69   * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
70   */
71  public final class ODApplier
72  {
73  
74      /**
75       * Utility class.
76       */
77      private ODApplier()
78      {
79          //
80      }
81  
82      /**
83       * Applies the OD to the network by creating vehicle generators. The map returned contains objects created for vehicle
84       * generation. These are bundled in a {@code GeneratorObjects} and mapped to the vehicle generator id. Vehicle generator id
85       * is equal to the origin node id. For lane-based generators the id's are appended with an ordered number (e.g. A1), where
86       * the ordering is first by link id, and then right to left concerning the lateral lane position at the start of the lane.
87       * For node "A" this would for example be:<br>
88       * <table >
89       * <caption>&nbsp;</caption>
90       * <tr>
91       * <th>Generator id</th>
92       * <th>Link</th>
93       * <th>Lateral start offset</th>
94       * </tr>
95       * <tr>
96       * <th>A1</th>
97       * <th>AB</th>
98       * <th>-1.75m</th>
99       * </tr>
100      * <tr>
101      * <th>A2</th>
102      * <th>AB</th>
103      * <th>1.75m</th>
104      * </tr>
105      * <tr>
106      * <th>A3</th>
107      * <th>AC</th>
108      * <th>-3.5m</th>
109      * </tr>
110      * <tr>
111      * <th>A4</th>
112      * <th>AC</th>
113      * <th>0.0m</th>
114      * </tr>
115      * </table>
116      * @param network OTSRoadNetwork; network
117      * @param od ODMatrix; OD matrix
118      * @param simulator OTSSimulatorInterface; simulator
119      * @param odOptions ODOptions; options for vehicle generation
120      * @return Map&lt;String, GeneratorObjects&gt; map of generator id's and created generator objects mainly for testing
121      * @throws ParameterException if a parameter is missing
122      * @throws SimRuntimeException if this method is called after simulation time 0
123      */
124     @SuppressWarnings("checkstyle:methodlength")
125     public static Map<String, GeneratorObjects> applyOD(final OTSRoadNetwork network, final ODMatrix od,
126             final OTSSimulatorInterface simulator, final ODOptions odOptions) throws ParameterException, SimRuntimeException
127     {
128         Throw.whenNull(network, "Network may not be null.");
129         Throw.whenNull(od, "OD matrix may not be null.");
130         Throw.whenNull(simulator, "Simulator may not be null.");
131         Throw.whenNull(odOptions, "OD options may not be null.");
132         Throw.when(!simulator.getSimulatorTime().eq0(), SimRuntimeException.class,
133             "Method ODApplier.applyOD() should be invoked at simulation time 0.");
134 
135         // TODO sinks? white extension links?
136         for (Node destination : od.getDestinations())
137         {
138             createSensorsAtDestination(destination, simulator);
139         }
140 
141         final Categorization categorization = od.getCategorization();
142         final boolean laneBased = categorization.entails(Lane.class);
143         boolean markovian = od.getCategorization().entails(GTUType.class);
144 
145         // TODO clean up stream acquiring code after task OTS-315 has been completed
146         StreamInterface stream = simulator.getReplication().getStream("generation");
147         if (stream == null)
148         {
149             stream = simulator.getReplication().getStream("default");
150             if (stream == null)
151             {
152                 System.out.println(
153                     "Using locally created stream (not from the simulator) for vehicle generation, with seed 1.");
154                 stream = new MersenneTwister(1L);
155             }
156             else
157             {
158                 System.out.println("Using stream 'default' for vehicle generation.");
159             }
160         }
161 
162         Map<String, GeneratorObjects> output = new LinkedHashMap<>();
163         for (Node origin : od.getOrigins())
164         {
165             // Step 1: create DemandNode trees, starting with a root for each vehicle generator
166             DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> rootNode = null; // root node for each generator
167             /**
168              * Depending on whether the categorization is lane based or not, we either have 1 root per origin, or we have 1 root
169              * per lane (i.e. 1 generator at an origin putting traffic on multiple lanes, or N generators per origin, each
170              * generating traffic on 1 lane). In order to know to which root node the sub nodes belong in a loop, we store root
171              * nodes by lane. Effectively, the map functions as an artificial branching of demand before the origin node, only
172              * used if the categorization contains lanes. For non-lane based demand, the root node and destination node created
173              * in the outer loop can simply be used.
174              */
175             Map<Lane, DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>> originNodePerLane = new LinkedHashMap<>();
176             MarkovChain markovChain = null;
177             if (!laneBased)
178             {
179                 rootNode = new DemandNode<>(origin, stream, null);
180                 LinkType linkType = getLinkTypeFromNode(origin);
181                 if (markovian)
182                 {
183                     MarkovCorrelation<GTUType, Frequency> correlation = odOptions.get(ODOptions.MARKOV, null, origin,
184                         linkType);
185                     if (correlation != null)
186                     {
187                         Throw.when(!od.getCategorization().entails(GTUType.class), IllegalArgumentException.class,
188                             "Markov correlation can only be used on OD categorization entailing GTU type.");
189                         markovChain = new MarkovChain(correlation);
190                     }
191                 }
192             }
193             for (Node destination : od.getDestinations())
194             {
195                 Set<Category> categories = od.getCategories(origin, destination);
196                 if (!categories.isEmpty())
197                 {
198                     DemandNode<Node, DemandNode<Category, ?>> destinationNode = null;
199                     if (!laneBased)
200                     {
201                         destinationNode = new DemandNode<>(destination, stream, markovChain);
202                         rootNode.addChild(destinationNode);
203                     }
204                     for (Category category : categories)
205                     {
206                         if (laneBased)
207                         {
208                             // obtain or create root and destination nodes
209                             Lane lane = category.get(Lane.class);
210                             rootNode = originNodePerLane.get(lane);
211                             if (rootNode == null)
212                             {
213                                 rootNode = new DemandNode<>(origin, stream, null);
214                                 originNodePerLane.put(lane, rootNode);
215                             }
216                             destinationNode = rootNode.getChild(destination);
217                             if (destinationNode == null)
218                             {
219                                 markovChain = null;
220                                 if (markovian)
221                                 {
222                                     MarkovCorrelation<GTUType, Frequency> correlation = odOptions.get(ODOptions.MARKOV, lane,
223                                         origin, lane.getParentLink().getLinkType());
224                                     if (correlation != null)
225                                     {
226                                         Throw.when(!od.getCategorization().entails(GTUType.class),
227                                             IllegalArgumentException.class,
228                                             "Markov correlation can only be used on OD categorization entailing GTU type.");
229                                         markovChain = new MarkovChain(correlation); // 1 for each generator
230                                     }
231                                 }
232                                 destinationNode = new DemandNode<>(destination, stream, markovChain);
233                                 rootNode.addChild(destinationNode);
234                             }
235                         }
236                         DemandNode<Category, ?> categoryNode = new DemandNode<>(category, od.getDemandPattern(origin,
237                             destination, category));
238                         if (markovian)
239                         {
240                             destinationNode.addLeaf(categoryNode, category.get(GTUType.class));
241                         }
242                         else
243                         {
244                             destinationNode.addChild(categoryNode);
245                         }
246                     }
247                 }
248             }
249 
250             // Step 2: gather DirectedLanePositions for each generator pertaining to each DemandNode<...>
251             Map<DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>, Set<DirectedLanePosition>> initialPositions =
252                 new LinkedHashMap<>();
253             Map<CrossSectionLink, Double> linkWeights = null;
254             Map<CrossSectionLink, Node> viaNodes = null;
255             if (laneBased)
256             {
257                 for (Lane lane : originNodePerLane.keySet())
258                 {
259                     DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> demandNode = originNodePerLane.get(lane);
260                     Set<DirectedLanePosition> initialPosition = new LinkedHashSet<>();
261                     try
262                     {
263                         initialPosition.add(lane.getParentLink().getStartNode().equals(demandNode.getObject())
264                             ? new DirectedLanePosition(lane, Length.ZERO, GTUDirectionality.DIR_PLUS)
265                             : new DirectedLanePosition(lane, lane.getLength(), GTUDirectionality.DIR_MINUS));
266                     }
267                     catch (GTUException ge)
268                     {
269                         throw new RuntimeException(ge);
270                     }
271                     initialPositions.put(demandNode, initialPosition);
272                 }
273             }
274             else
275             {
276                 Set<DirectedLanePosition> positionSet = new LinkedHashSet<>();
277                 for (Link link : origin.getLinks())
278                 {
279                     if (link.getLinkType().isConnector())
280                     {
281                         if (link.getStartNode().equals(origin))
282                         {
283                             Node connectedNode = link.getEndNode();
284                             // count number of served links
285                             int served = 0;
286                             for (Link connectedLink : connectedNode.getLinks())
287                             {
288                                 if (connectedLink instanceof CrossSectionLink && !connectedLink.getLinkType().isConnector())
289                                 {
290                                     served++;
291                                 }
292                             }
293                             for (Link connectedLink : connectedNode.getLinks())
294                             {
295                                 if (connectedLink instanceof CrossSectionLink)
296                                 {
297                                     if (link instanceof CrossSectionLink./../org/opentrafficsim/road/network/lane/CrossSectionLink.html#CrossSectionLink">CrossSectionLink && ((CrossSectionLink) link)
298                                         .getDemandWeight() != null)
299                                     {
300                                         if (linkWeights == null)
301                                         {
302                                             linkWeights = new LinkedHashMap<>();
303                                             viaNodes = new LinkedHashMap<>();
304                                         }
305                                         // store weight under connected link, as this
306                                         linkWeights.put(((CrossSectionLinkrg/opentrafficsim/road/network/lane/CrossSectionLink.html#CrossSectionLink">CrossSectionLink) connectedLink), ((CrossSectionLink) link)
307                                             .getDemandWeight() / served);
308                                         viaNodes.put((CrossSectionLink) connectedLink, connectedNode);
309                                     }
310                                     setDirectedLanePosition((CrossSectionLink) connectedLink, connectedNode, positionSet);
311                                 }
312                             }
313                         }
314                     }
315                     else if (link instanceof CrossSectionLink)
316                     {
317                         setDirectedLanePosition((CrossSectionLink) link, origin, positionSet);
318                     }
319                 }
320                 initialPositions.put(rootNode, positionSet);
321             }
322 
323             // Step 3: create generator(s)
324             initialPositions = sortByValue(initialPositions); // sorts by lateral position at link start
325             Map<Node, Integer> originGeneratorCounts = new LinkedHashMap<>();
326             for (DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root : initialPositions.keySet())
327             {
328                 Set<DirectedLanePosition> initialPosition = initialPositions.get(root);
329                 // id
330                 Node o = root.getObject();
331                 String id = o.getId();
332                 if (laneBased)
333                 {
334                     Integer count = originGeneratorCounts.get(o);
335                     if (count == null)
336                     {
337                         count = 0;
338                     }
339                     count++;
340                     id += count;
341                     originGeneratorCounts.put(o, count);
342                 }
343                 // functional generation elements
344                 Lane lane;
345                 LinkType linkType;
346                 if (laneBased)
347                 {
348                     lane = initialPosition.iterator().next().getLane();
349                     linkType = lane.getParentLink().getLinkType();
350                 }
351                 else
352                 {
353                     lane = null;
354                     linkType = getLinkTypeFromNode(o);
355                 }
356                 HeadwayDistribution randomization = odOptions.get(ODOptions.HEADWAY_DIST, lane, o, linkType);
357                 ArrivalsHeadwayGeneratorvalsHeadwayGenerator.html#ArrivalsHeadwayGenerator">ArrivalsHeadwayGenerator headwayGenerator = new ArrivalsHeadwayGenerator(root, simulator, stream,
358                     randomization);
359                 GTUCharacteristicsGeneratorODWrapper characteristicsGenerator = new GTUCharacteristicsGeneratorODWrapper(
360                     root, simulator, odOptions.get(ODOptions.GTU_TYPE, lane, o, linkType), stream);
361                 RoomChecker roomChecker = odOptions.get(ODOptions.ROOM_CHECKER, lane, o, linkType);
362                 IdGenerator idGenerator = odOptions.get(ODOptions.GTU_ID, lane, o, linkType);
363                 LaneBiases biases = odOptions.get(ODOptions.getLaneBiasOption(network), lane, o, linkType);
364                 // and finally, the generator
365                 try
366                 {
367                     LaneBasedGTUGeneratorneBasedGTUGenerator.html#LaneBasedGTUGenerator">LaneBasedGTUGenerator generator = new LaneBasedGTUGenerator(id, headwayGenerator,
368                         characteristicsGenerator, GeneratorPositions.create(initialPosition, stream, biases, linkWeights,
369                             viaNodes), network, simulator, roomChecker, idGenerator);
370                     generator.setNoLaneChangeDistance(odOptions.get(ODOptions.NO_LC_DIST, lane, o, linkType));
371                     generator.setInstantaneousLaneChange(odOptions.get(ODOptions.INSTANT_LC, lane, o, linkType));
372                     generator.setErrorHandler(odOptions.get(ODOptions.ERROR_HANDLER, lane, o, linkType));
373                     output.put(id, new GeneratorObjects(generator, headwayGenerator, characteristicsGenerator));
374                 }
375                 catch (SimRuntimeException exception)
376                 {
377                     // should not happen, we check that time is 0
378                     simulator.getLogger().always().error(exception);
379                     throw new RuntimeException(exception);
380                 }
381                 catch (ProbabilityException exception)
382                 {
383                     // should not happen, as we define probabilities in the headwayGenerator
384                     simulator.getLogger().always().error(exception);
385                     throw new RuntimeException(exception);
386                 }
387             }
388         }
389         return output;
390     }
391 
392     /**
393      * Create destination sensors at all lanes connected to a destination node. This method considers connectors too.
394      * @param destination Node; destination node
395      * @param simulator OTSSimulatorInterface; simulator
396      */
397     private static void createSensorsAtDestination(final Node destination, final OTSSimulatorInterface simulator)
398     {
399         for (Link link : destination.getLinks())
400         {
401             if (link.getLinkType().isConnector() && !link.getStartNode().equals(destination))
402             {
403                 createSensorsAtDestinationNode(link.getStartNode(), simulator);
404             }
405             else
406             {
407                 createSensorsAtDestinationNode(destination, simulator);
408             }
409         }
410     }
411 
412     /**
413      * Create sensors at all lanes connected to this node. This method does not handle connectors.
414      * @param destination Node; the destination node
415      * @param simulator OTSSimulatorInterface; simulator
416      */
417     private static void createSensorsAtDestinationNode(final Node destination, final OTSSimulatorInterface simulator)
418     {
419         for (Link link : destination.getLinks())
420         {
421             if (link instanceof CrossSectionLink)
422             {
423                 for (Lane lane : ((CrossSectionLink) link).getLanes())
424                 {
425                     try
426                     {
427                         // if the lane already contains a SinkSensor, skip creating a new one
428                         boolean destinationSensorExists = false;
429                         for (Sensor sensor : lane.getSensors())
430                         {
431                             if (sensor instanceof DestinationSensor)
432                             {
433                                 destinationSensorExists = true;
434                             }
435                         }
436                         if (!destinationSensorExists)
437                         {
438                             if (link.getEndNode().equals(destination))
439                             {
440                                 new DestinationSensor(lane, lane.getLength(), GTUDirectionality.DIR_PLUS, simulator);
441                             }
442                             else if (link.getStartNode().equals(destination))
443                             {
444                                 new DestinationSensor(lane, Length.ZERO, GTUDirectionality.DIR_MINUS, simulator);
445                             }
446                         }
447                     }
448                     catch (NetworkException exception)
449                     {
450                         // can not happen, we use Length.ZERO and lane.getLength()
451                         simulator.getLogger().always().error(exception);
452                         throw new RuntimeException(exception);
453                     }
454                 }
455             }
456         }
457     }
458 
459     /**
460      * Returns the common ancestor {@code LinkType} of all links connected to the node, moving through connectors.
461      * @param node Node; origin node
462      * @return common ancestor {@code LinkType} of all links connected to the node, moving through connectors
463      */
464     private static LinkType getLinkTypeFromNode(final Node node)
465     {
466         return getLinkTypeFromNode0(node, false);
467     }
468 
469     /**
470      * Returns the common ancestor {@code LinkType} of all links connected to the node, moving through connectors.
471      * @param node Node; origin node
472      * @param ignoreConnectors boolean; ignore connectors
473      * @return common ancestor {@code LinkType} of all links connected to the node, moving through connectors
474      */
475     private static LinkType getLinkTypeFromNode0(final Node node, final boolean ignoreConnectors)
476     {
477         LinkType linkType = null;
478         for (Link link : node.getLinks())
479         {
480             LinkType next = link.getLinkType();
481             if (!ignoreConnectors && next.isConnector())
482             {
483                 Node otherNode = link.getStartNode().equals(node) ? link.getEndNode() : link.getStartNode();
484                 next = getLinkTypeFromNode0(otherNode, true);
485             }
486             if (next != null && !next.isConnector())
487             {
488                 if (linkType == null)
489                 {
490                     linkType = next;
491                 }
492                 else
493                 {
494                     linkType = linkType.commonAncestor(next);
495                     if (linkType == null)
496                     {
497                         // incompatible link types
498                         return null;
499                     }
500                 }
501             }
502         }
503         return linkType;
504     }
505 
506     /**
507      * Returns a sorted map.
508      * @param map Map&lt;K, V&gt;; input map
509      * @param <K> key type (implemented for cleaner code only)
510      * @param <V> value type (implemented for cleaner code only)
511      * @return Map; sorted map
512      */
513     private static <K, V extends Set<DirectedLanePosition>> Map<K, V> sortByValue(final Map<K, V> map)
514     {
515         return map.entrySet().stream().sorted(new Comparator<Map.Entry<K, V>>()
516         {
517             @Override
518             public int compare(final Entry<K, V> o1, final Entry<K, V> o2)
519             {
520                 DirectedLanePosition lanePos1 = o1.getValue().iterator().next();
521                 String linkId1 = lanePos1.getLane().getParentLink().getId();
522                 DirectedLanePosition lanePos2 = o2.getValue().iterator().next();
523                 String linkId2 = lanePos2.getLane().getParentLink().getId();
524                 int c = linkId1.compareToIgnoreCase(linkId2);
525                 if (c == 0)
526                 {
527                     Length pos1 = lanePos1.getGtuDirection().isPlus() ? Length.ZERO : lanePos1.getLane().getLength();
528                     Length lat1 = lanePos1.getLane().getLateralCenterPosition(pos1);
529                     Length pos2 = lanePos2.getGtuDirection().isPlus() ? Length.ZERO : lanePos2.getLane().getLength();
530                     Length lat2 = lanePos2.getLane().getLateralCenterPosition(pos2);
531                     return lat1.compareTo(lat2);
532                 }
533                 return c;
534             }
535         }).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
536     }
537 
538     /**
539      * Adds {@code DirectedLanePosition}s to the input set, for {@code Lane}s on the given link, starting at the given
540      * {@code Node}.
541      * @param link CrossSectionLink; link with lanes to add positions for
542      * @param node Node; node on the side where positions should be placed
543      * @param positionSet Set&lt;DirectedLanePosition&gt;; set to add position to
544      */
545     private static void setDirectedLanePosition(final CrossSectionLink link, final Node node,
546             final Set<DirectedLanePosition> positionSet)
547     {
548         for (Lane lane : link.getLanes())
549         {
550             // TODO should be GTU type dependent.
551             if (!lane.getParentLink().getStartNode().equals(node))
552             {
553                 return;
554                 // TODO handle lanes that ARE drivable contrary to the design direction of the link
555             }
556             try
557             {
558                 positionSet.add(lane.getParentLink().getStartNode().equals(node) ? new DirectedLanePosition(lane,
559                     Length.ZERO, GTUDirectionality.DIR_PLUS) : new DirectedLanePosition(lane, lane.getLength(),
560                         GTUDirectionality.DIR_MINUS));
561             }
562             catch (GTUException ge)
563             {
564                 link.getSimulator().getLogger().always().error(ge);
565                 throw new RuntimeException(ge);
566             }
567         }
568     }
569 
570     /**
571      * Node for demand tree. Based on two constructors there are 2 types of nodes:<br>
572      * <ul>
573      * <li>Branch nodes; with an object and a stream for randomly drawing a child node.</li>
574      * <li>Leaf nodes; with an object and demand data (time, frequency, interpolation).</li>
575      * </ul>
576      * To accomplish a branching of Node (origin) &gt; Node (destination) &gt; Category, the following generics types can be
577      * used:<br>
578      * <br>
579      * {@code DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>}
580      * <p>
581      * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
582      * <br>
583      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
584      * <p>
585      * @version $Revision$, $LastChangedDate$, by $Author$, initial version 1 dec. 2017 <br>
586      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
587      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
588      * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
589      * @param <T> type of contained object
590      * @param <K> type of child nodes
591      */
592     private static class DemandNode<T, K extends DemandNode<?, ?>> implements Arrivals
593     {
594 
595         /** Node object. */
596         private final T object;
597 
598         /** Random stream to draw child node. */
599         private final StreamInterface stream;
600 
601         /** Children. */
602         private final List<K> children = new ArrayList<>();
603 
604         /** Demand data. */
605         private final DemandPattern demandPattern;
606 
607         /** Unique GTU types of leaf nodes. */
608         private final List<GTUType> gtuTypes = new ArrayList<>();
609 
610         /** Number of leaf nodes for the unique GTU types. */
611         private final List<Integer> gtuTypeCounts = new ArrayList<>();
612 
613         /** GTU type of leaf nodes. */
614         private final Map<K, GTUType> gtuTypesPerChild = new LinkedHashMap<>();
615 
616         /** Markov chain for GTU type selection. */
617         private final MarkovChain markov;
618 
619         /**
620          * Constructor for branching node, with Markov selection.
621          * @param object T; node object
622          * @param stream StreamInterface; random stream to draw child node
623          * @param markov MarkovChain; Markov chain
624          */
625         DemandNode(final T object, final StreamInterface stream, final MarkovChain markov)
626         {
627             this.object = object;
628             this.stream = stream;
629             this.demandPattern = null;
630             this.markov = markov;
631         }
632 
633         /**
634          * Constructor for leaf node, without Markov selection.
635          * @param object T; node object
636          * @param demandPattern DemandPattern; demand data
637          */
638         DemandNode(final T object, final DemandPattern demandPattern)
639         {
640             this.object = object;
641             this.stream = null;
642             this.demandPattern = demandPattern;
643             this.markov = null;
644         }
645 
646         /**
647          * Adds child to a branching node.
648          * @param child K; child node
649          */
650         public void addChild(final K child)
651         {
652             this.children.add(child);
653         }
654 
655         /**
656          * Adds child to a branching node.
657          * @param child K; child node
658          * @param gtuType GTUType; gtu type for Markov chain
659          */
660         public void addLeaf(final K child, final GTUType gtuType)
661         {
662             Throw.when(this.gtuTypes == null, IllegalStateException.class,
663                 "Adding leaf with GTUType in not possible on a non-Markov node.");
664             addChild(child);
665             this.gtuTypesPerChild.put(child, gtuType);
666             if (!this.gtuTypes.contains(gtuType))
667             {
668                 this.gtuTypes.add(gtuType);
669                 this.gtuTypeCounts.add(1);
670             }
671             else
672             {
673                 int index = this.gtuTypes.indexOf(gtuType);
674                 this.gtuTypeCounts.set(index, this.gtuTypeCounts.get(index) + 1);
675             }
676         }
677 
678         /**
679          * Randomly draws a child node.
680          * @param time Time; simulation time
681          * @return K; randomly drawn child node
682          */
683         public K draw(final Time time)
684         {
685             Throw.when(this.children.isEmpty(), RuntimeException.class, "Calling draw on a leaf node in the demand tree.");
686             Map<K, Double> weightMap = new LinkedHashMap<>();
687             if (this.markov == null)
688             {
689                 // regular draw, loop children and collect their frequencies
690                 for (K child : this.children)
691                 {
692                     double f = child.getFrequency(time, true).si; // sliceStart = true is arbitrary
693                     weightMap.put(child, f);
694                 }
695             }
696             else
697             {
698                 // markov chain draw, the markov chain only selects a GTU type, not a child node
699                 GTUType[] gtuTypeArray = new GTUType[this.gtuTypes.size()];
700                 gtuTypeArray = this.gtuTypes.toArray(gtuTypeArray);
701                 Frequency[] steadyState = new Frequency[this.gtuTypes.size()];
702                 Arrays.fill(steadyState, Frequency.ZERO);
703                 Map<K, Frequency> frequencies = new LinkedHashMap<>(); // stored, saves us from calculating them twice
704                 for (K child : this.children)
705                 {
706                     GTUType gtuType = this.gtuTypesPerChild.get(child);
707                     int index = this.gtuTypes.indexOf(gtuType);
708                     Frequency f = child.getFrequency(time, true); // sliceStart = true is arbitrary
709                     frequencies.put(child, f);
710                     steadyState[index] = steadyState[index].plus(f);
711                 }
712                 GTUType nextGtuType = this.markov.draw(gtuTypeArray, steadyState, this.stream);
713                 // select only child nodes registered to the next GTU type
714                 for (K child : this.children)
715                 {
716                     if (this.gtuTypesPerChild.get(child).equals(nextGtuType))
717                     {
718                         double f = frequencies.get(child).si;
719                         weightMap.put(child, f);
720                     }
721                 }
722             }
723             return Draw.drawWeighted(weightMap, this.stream);
724         }
725 
726         /**
727          * Returns the node object.
728          * @return T; node object
729          */
730         public T getObject()
731         {
732             return this.object;
733         }
734 
735         /**
736          * Returns the child that pertains to specified object or {@code null} if no such child is present.
737          * @param obj Object; child object
738          * @return child that pertains to specified object or {@code null} if no such child is present
739          */
740         public K getChild(final Object obj)
741         {
742             for (K child : this.children)
743             {
744                 if (child.getObject().equals(obj))
745                 {
746                     return child;
747                 }
748             }
749             return null;
750         }
751 
752         /** {@inheritDoc} */
753         @Override
754         public Frequency getFrequency(final Time time, final boolean sliceStart)
755         {
756             if (this.demandPattern != null)
757             {
758                 return this.demandPattern.getFrequency(time, sliceStart);
759             }
760             Frequency f = new Frequency(0.0, FrequencyUnit.PER_HOUR);
761             for (K child : this.children)
762             {
763                 f = f.plus(child.getFrequency(time, sliceStart));
764             }
765             return f;
766         }
767 
768         /** {@inheritDoc} */
769         @Override
770         public Time nextTimeSlice(final Time time)
771         {
772             if (this.demandPattern != null)
773             {
774                 return this.demandPattern.nextTimeSlice(time);
775             }
776             Time out = null;
777             for (K child : this.children)
778             {
779                 Time childSlice = child.nextTimeSlice(time);
780                 out = out == null || (childSlice != null && childSlice.lt(out)) ? childSlice : out;
781             }
782             return out;
783         }
784 
785         /** {@inheritDoc} */
786         @Override
787         public String toString()
788         {
789             return "DemandNode [object=" + this.object + ", stream=" + this.stream + ", children=" + this.children
790                 + ", demandPattern=" + this.demandPattern + ", gtuTypes=" + this.gtuTypes + ", gtuTypeCounts="
791                 + this.gtuTypeCounts + ", gtuTypesPerChild=" + this.gtuTypesPerChild + ", markov=" + this.markov + "]";
792         }
793 
794     }
795 
796     /**
797      * Wrapper class around a {@code MarkovCorrelation}, including the last type. One of these should be used for each vehicle
798      * generator.
799      */
800     private static class MarkovChain
801     {
802         /** Markov correlation for GTU type selection. */
803         private final MarkovCorrelation<GTUType, Frequency> markov;
804 
805         /** Previously returned GTU type. */
806         private GTUType previousGtuType = null;
807 
808         /**
809          * Constructor.
810          * @param markov MarkovCorrelation&lt;GTUType, Frequency&gt;; Markov correlation for GTU type selection
811          */
812         MarkovChain(final MarkovCorrelation<GTUType, Frequency> markov)
813         {
814             this.markov = markov;
815         }
816 
817         /**
818          * Returns a next GTU type drawn using a Markov chain.
819          * @param gtuTypes GTUType[]; GTUTypes to consider
820          * @param intensities Frequency[]; frequency for each GTU type, i.e. the steady-state
821          * @param stream StreamInterface; stream for random numbers
822          * @return next GTU type drawn using a Markov chain
823          */
824         public GTUType draw(final GTUType[] gtuTypes, final Frequency[] intensities, final StreamInterface stream)
825         {
826             this.previousGtuType = this.markov.drawState(this.previousGtuType, gtuTypes, intensities, stream);
827             return this.previousGtuType;
828         }
829     }
830 
831     /**
832      * Characteristics generation based on OD demand.
833      * <p>
834      * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
835      * <br>
836      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
837      * <p>
838      * @version $Revision$, $LastChangedDate$, by $Author$, initial version 7 dec. 2017 <br>
839      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
840      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
841      * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
842      */
843     private static class GTUCharacteristicsGeneratorODWrapper implements LaneBasedGTUCharacteristicsGenerator
844     {
845 
846         /** Root node with origin. */
847         private final DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root;
848 
849         /** Simulator. */
850         private final DEVSSimulatorInterface.TimeDoubleUnit simulator;
851 
852         /** Characteristics generator based on OD information. */
853         private final GTUCharacteristicsGeneratorOD characteristicsGenerator;
854 
855         /** Stream for random numbers. */
856         private final StreamInterface randomStream;
857 
858         /**
859          * @param root DemandNode&lt;Node, DemandNode&lt;Node, DemandNode&lt;Category, ?&gt;&gt;&gt;; root node with origin
860          * @param simulator DEVSSimulatorInterface.TimeDoubleUnit; simulator
861          * @param characteristicsGenerator GTUCharacteristicsGeneratorOD; characteristics generator based on OD information
862          * @param randomStream StreamInterface; stream for random numbers
863          */
864         GTUCharacteristicsGeneratorODWrapper(final DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root,
865                 final DEVSSimulatorInterface.TimeDoubleUnit simulator,
866                 final GTUCharacteristicsGeneratorOD characteristicsGenerator, final StreamInterface randomStream)
867         {
868             this.root = root;
869             this.simulator = simulator;
870             this.characteristicsGenerator = characteristicsGenerator;
871             this.randomStream = randomStream;
872         }
873 
874         /** {@inheritDoc} */
875         @Override
876         public LaneBasedGTUCharacteristics draw() throws ProbabilityException, ParameterException, GTUException
877         {
878             // obtain node objects
879             Time time = this.simulator.getSimulatorTime();
880             Node origin = this.root.getObject();
881             DemandNode<Node, DemandNode<Category, ?>> destinationNode = this.root.draw(time);
882             Node destination = destinationNode.getObject();
883             Category category = destinationNode.draw(time).getObject();
884             // forward to lower-level generator
885             // XXX typically calls DefaultGTUCharacteristicsGeneratorOD.draw(...)
886             return this.characteristicsGenerator.draw(origin, destination, category, this.randomStream);
887         }
888 
889         /** {@inheritDoc} */
890         @Override
891         public String toString()
892         {
893             return "GTUCharacteristicsGeneratorODWrapper [root=" + this.root + ", simulator=" + this.simulator
894                 + ", characteristicsGenerator=" + this.characteristicsGenerator + ", randomStream=" + this.randomStream
895                 + "]";
896         }
897 
898     }
899 
900     /**
901      * Class to contain created generator objects.
902      * <p>
903      * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
904      * <br>
905      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
906      * <p>
907      * @version $Revision$, $LastChangedDate$, by $Author$, initial version 12 dec. 2017 <br>
908      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
909      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
910      * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
911      */
912     public static class GeneratorObjects
913     {
914 
915         /** Main generator for GTU's. */
916         private final LaneBasedGTUGenerator generator;
917 
918         /** Generator of headways. */
919         private final Generator<Duration> headwayGenerator;
920 
921         /** Generator of GTU characteristics. */
922         private final LaneBasedGTUCharacteristicsGenerator characteristicsGenerator;
923 
924         /**
925          * @param generator LaneBasedGTUGenerator; main generator for GTU's
926          * @param headwayGenerator Generator&lt;Duration&gt;; generator of headways
927          * @param characteristicsGenerator LaneBasedGTUCharacteristicsGenerator; generator of GTU characteristics
928          */
929         public GeneratorObjects(final LaneBasedGTUGenerator generator, final Generator<Duration> headwayGenerator,
930                 final LaneBasedGTUCharacteristicsGenerator characteristicsGenerator)
931         {
932             this.generator = generator;
933             this.headwayGenerator = headwayGenerator;
934             this.characteristicsGenerator = characteristicsGenerator;
935         }
936 
937         /**
938          * Returns the main generator for GTU's.
939          * @return LaneBasedGTUGenerator; main generator for GTU's
940          */
941         public LaneBasedGTUGenerator getGenerator()
942         {
943             return this.generator;
944         }
945 
946         /**
947          * Returns the generator of headways.
948          * @return Generator&lt;Duration&gt; generator of headways
949          */
950         public Generator<Duration> getHeadwayGenerator()
951         {
952             return this.headwayGenerator;
953         }
954 
955         /**
956          * Returns the generator of GTU characteristics.
957          * @return LaneBasedGTUCharacteristicsGenerator; generator of GTU characteristics
958          */
959         public LaneBasedGTUCharacteristicsGenerator getCharachteristicsGenerator()
960         {
961             return this.characteristicsGenerator;
962         }
963 
964     }
965 
966 }