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