OdApplier.java

  1. package org.opentrafficsim.road.od;

  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.Comparator;
  5. import java.util.LinkedHashMap;
  6. import java.util.LinkedHashSet;
  7. import java.util.List;
  8. import java.util.Map;
  9. import java.util.Map.Entry;
  10. import java.util.Set;
  11. import java.util.stream.Collectors;

  12. import org.djunits.unit.FrequencyUnit;
  13. import org.djunits.value.vdouble.scalar.Duration;
  14. import org.djunits.value.vdouble.scalar.Frequency;
  15. import org.djunits.value.vdouble.scalar.Length;
  16. import org.djunits.value.vdouble.scalar.Time;
  17. import org.djutils.exceptions.Throw;
  18. import org.opentrafficsim.base.parameters.ParameterException;
  19. import org.opentrafficsim.core.distributions.Generator;
  20. import org.opentrafficsim.core.dsol.OtsSimulatorInterface;
  21. import org.opentrafficsim.core.gtu.GtuException;
  22. import org.opentrafficsim.core.gtu.GtuType;
  23. import org.opentrafficsim.core.idgenerator.IdGenerator;
  24. import org.opentrafficsim.core.math.Draw;
  25. import org.opentrafficsim.core.network.Connector;
  26. import org.opentrafficsim.core.network.Link;
  27. import org.opentrafficsim.core.network.LinkType;
  28. import org.opentrafficsim.core.network.NetworkException;
  29. import org.opentrafficsim.core.network.Node;
  30. import org.opentrafficsim.core.object.DetectorType;
  31. import org.opentrafficsim.road.gtu.generator.GeneratorPositions;
  32. import org.opentrafficsim.road.gtu.generator.GeneratorPositions.LaneBiases;
  33. import org.opentrafficsim.road.gtu.generator.LaneBasedGtuGenerator;
  34. import org.opentrafficsim.road.gtu.generator.LaneBasedGtuGenerator.RoomChecker;
  35. import org.opentrafficsim.road.gtu.generator.MarkovCorrelation;
  36. import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGtuCharacteristics;
  37. import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGtuCharacteristicsGenerator;
  38. import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGtuCharacteristicsGeneratorOd;
  39. import org.opentrafficsim.road.gtu.generator.headway.Arrivals;
  40. import org.opentrafficsim.road.gtu.generator.headway.ArrivalsHeadwayGenerator;
  41. import org.opentrafficsim.road.gtu.generator.headway.ArrivalsHeadwayGenerator.HeadwayDistribution;
  42. import org.opentrafficsim.road.gtu.generator.headway.DemandPattern;
  43. import org.opentrafficsim.road.network.RoadNetwork;
  44. import org.opentrafficsim.road.network.lane.CrossSectionLink;
  45. import org.opentrafficsim.road.network.lane.Lane;
  46. import org.opentrafficsim.road.network.lane.LanePosition;
  47. import org.opentrafficsim.road.network.lane.object.detector.LaneDetector;
  48. import org.opentrafficsim.road.network.lane.object.detector.SinkDetector;

  49. import nl.tudelft.simulation.dsol.SimRuntimeException;
  50. import nl.tudelft.simulation.jstats.streams.MersenneTwister;
  51. import nl.tudelft.simulation.jstats.streams.StreamInterface;

  52. /**
  53.  * Utility to create vehicle generators on a network from an OD.
  54.  * <p>
  55.  * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
  56.  * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  57.  * </p>
  58.  * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  59.  * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
  60.  * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  61.  */
  62. public final class OdApplier
  63. {

  64.     /**
  65.      * Utility class.
  66.      */
  67.     private OdApplier()
  68.     {
  69.         //
  70.     }

  71.     /**
  72.      * Applies the OD to the network by creating vehicle generators. The map returned contains objects created for vehicle
  73.      * generation. These are bundled in a {@code GeneratorObjects} and mapped to the vehicle generator id. Vehicle generator id
  74.      * is equal to the origin node id. For lane-based generators the id's are appended with an ordered number (e.g. A1), where
  75.      * the ordering is first by link id, and then right to left concerning the lateral lane position at the start of the lane.
  76.      * For node "A" this would for example be:<br>
  77.      * <table >
  78.      * <caption>&nbsp;</caption>
  79.      * <tr>
  80.      * <th>Generator id</th>
  81.      * <th>Link</th>
  82.      * <th>Lateral start offset</th>
  83.      * </tr>
  84.      * <tr>
  85.      * <th>A1</th>
  86.      * <th>AB</th>
  87.      * <th>-1.75m</th>
  88.      * </tr>
  89.      * <tr>
  90.      * <th>A2</th>
  91.      * <th>AB</th>
  92.      * <th>1.75m</th>
  93.      * </tr>
  94.      * <tr>
  95.      * <th>A3</th>
  96.      * <th>AC</th>
  97.      * <th>-3.5m</th>
  98.      * </tr>
  99.      * <tr>
  100.      * <th>A4</th>
  101.      * <th>AC</th>
  102.      * <th>0.0m</th>
  103.      * </tr>
  104.      * </table>
  105.      * If the GTU generation is lane-based (i.e. {@code Lane} in the {@code Categorization}) this method creates a
  106.      * {@code LaneBasedGtuGenerator} per lane. It will have a single source of demand data, specifying demand towards all
  107.      * relevant destinations, and with a unique {@code MarkovChain} for the GTU type if {@code MarkovCorrelation} is defined.
  108.      * For zone GTU generation one {@code LaneBasedGtuGenerator} is created, with one single source of demand data, specifying
  109.      * demand towards all destinations. A single {@code MarkovChain} may be used. Traffic is distributed over possible
  110.      * {@code Connectors} based on their link-weight, or the number of lanes of the connected links if no weight is given.
  111.      * @param network network
  112.      * @param od OD matrix
  113.      * @param odOptions options for vehicle generation
  114.      * @param detectorType detector type.
  115.      * @return Map&lt;String, GeneratorObjects&gt; map of generator id's and created generator objects mainly for testing
  116.      * @throws ParameterException if a parameter is missing
  117.      * @throws SimRuntimeException if this method is called after simulation time 0
  118.      */
  119.     @SuppressWarnings("checkstyle:methodlength")
  120.     public static Map<String, GeneratorObjects> applyOd(final RoadNetwork network, final OdMatrix od, final OdOptions odOptions,
  121.             final DetectorType detectorType) throws ParameterException, SimRuntimeException
  122.     {
  123.         Throw.whenNull(network, "Network may not be null.");
  124.         Throw.whenNull(od, "OD matrix may not be null.");
  125.         Throw.whenNull(odOptions, "OD options may not be null.");
  126.         OtsSimulatorInterface simulator = network.getSimulator();
  127.         Throw.when(!simulator.getSimulatorTime().eq0(), SimRuntimeException.class,
  128.                 "Method OdApplier.applyOd() should be invoked at simulation time 0.");

  129.         // TODO sinks? white extension links?
  130.         for (Node destination : od.getDestinations())
  131.         {
  132.             createSensorsAtDestination(destination, detectorType);
  133.         }

  134.         // TODO clean up stream acquiring code after task OTS-315 has been completed
  135.         StreamInterface stream = getStream(simulator);

  136.         boolean laneBased = od.getCategorization().entails(Lane.class);
  137.         Map<String, GeneratorObjects> output = new LinkedHashMap<>();
  138.         for (Node origin : od.getOrigins())
  139.         {
  140.             Map<Lane, DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>> originNodePerLane = new LinkedHashMap<>();
  141.             DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> originNodeZone =
  142.                     buildDemandNodeTree(od, odOptions, stream, origin, originNodePerLane);
  143.             Map<DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>, Set<LanePosition>> initialPositions =
  144.                     new LinkedHashMap<>();
  145.             Map<CrossSectionLink, Double> linkWeights = new LinkedHashMap<>();
  146.             Map<CrossSectionLink, Node> viaNodes = new LinkedHashMap<>();
  147.             if (laneBased)
  148.             {
  149.                 gatherPositionsLaneBased(originNodePerLane, initialPositions);
  150.             }
  151.             else
  152.             {
  153.                 initialPositions.put(originNodeZone, gatherPositionsZone(origin, linkWeights, viaNodes));
  154.             }
  155.             if (linkWeights.isEmpty())
  156.             {
  157.                 linkWeights = null;
  158.                 viaNodes = null;
  159.             }
  160.             initialPositions = sortByValue(initialPositions); // sorts by lateral position at link start
  161.             createGenerators(network, odOptions, simulator, laneBased, stream, output, initialPositions, linkWeights, viaNodes);
  162.         }
  163.         return output;
  164.     }

  165.     /**
  166.      * Builds nested demand node structure (i.e. tree) for demand and GTU characteristics generation. If
  167.      * {@code MarkovCorrelation} is specified, in case of zone GTU generation, a single {@code MarkovChain} is used for the
  168.      * selection of GTU type and the relevant lane. In case of lane-based GTU generation, one {@code MarkovChain} is used for
  169.      * each lane, even when multiple {@code Category}'s contain the same lane. This method loops over all destinations for the
  170.      * given origin, and then over all categories. For lane-based GTU generation, at that level the appropriate origin node is
  171.      * taken from the input map, or it is created in to it, and the destination demand-node coupled to that for the looped
  172.      * destination is obtained or created, with possible {@code MarkovChain}. For zone GTU generation, the looping is a more
  173.      * straight-forward creation of nodes from origin, and for destination and category. The result of lane-based GTU generation
  174.      * is given in the input map, for zone GTU generation the single origin demand node is returned by the method.
  175.      * @param od OD matrix.
  176.      * @param odOptions OD options.
  177.      * @param stream random number stream.
  178.      * @param origin origin node.
  179.      * @param originNodePerLane map of origin demand node per lane, populated for lane-based GTU generation.
  180.      * @return demand node structure for the entire generator in case of zone GTU generation.
  181.      */
  182.     private static DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> buildDemandNodeTree(final OdMatrix od,
  183.             final OdOptions odOptions, final StreamInterface stream, final Node origin,
  184.             final Map<Lane, DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>> originNodePerLane)
  185.     {
  186.         boolean laneBased = od.getCategorization().entails(Lane.class);
  187.         boolean markovian = od.getCategorization().entails(GtuType.class);
  188.         DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> demandNode = null; // for each generator, flexibly used
  189.         MarkovChain markovChain = null;
  190.         if (!laneBased)
  191.         {
  192.             demandNode = new DemandNode<>(origin, stream, null);
  193.             LinkType linkType = getLinkTypeFromNode(origin);
  194.             if (markovian)
  195.             {
  196.                 MarkovCorrelation<GtuType, Frequency> correlation = odOptions.get(OdOptions.MARKOV, null, origin, linkType);
  197.                 if (correlation != null)
  198.                 {
  199.                     Throw.when(!od.getCategorization().entails(GtuType.class), IllegalArgumentException.class,
  200.                             "Markov correlation can only be used on OD categorization entailing GTU type.");
  201.                     markovChain = new MarkovChain(correlation);
  202.                 }
  203.             }
  204.         }
  205.         for (Node destination : od.getDestinations())
  206.         {
  207.             Set<Category> categories = od.getCategories(origin, destination);
  208.             if (!categories.isEmpty())
  209.             {
  210.                 DemandNode<Node, DemandNode<Category, ?>> destinationNode = null;
  211.                 if (!laneBased)
  212.                 {
  213.                     destinationNode = new DemandNode<>(destination, stream, markovChain);
  214.                     demandNode.addChild(destinationNode);
  215.                 }
  216.                 for (Category category : categories)
  217.                 {
  218.                     if (laneBased)
  219.                     {
  220.                         // obtain or create root and destination nodes
  221.                         Lane lane = category.get(Lane.class);
  222.                         demandNode = originNodePerLane.get(lane);
  223.                         if (demandNode == null)
  224.                         {
  225.                             demandNode = new DemandNode<>(origin, stream, null);
  226.                             originNodePerLane.put(lane, demandNode);
  227.                         }
  228.                         destinationNode = demandNode.getChild(destination);
  229.                         if (destinationNode == null)
  230.                         {
  231.                             markovChain = null;
  232.                             if (markovian)
  233.                             {
  234.                                 MarkovCorrelation<GtuType, Frequency> correlation =
  235.                                         odOptions.get(OdOptions.MARKOV, lane, origin, lane.getLink().getType());
  236.                                 if (correlation != null)
  237.                                 {
  238.                                     Throw.when(!od.getCategorization().entails(GtuType.class), IllegalArgumentException.class,
  239.                                             "Markov correlation can only be used on OD categorization entailing GTU type.");
  240.                                     markovChain = new MarkovChain(correlation); // 1 for each generator per lane
  241.                                 }
  242.                             }
  243.                             destinationNode = new DemandNode<>(destination, stream, markovChain);
  244.                             demandNode.addChild(destinationNode);
  245.                         }
  246.                     }
  247.                     DemandNode<Category, ?> categoryNode =
  248.                             new DemandNode<>(category, od.getDemandPattern(origin, destination, category));
  249.                     if (markovian)
  250.                     {
  251.                         destinationNode.addLeaf(categoryNode, category.get(GtuType.class));
  252.                     }
  253.                     else
  254.                     {
  255.                         destinationNode.addChild(categoryNode);
  256.                     }
  257.                 }
  258.             }
  259.         }
  260.         return demandNode;
  261.     }

  262.     /**
  263.      * Returns a set of positions for GTU generation from each lane defined in demand. Stores the positions with the coupled
  264.      * demand node.
  265.      * @param originNodePerLane map with a demand node per lane.
  266.      * @param initialPositions Map&lt;DemandNode&lt;Node, DemandNode&lt;Node, DemandNode&lt;Category, ?&gt;&gt;&gt;,
  267.      *            Set&lt;LanePosition&gt;&gt;; map with positions per demand node.
  268.      */
  269.     private static void gatherPositionsLaneBased(
  270.             final Map<Lane, DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>> originNodePerLane,
  271.             final Map<DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>, Set<LanePosition>> initialPositions)
  272.     {
  273.         for (Lane lane : originNodePerLane.keySet())
  274.         {
  275.             DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> demandNode = originNodePerLane.get(lane);
  276.             Set<LanePosition> initialPosition = new LinkedHashSet<>();
  277.             initialPosition.add(lane.getLink().getStartNode().equals(demandNode.getObject())
  278.                     ? new LanePosition(lane, Length.ZERO) : new LanePosition(lane, lane.getLength()));
  279.             initialPositions.put(demandNode, initialPosition);
  280.         }
  281.     }

  282.     /**
  283.      * Returns a set of positions for GTU generation from a zone. All links connected to the origin node are considered. In case
  284.      * a link is a {@code Connector}, a link weight and via-node over that link are stored in the provided maps, for later use
  285.      * in constructing weighted generator positions. For each {@code CrossSectionLink} attached to the via-node, or to the first
  286.      * link if there was no {@code Connector}, positions are generated.
  287.      * @param origin origin node for the zone.
  288.      * @param linkWeights link weight map to place link weights in.
  289.      * @param viaNodes via node map to place via nodes in.
  290.      * @return gathered lane positions.
  291.      */
  292.     private static Set<LanePosition> gatherPositionsZone(final Node origin, final Map<CrossSectionLink, Double> linkWeights,
  293.             final Map<CrossSectionLink, Node> viaNodes)
  294.     {
  295.         Set<LanePosition> positionSet = new LinkedHashSet<>();
  296.         for (Link link : origin.getLinks())
  297.         {
  298.             if (link instanceof Connector)
  299.             {
  300.                 Connector connector = (Connector) link;
  301.                 if (connector.getStartNode().equals(origin))
  302.                 {
  303.                     Node connectedNode = connector.getEndNode();
  304.                     // count number of served links
  305.                     int served = 0;
  306.                     for (Link connectedLink : connectedNode.getLinks())
  307.                     {
  308.                         if (connectedLink instanceof CrossSectionLink)
  309.                         {
  310.                             served++;
  311.                         }
  312.                     }
  313.                     for (Link connectedLink : connectedNode.getLinks())
  314.                     {
  315.                         if (connectedLink instanceof CrossSectionLink)
  316.                         {
  317.                             if (connector.getDemandWeight() > 0.0)
  318.                             {
  319.                                 // store weight under connected link, as this
  320.                                 linkWeights.put(((CrossSectionLink) connectedLink), connector.getDemandWeight() / served);
  321.                             }
  322.                             else
  323.                             {
  324.                                 // negative weight results in number of lanes being used
  325.                                 linkWeights.put(((CrossSectionLink) connectedLink), -1.0);
  326.                             }
  327.                             viaNodes.put((CrossSectionLink) connectedLink, connectedNode);
  328.                             setLanePosition((CrossSectionLink) connectedLink, connectedNode, positionSet);
  329.                         }
  330.                     }
  331.                 }
  332.             }
  333.             else if (link instanceof CrossSectionLink)
  334.             {
  335.                 setLanePosition((CrossSectionLink) link, origin, positionSet);
  336.             }
  337.         }
  338.         return positionSet;
  339.     }

  340.     /**
  341.      * Creates GTU generators. For lane-based GTU generation (i.e. {@code Lane} in the {@code Categorization}), the generators
  342.      * will obtain an ID with the node id plus a counter. For this the initial positions need to be sorted. The link weights and
  343.      * via nodes should be {@code null} for lane-based GTU generation. Furthermore, the lane is then used to obtain OD option
  344.      * values possibly specified at the lane level. Other than that, for either lane-based or zone GTU generation, a
  345.      * {@code LaneBasedGtuGenerator} is created for each initial position given.
  346.      * @param network network.
  347.      * @param odOptions od options.
  348.      * @param simulator simulator.
  349.      * @param laneBased lane in category.
  350.      * @param stream random number stream.
  351.      * @param output map that output elements will be stored in.
  352.      * @param initialPositions Map&lt;DemandNode&lt;Node, DemandNode&lt;Node, DemandNode&lt;Category, ?&gt;&gt;&gt;,
  353.      *            Set&lt;LanePosition&gt;&gt;; sorted initial positions.
  354.      * @param linkWeights weights per link, may be {@code null}.
  355.      * @param viaNodes nodes to select from for zone, may be {@code null}.
  356.      * @throws ParameterException if drawing from the inter-arrival generator fails
  357.      */
  358.     @SuppressWarnings("checkstyle:parameternumber")
  359.     private static void createGenerators(final RoadNetwork network, final OdOptions odOptions,
  360.             final OtsSimulatorInterface simulator, final boolean laneBased, final StreamInterface stream,
  361.             final Map<String, GeneratorObjects> output,
  362.             final Map<DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>, Set<LanePosition>> initialPositions,
  363.             final Map<CrossSectionLink, Double> linkWeights, final Map<CrossSectionLink, Node> viaNodes)
  364.             throws ParameterException
  365.     {
  366.         Map<Node, Integer> laneGeneratorCounterForUniqueId = new LinkedHashMap<>();
  367.         for (DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root : initialPositions.keySet())
  368.         {
  369.             Set<LanePosition> initialPosition = initialPositions.get(root);
  370.             // id
  371.             Node o = root.getObject();
  372.             String id = o.getId();
  373.             if (laneBased)
  374.             {
  375.                 Integer count = laneGeneratorCounterForUniqueId.get(o);
  376.                 if (count == null)
  377.                 {
  378.                     count = 0;
  379.                 }
  380.                 count++;
  381.                 id += count;
  382.                 laneGeneratorCounterForUniqueId.put(o, count);
  383.             }
  384.             // functional generation elements
  385.             Lane lane;
  386.             LinkType linkType;
  387.             if (laneBased)
  388.             {
  389.                 lane = initialPosition.iterator().next().lane();
  390.                 linkType = lane.getLink().getType();
  391.             }
  392.             else
  393.             {
  394.                 lane = null;
  395.                 linkType = getLinkTypeFromNode(o);
  396.             }
  397.             HeadwayDistribution randomization = odOptions.get(OdOptions.HEADWAY_DIST, lane, o, linkType);
  398.             ArrivalsHeadwayGenerator headwayGenerator = new ArrivalsHeadwayGenerator(root, simulator, stream, randomization);
  399.             LaneBasedGtuCharacteristicsGeneratorOd characteristicsGeneratorOd =
  400.                     odOptions.get(OdOptions.GTU_TYPE, lane, o, linkType);
  401.             LaneBasedGtuCharacteristicsGenerator characteristicsGenerator = new LaneBasedGtuCharacteristicsGenerator()
  402.             {
  403.                 @Override
  404.                 public LaneBasedGtuCharacteristics draw() throws ParameterException, GtuException
  405.                 {
  406.                     Time time = simulator.getSimulatorAbsTime();
  407.                     Node origin = root.getObject();
  408.                     DemandNode<Node, DemandNode<Category, ?>> destinationNode = root.draw(time);
  409.                     Node destination = destinationNode.getObject();
  410.                     Category category = destinationNode.draw(time).getObject();
  411.                     return characteristicsGeneratorOd.draw(origin, destination, category, stream);
  412.                 }
  413.             };

  414.             RoomChecker roomChecker = odOptions.get(OdOptions.ROOM_CHECKER, lane, o, linkType);
  415.             IdGenerator idGenerator = odOptions.get(OdOptions.GTU_ID, lane, o, linkType);
  416.             LaneBiases biases = odOptions.get(OdOptions.LANE_BIAS, lane, o, linkType);
  417.             // and finally, the generator
  418.             try
  419.             {
  420.                 LaneBasedGtuGenerator generator = new LaneBasedGtuGenerator(id, headwayGenerator, characteristicsGenerator,
  421.                         GeneratorPositions.create(initialPosition, stream, biases, linkWeights, viaNodes), network, simulator,
  422.                         roomChecker, idGenerator);
  423.                 generator.setNoLaneChangeDistance(odOptions.get(OdOptions.NO_LC_DIST, lane, o, linkType));
  424.                 generator.setInstantaneousLaneChange(odOptions.get(OdOptions.INSTANT_LC, lane, o, linkType));
  425.                 generator.setErrorHandler(odOptions.get(OdOptions.ERROR_HANDLER, lane, o, linkType));
  426.                 output.put(id, new GeneratorObjects(generator, headwayGenerator, characteristicsGenerator));
  427.             }
  428.             catch (SimRuntimeException exception)
  429.             {
  430.                 // should not happen, we check that time is 0
  431.                 simulator.getLogger().always().error(exception);
  432.                 throw new RuntimeException(exception);
  433.             }
  434.             catch (NetworkException exception)
  435.             {
  436.                 // should not happen, as unique ids are guaranteed by UUID
  437.                 simulator.getLogger().always().error(exception);
  438.                 throw new RuntimeException(exception);
  439.             }
  440.         }
  441.     }

  442.     /**
  443.      * Obtains a stream for vehicle generation.
  444.      * @param simulator simulator.
  445.      * @return stream for vehicle generation.
  446.      */
  447.     private static StreamInterface getStream(final OtsSimulatorInterface simulator)
  448.     {
  449.         StreamInterface stream = simulator.getModel().getStream("generation");
  450.         if (stream == null)
  451.         {
  452.             stream = simulator.getModel().getStream("default");
  453.             if (stream == null)
  454.             {
  455.                 System.out
  456.                         .println("Using locally created stream (not from the simulator) for vehicle generation, with seed 1.");
  457.                 stream = new MersenneTwister(1L);
  458.             }
  459.             else
  460.             {
  461.                 System.out.println("Using stream 'default' for vehicle generation.");
  462.             }
  463.         }
  464.         return stream;
  465.     }

  466.     /**
  467.      * Create destination sensors at all lanes connected to a destination node. This method considers connectors too.
  468.      * @param destination destination node
  469.      * @param detectorType detector type.
  470.      */
  471.     private static void createSensorsAtDestination(final Node destination, final DetectorType detectorType)
  472.     {
  473.         for (Link link : destination.getLinks())
  474.         {
  475.             if (link.isConnector() && !link.getStartNode().equals(destination))
  476.             {
  477.                 createSensorsAtDestinationNode(link.getStartNode(), detectorType);
  478.             }
  479.             else
  480.             {
  481.                 createSensorsAtDestinationNode(destination, detectorType);
  482.             }
  483.         }
  484.     }

  485.     /**
  486.      * Create sensors at all lanes connected to this node. This method does not handle connectors.
  487.      * @param destination the destination node
  488.      * @param detectorType detector type.
  489.      */
  490.     private static void createSensorsAtDestinationNode(final Node destination, final DetectorType detectorType)
  491.     {
  492.         for (Link link : destination.getLinks())
  493.         {
  494.             if (link instanceof CrossSectionLink)
  495.             {
  496.                 for (Lane lane : ((CrossSectionLink) link).getLanes())
  497.                 {
  498.                     try
  499.                     {
  500.                         // if the lane already contains a SinkDetector, skip creating a new one
  501.                         boolean destinationDetectorExists = false;
  502.                         for (LaneDetector detector : lane.getDetectors())
  503.                         {
  504.                             if (detector instanceof SinkDetector)
  505.                             {
  506.                                 destinationDetectorExists = true;
  507.                             }
  508.                         }
  509.                         if (!destinationDetectorExists)
  510.                         {
  511.                             new SinkDetector(lane, lane.getLength(), detectorType, SinkDetector.DESTINATION);
  512.                         }
  513.                     }
  514.                     catch (NetworkException exception)
  515.                     {
  516.                         // can not happen, we use Length.ZERO and lane.getLength()
  517.                         destination.getNetwork().getSimulator().getLogger().always().error(exception);
  518.                         throw new RuntimeException(exception);
  519.                     }
  520.                 }
  521.             }
  522.         }
  523.     }

  524.     /**
  525.      * Returns the common ancestor {@code LinkType} of all links connected to the node, moving through connectors.
  526.      * @param node origin node
  527.      * @return common ancestor {@code LinkType} of all links connected to the node, moving through connectors
  528.      */
  529.     private static LinkType getLinkTypeFromNode(final Node node)
  530.     {
  531.         return getLinkTypeFromNode0(node, false);
  532.     }

  533.     /**
  534.      * Returns the common ancestor {@code LinkType} of all links connected to the node, moving through connectors.
  535.      * @param node origin node
  536.      * @param ignoreConnectors ignore connectors
  537.      * @return common ancestor {@code LinkType} of all links connected to the node, moving through connectors
  538.      */
  539.     private static LinkType getLinkTypeFromNode0(final Node node, final boolean ignoreConnectors)
  540.     {
  541.         LinkType linkType = null;
  542.         for (Link link : node.getLinks())
  543.         {
  544.             LinkType next = link.getType();
  545.             if (!ignoreConnectors && link.isConnector())
  546.             {
  547.                 Node otherNode = link.getStartNode().equals(node) ? link.getEndNode() : link.getStartNode();
  548.                 next = getLinkTypeFromNode0(otherNode, true);
  549.             }
  550.             if (next != null && !link.isConnector())
  551.             {
  552.                 if (linkType == null)
  553.                 {
  554.                     linkType = next;
  555.                 }
  556.                 else
  557.                 {
  558.                     linkType = linkType.commonAncestor(next);
  559.                     if (linkType == null)
  560.                     {
  561.                         // incompatible link types
  562.                         return null;
  563.                     }
  564.                 }
  565.             }
  566.         }
  567.         return linkType;
  568.     }

  569.     /**
  570.      * Returns a sorted map.
  571.      * @param map input map
  572.      * @param <K> key type (implemented for cleaner code only)
  573.      * @param <V> value type (implemented for cleaner code only)
  574.      * @return sorted map
  575.      */
  576.     private static <K, V extends Set<LanePosition>> Map<K, V> sortByValue(final Map<K, V> map)
  577.     {
  578.         return map.entrySet().stream().sorted(new Comparator<Map.Entry<K, V>>()
  579.         {
  580.             @Override
  581.             public int compare(final Entry<K, V> o1, final Entry<K, V> o2)
  582.             {
  583.                 LanePosition lanePos1 = o1.getValue().iterator().next();
  584.                 String linkId1 = lanePos1.lane().getLink().getId();
  585.                 LanePosition lanePos2 = o2.getValue().iterator().next();
  586.                 String linkId2 = lanePos2.lane().getLink().getId();
  587.                 int c = linkId1.compareToIgnoreCase(linkId2);
  588.                 if (c == 0)
  589.                 {
  590.                     Length pos1 = Length.ZERO;
  591.                     Length lat1 = lanePos1.lane().getLateralCenterPosition(pos1);
  592.                     Length pos2 = Length.ZERO;
  593.                     Length lat2 = lanePos2.lane().getLateralCenterPosition(pos2);
  594.                     return lat1.compareTo(lat2);
  595.                 }
  596.                 return c;
  597.             }
  598.         }).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
  599.     }

  600.     /**
  601.      * Adds {@code LanePosition}s to the input set, for {@code Lane}s on the given link, starting at the given {@code Node}.
  602.      * @param link link with lanes to add positions for
  603.      * @param node node on the side where positions should be placed
  604.      * @param positionSet set to add position to
  605.      */
  606.     private static void setLanePosition(final CrossSectionLink link, final Node node, final Set<LanePosition> positionSet)
  607.     {
  608.         for (Lane lane : link.getLanes())
  609.         {
  610.             // TODO should be GTU type dependent.
  611.             if (lane.getLink().getStartNode().equals(node))
  612.             {
  613.                 positionSet.add(new LanePosition(lane, Length.ZERO));
  614.             }
  615.         }
  616.     }

  617.     /**
  618.      * Node for demand tree. Based on two constructors there are 2 types of nodes:<br>
  619.      * <ul>
  620.      * <li>Branch nodes; with an object and a stream for randomly drawing a child node.</li>
  621.      * <li>Leaf nodes; with an object and demand data (time, frequency, interpolation).</li>
  622.      * </ul>
  623.      * To accomplish a branching of Node (origin) &gt; Node (destination) &gt; Category, the following generics types can be
  624.      * used:<br>
  625.      * <br>
  626.      * {@code DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>}
  627.      * <p>
  628.      * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  629.      * <br>
  630.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  631.      * </p>
  632.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  633.      * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
  634.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  635.      * @param <T> type of contained object
  636.      * @param <K> type of child nodes
  637.      */
  638.     private static class DemandNode<T, K extends DemandNode<?, ?>> implements Arrivals
  639.     {

  640.         /** Node object. */
  641.         private final T object;

  642.         /** Random stream to draw child node. */
  643.         private final StreamInterface stream;

  644.         /** Children. */
  645.         private final List<K> children = new ArrayList<>();

  646.         /** Demand data. */
  647.         private final DemandPattern demandPattern;

  648.         /** Unique GTU types of leaf nodes. */
  649.         private final List<GtuType> gtuTypes = new ArrayList<>();

  650.         /** Number of leaf nodes for the unique GTU types. */
  651.         private final List<Integer> gtuTypeCounts = new ArrayList<>();

  652.         /** GTU type of leaf nodes. */
  653.         private final Map<K, GtuType> gtuTypesPerChild = new LinkedHashMap<>();

  654.         /** Markov chain for GTU type selection. */
  655.         private final MarkovChain markov;

  656.         /**
  657.          * Constructor for branching node, with Markov selection.
  658.          * @param object node object
  659.          * @param stream random stream to draw child node
  660.          * @param markov Markov chain
  661.          */
  662.         DemandNode(final T object, final StreamInterface stream, final MarkovChain markov)
  663.         {
  664.             this.object = object;
  665.             this.stream = stream;
  666.             this.demandPattern = null;
  667.             this.markov = markov;
  668.         }

  669.         /**
  670.          * Constructor for leaf node, without Markov selection.
  671.          * @param object node object
  672.          * @param demandPattern demand data
  673.          */
  674.         DemandNode(final T object, final DemandPattern demandPattern)
  675.         {
  676.             this.object = object;
  677.             this.stream = null;
  678.             this.demandPattern = demandPattern;
  679.             this.markov = null;
  680.         }

  681.         /**
  682.          * Adds child to a branching node.
  683.          * @param child child node
  684.          */
  685.         public void addChild(final K child)
  686.         {
  687.             this.children.add(child);
  688.         }

  689.         /**
  690.          * Adds child to a branching node.
  691.          * @param child child node
  692.          * @param gtuType gtu type for Markov chain
  693.          */
  694.         public void addLeaf(final K child, final GtuType gtuType)
  695.         {
  696.             Throw.when(this.gtuTypes == null, IllegalStateException.class,
  697.                     "Adding leaf with GtuType in not possible on a non-Markov node.");
  698.             addChild(child);
  699.             this.gtuTypesPerChild.put(child, gtuType);
  700.             if (!this.gtuTypes.contains(gtuType))
  701.             {
  702.                 this.gtuTypes.add(gtuType);
  703.                 this.gtuTypeCounts.add(1);
  704.             }
  705.             else
  706.             {
  707.                 int index = this.gtuTypes.indexOf(gtuType);
  708.                 this.gtuTypeCounts.set(index, this.gtuTypeCounts.get(index) + 1);
  709.             }
  710.         }

  711.         /**
  712.          * Randomly draws a child node.
  713.          * @param time simulation time
  714.          * @return randomly drawn child node
  715.          */
  716.         public K draw(final Time time)
  717.         {
  718.             Throw.when(this.children.isEmpty(), RuntimeException.class, "Calling draw on a leaf node in the demand tree.");
  719.             Map<K, Double> weightMap = new LinkedHashMap<>();
  720.             if (this.markov == null)
  721.             {
  722.                 // regular draw, loop children and collect their frequencies
  723.                 for (K child : this.children)
  724.                 {
  725.                     double f = child.getFrequency(time, true).si; // sliceStart = true is arbitrary
  726.                     weightMap.put(child, f);
  727.                 }
  728.             }
  729.             else
  730.             {
  731.                 // markov chain draw, the markov chain only selects a GTU type, not a child node
  732.                 GtuType[] gtuTypeArray = new GtuType[this.gtuTypes.size()];
  733.                 gtuTypeArray = this.gtuTypes.toArray(gtuTypeArray);
  734.                 Frequency[] steadyState = new Frequency[this.gtuTypes.size()];
  735.                 Arrays.fill(steadyState, Frequency.ZERO);
  736.                 Map<K, Frequency> frequencies = new LinkedHashMap<>(); // stored, saves us from calculating them twice
  737.                 for (K child : this.children)
  738.                 {
  739.                     GtuType gtuType = this.gtuTypesPerChild.get(child);
  740.                     int index = this.gtuTypes.indexOf(gtuType);
  741.                     Frequency f = child.getFrequency(time, true); // sliceStart = true is arbitrary
  742.                     frequencies.put(child, f);
  743.                     steadyState[index] = steadyState[index].plus(f);
  744.                 }
  745.                 GtuType nextGtuType = this.markov.draw(gtuTypeArray, steadyState, this.stream);
  746.                 // select only child nodes registered to the next GTU type
  747.                 for (K child : this.children)
  748.                 {
  749.                     if (this.gtuTypesPerChild.get(child).equals(nextGtuType))
  750.                     {
  751.                         double f = frequencies.get(child).si;
  752.                         weightMap.put(child, f);
  753.                     }
  754.                 }
  755.             }
  756.             return Draw.drawWeighted(weightMap, this.stream);
  757.         }

  758.         /**
  759.          * Returns the node object.
  760.          * @return node object
  761.          */
  762.         public T getObject()
  763.         {
  764.             return this.object;
  765.         }

  766.         /**
  767.          * Returns the child that pertains to specified object or {@code null} if no such child is present.
  768.          * @param obj child object
  769.          * @return child that pertains to specified object or {@code null} if no such child is present
  770.          */
  771.         public K getChild(final Object obj)
  772.         {
  773.             for (K child : this.children)
  774.             {
  775.                 if (child.getObject().equals(obj))
  776.                 {
  777.                     return child;
  778.                 }
  779.             }
  780.             return null;
  781.         }

  782.         @Override
  783.         public Frequency getFrequency(final Time time, final boolean sliceStart)
  784.         {
  785.             if (this.demandPattern != null)
  786.             {
  787.                 return this.demandPattern.getFrequency(time, sliceStart);
  788.             }
  789.             Frequency f = new Frequency(0.0, FrequencyUnit.PER_HOUR);
  790.             for (K child : this.children)
  791.             {
  792.                 f = f.plus(child.getFrequency(time, sliceStart));
  793.             }
  794.             return f;
  795.         }

  796.         @Override
  797.         public Time nextTimeSlice(final Time time)
  798.         {
  799.             if (this.demandPattern != null)
  800.             {
  801.                 return this.demandPattern.nextTimeSlice(time);
  802.             }
  803.             Time out = null;
  804.             for (K child : this.children)
  805.             {
  806.                 Time childSlice = child.nextTimeSlice(time);
  807.                 out = out == null || (childSlice != null && childSlice.lt(out)) ? childSlice : out;
  808.             }
  809.             return out;
  810.         }

  811.         @Override
  812.         public String toString()
  813.         {
  814.             return "DemandNode [object=" + this.object + ", stream=" + this.stream + ", children=" + this.children
  815.                     + ", demandPattern=" + this.demandPattern + ", gtuTypes=" + this.gtuTypes + ", gtuTypeCounts="
  816.                     + this.gtuTypeCounts + ", gtuTypesPerChild=" + this.gtuTypesPerChild + ", markov=" + this.markov + "]";
  817.         }

  818.     }

  819.     /**
  820.      * Wrapper class around a {@code MarkovCorrelation}, including the last type. One of these should be used for each vehicle
  821.      * generator.
  822.      */
  823.     private static class MarkovChain
  824.     {
  825.         /** Markov correlation for GTU type selection. */
  826.         private final MarkovCorrelation<GtuType, Frequency> markov;

  827.         /** Previously returned GTU type. */
  828.         private GtuType previousGtuType = null;

  829.         /**
  830.          * Constructor.
  831.          * @param markov Markov correlation for GTU type selection
  832.          */
  833.         MarkovChain(final MarkovCorrelation<GtuType, Frequency> markov)
  834.         {
  835.             this.markov = markov;
  836.         }

  837.         /**
  838.          * Returns a next GTU type drawn using a Markov chain.
  839.          * @param gtuTypes GtuTypes to consider
  840.          * @param intensities frequency for each GTU type, i.e. the steady-state
  841.          * @param stream stream for random numbers
  842.          * @return next GTU type drawn using a Markov chain
  843.          */
  844.         public GtuType draw(final GtuType[] gtuTypes, final Frequency[] intensities, final StreamInterface stream)
  845.         {
  846.             this.previousGtuType = this.markov.drawState(this.previousGtuType, gtuTypes, intensities, stream);
  847.             return this.previousGtuType;
  848.         }
  849.     }

  850.     /**
  851.      * Class to contain created generator objects.
  852.      * <p>
  853.      * Copyright (c) 2013-2024 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
  854.      * <br>
  855.      * BSD-style license. See <a href="https://opentrafficsim.org/docs/license.html">OpenTrafficSim License</a>.
  856.      * </p>
  857.      * @author <a href="https://github.com/averbraeck">Alexander Verbraeck</a>
  858.      * @author <a href="https://github.com/peter-knoppers">Peter Knoppers</a>
  859.      * @author <a href="https://github.com/wjschakel">Wouter Schakel</a>
  860.      * @param generator main generator for GTU's
  861.      * @param headwayGenerator generator of headways
  862.      * @param characteristicsGenerator generator of GTU characteristics
  863.      */
  864.     public static record GeneratorObjects(LaneBasedGtuGenerator generator, Generator<Duration> headwayGenerator,
  865.             LaneBasedGtuCharacteristicsGenerator characteristicsGenerator)
  866.     {
  867.     }

  868. }