19. More simulation: stop lights

Stoplights

Adding stop lights to the model adds complexity we have ignored up to this point. With uncontrolled intersections, each intersection had just one logical queue, so that vehicles went through the intersection in first-come-first-served order. This is not strictly realistic, because in a real intersection, when things get congested, separate queues build up on each incoming road, but we can get away with it because most uncontrolled intersections rarely have this much traffic in real life.

With stop lights, on the other hand, we definitely need separate queues for each incoming road. To do this, the connections between roads and intersections need to be more elaborate, and we face a design decision. If vehicles have to wait, do they queue up in the intersection or on the road leading to the intersection. This is not a question about the physical geometry of real intersections, it is a question about the structure of our code: Are the queues of waiting cars part of the road object or are the queues of waiting cars part of the intersection object? Both of these schemes can be made to work.

• If queues are part of the road then the leave method of each road must know whether the intersection is blocking that road or not, and it must only call the enter method of the intersection if the intersection permits it. One way to do this would be for the intersection to communicate with each incoming road, effectively telling the road "green light" or "red light."

• If queues are part of the intersection then the leave method of roads can remain simple because the queues within the intersection are hidden from the road. This seems like it will reduce the amount of communication needed between roads and intersections.

But, we still have a problem: Stop lights have a direction, and our basic road network description does not have a concept of direction. Whichever of the approaches we take above, we need to add directions to the roads entering an intersection, and we need to add rules to the stop light that indicate which directions it turns green in what order. This has an impact on both the model description language we use and on the internals of the simulator.

Adding Direction intersections

Most intersections in the American midwest are 4-way intersections, but in older regions, the US east coast and most of Europe, there are large numbers of three-way and occasional 5 and even occasional 6-way intersections. 4-way stoplights, though, have a unique property: When the light is red in the east-west direction, it is green in the north-south direction, and visa versa. 3 and 5-way intersections do not have this convenient property.

We could build a very complex model, but for the time being, we will simplify. Each stoplight will have a cycle length: 2-way stop lights will adequately model both one-lane roads with a light at each end, so the road is either westbound or eastbound at any given time, and 4-way intersections, where the light alternates between east-west and north-south. 3-way and 5-way lights model intersections with that many incoming roads where only one incoming road has a green light at any time. So, a stop light could be declared as follows:

intersection B 1.0 source 20.0 3

To make this work, we add an optional field to every road, a queue number. If that road is connected to a stoplight, it indicates which queue at that stoplight this road feeds. The field is optional because it doesn't matter for roads that connect to uncontrolled intersections. If the number is missing when a road connects to a stoplight, there should be an error message.

road A B 3.0 1

The above road connects to incoming road number 1 of stop-light B.

Building the Model

Stop light intersections need an incoming queue of vehicles for each incoming road. We can substitute an integer for each queue, just counting the vehicles until such time as we think about giving vehicle an individual identity. If we want to detect and report the fact that some incoming queue of a stop light has no road connected to it, we need to have an array of booleans, one per stop-light direction, to track which connections are unused.

Our constructor for a new road now needs to read the destination intersection incoming road number, we'll call this dstNumber, and if no value is given, we can make a default of -1. Where we used to call

destination.addIncoming( this );

We now need to call:

destination.addIncoming( this, dstNumber );

The addIncoming method needs to do several things: First, check that the road number is acceptable. And then not that that incoming queue has a road connected to it. The rules for an acceptible incoming road number depend on whether the intersection is a stop light or not.

At Simulation Time

In the simulation, when a vehicle exits a road, our event-service routine currently does this:

private void leave( double time ) {
    this.destination.enter( time );
}

private void leave( double time ) {
    this.destination.enter( time, dstNumber );
}

The fun part of this exercise occurs at stop-lights, in the enter routine and its interaction with the light-change routine. Recall the code for entry to a NoStop intersection:

public void enter( double time, int road ) {
    waiting = waiting + 1;  // enqueue this car
    if (waiting <= 1) {     // am I the only one in the queue, send me on
        Simulator.schedule(
            time + travelTime,
            (double t)-> this.leave( t )
        );
    }
}

What we will do for stop-lights is modify this code by having not one variable waiting that represents the length of the one queue, but an array, one for each queue. We also add a variable to indicate the current "green light" direction:

public void enter( double time, int road ) {
    if (!occupied && (road == greenLight)) {
        // am I the only one in the queue at a green light? send me on!
	occupied = true;
        Simulator.schedule(
            time + travelTime,
            (double t)-> this.leave( t )
        );
    } else {
        waiting[road] = waiting[road] + 1;  // enqueue this car
    }
}

private void leave( double time ) {
    assert occupied == true;
    if (waiting[greenLight] > 0) {   // can a new car enter the intersection?
        waiting[greenLight] = waiting[greenLight] - 1;  // dequeue that car
        Simulator.schedule(          // schedule its departure
            time + travelTime,
            (double t)-> this.leave( t )
        );
        // that car now occupies the intersection, so occupied is still true
    } else {
	occupied = false;
    }

    this.pickOutgoing().enter( time );
}

private void lightChange( double time ) {
    Simulator.schedule(
        time + period,
        (double t)-> this.lightChange( t )
    );
    // BUG -- light changes should change which roads are blocked
    // BUG -- light changes should unblock any waiting vehicles
}

private void lightChange( double time ) {
    Simulator.schedule(
        time + period,
        (double t)-> this.lightChange( t )
    );

    // change which way the green light faces
    this.greenLight = (this.greenLight + 1) % incomingRoads;

    // is there a car waiting in the new green direction that can go?
    if (!occupied && (waiting[greenLight] > 0)) {
        waiting[greenLight] = waiting[greenLight] - 1;  // dequeue that car
        Simulator.schedule(          // schedule its departure
            time + travelTime,
            (double t)-> this.leave( t )
        );
	occupied = true; // that car now occupies the intersection
    }
}

this.greenLight = (this.greenLight + 1) % incomingRoads;

this.greenLight = this.greenLight + 1;
if (this.greenLight >= incomingRoads) this.greenLight = 0;