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