24. Building a Simulation

Where Are We

At the end of the last lecture, we presented this lambda-expression based simulation framework:

/** Framework for discrete event simulation.
 */
public class Simulator {

    public interface Action {
        // actions contain the specific code of each event
        void trigger( double time );
    }

    private static class Event {
        public double time; // the time of this event
        public Action act; // what to do at that time
    }

    private static PriorityQueue<Event> eventSet
        = new PriorityQueue<Event> (
            (Event e1, Event e2)-> Double.compare( e1.time, e2.time )
        );

    /** Call schedule to make act happen at time.
     *  Users typically pass the action as a lambda expression:
     *  <PRE>
     *  Simulator.schedule( t, ( double time )-> method( ... time ... ) )
     *  </PRE>
     */
    static void schedule( double time, Action act ) {
        Event e = new Event();
        e.time = time;
        e.act = act;
        eventSet.add( e );
    }

    /** run the simulation.
     *  Call run() after scheduling some initial events to run the simulation.
     */
    static void run() {
        while (!eventSet.isEmpty()) {
            Event e = eventSet.remove();
            e.act.trigger( e.time );
        }
    }
}

Adding Vehicle Behavior

We have a Java program that builds an internal representation of a road network on the computer, and we have a pending event set mechanism (actually two of them), so it's time to marry the two and create a simulation of a road network.

Of course, we need to add some things to our road network to do this:

• Vehicles: Where do they come from and where do they go?

• Behavior: How do vehicles behave as they traverse a road?

Vehicle Sources and Destinations

One way to add vehicles to a highway network is to add some new classes of intersection, vehicle sources and sinks. In the real world, these might model roads coming into the highway network from the outside world and roads leaving the highway network, or they might model parking lots.

In the simulated world, vehicle sources create new vehicles out of nothing and spit them out into the road network. Similarly, vehile sinks consume any vehicle that enters them, utterly and completely destroying those vehicles.

In our model, we'll keep things simple with the following two new intersection types:

• Vehicle sources: There could be several kinds of sources with different behaviors. For example, we could have sources that behave differently depending on the time of day. Here, we'll keep things simple, sources simply inject vehicles at random times, and they are characterized by just one parameter, the median interval between vehicles. The textual description of a source intersection will look very much like the textual description of a stop light:

  interseciton X source 3.5
  

• Vehicle sinks: If we were traffic engineers, we'd make the sink intersection accumulate some kind of statistics about the life history of each vehicle as it is destroyed, but since we're just building the simulation engine, we'll ignore that. Sinks could look like this in our textual language:

  interseciton Y sink
  

Adding source intersections to the program

We need to add parsing support for source intersections. Step 1 in this venture is to just parse the details of the source and store the parameter values. This is straightforward code that is no different from the code we've already given for stop lights. The two classes begin to diverge only when we get to the simulation methods. For a source intersection, as in a stop light, the constructor schedules an event that schedules an event that schedulesd an event, for ever until the end of time. In the case of the stop light, these events are strictly periodic. In the case of source intersections, the interval between successive cars arriving into the simulation model from the most basic type of source intersection should be random. So, the repeating event code looks like this:

private void produce( double time ) {
    Simulator.schedule(
        time + period, // BUG -- need to randomize time of next production
        (double t)-> this.produce( t )
    );
    // BUG -- produce a vehicle v
    // BUG -- what is the travel time of a source intersection?
    // BUG -- pick an outgoing road r
    // BUG -- r.enter( time, v );

    System.out.println( this.toString() +": produces at t ="+ time );
}

Here, aside from bug notices, this code is still the same as the code for the stop-light, but the bug notices hint at an entirely different direction for the development of this code:

• The interval between successive events will need to be randomized.
• We need to figure out how to produce vehicles. For that matter, we need to figure out if we even need to represent vehicles with any data structure at all.
• Two vehicles cannot leave the same intersection at the same time, so the travel time of a source intersection gives the minimum time between vehicle departures. How does this work?
• We need a mechanism to decide, for each vehicle, which outgoing road to take from the source intersection.

As we will see later, some of these problems apply to all intersections. We need to further develop the model to fully appreciate this.

In contrast, the Sink subclass of Intersection is relatively easy. We won't give the code here to parse vehicle sinks, and we note that sinks simply consume vehicles and discard them. In a fully developed model, the sink could also gather statistics, but we won't do that here.