17. A Working Road Network Simulator

Part of CS:2820 Object Oriented Software Development Notes, Fall 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

A Working Road Network Simulator

The pieces we have developed up to this point allow us to build a working road network simulator. First, we had a few small errors in the old code, and we need to add some output to the simulator so we can see what it is doing.

Small Errors:

The old code had a significant error. We can identify 4 basic events in a road network:

We need to simulate all 4 of these. For example, entering a road schedules the exit from that road after the appropriate travel time and enter and exit from a road can track of the population of that road (just in case we later decide that the travel time of a road depends on how congested it is). Similarly, entry to an intersection can place a car in a queue if the intersection is occupied and exiting an intersection clears that intersection for other vehicles to continue, possibly removing a car from the queue.

In our early version of the code, we had entering a road cause the car to leave the associated intersection, while exiting the road caused the car to enter the next intersection. This was wrong. We could have written the entry to a road like this, scheduling both the exit from the road and the entry to the next intersection at the same time:

	public void enter( Vehicle v, float t ) {
		/** Simulate v entering this road at time t.
		 *  This is always called at the same time as intersection exit.
		 */

		// track state of road
		population = population + 1;

		Simulator.schedule(
			t + travelTime,
			(float time)->this.exit( v, time )
		);
		Simulator.schedule(
			t + travelTime,
			(float time)->destination.enter( v, time )
		);
	}

Alternatively, we could just have entry to the road schedule the exit from the road, and let the code to exit the road schedule the entry to the adjoining intersection:

        public void exit( Vehicle v, float t ) {
		/** Simulate v exiting this road at time t.
		 */

		// track state of road
		population = population - 1;

		// report that v will enter the destination intersetion
		Simulator.schedule(
			t,
			(float time)->destination.enter( v, time )
		);
	}

It seems silly to schedule a call to a method to take place "now" when we could just as easily call that method directly, as follows:

        public void exit( Vehicle v, float t ) {
		/** Simulate v exiting this road at time t.
		 */

		// track state of road
		population = population - 1;

		destination.enter( v, t )
	}

We opt for the latter solution, both for exiting roads and for exiting intersections.

Of course, we must not forget to actually run the simulation. We do this with a call to Simulator.run() in the main program after initializing the road network data structures and checking that they are well formed.

Debug Output

We need some way to see if the simulation is actually running correctly. The obvious way to do this, at least initially, is to produce debug output tracing every entry and exit from roads or intersections. For example, the code to exit a source interseciton might be written as follows:

        public void exit( Vehicle v, float t ) {
		/** Simulate v exiting this intersection at time t.
		 */

		System.out.println( "Exiting " + this.toString()
			+ " at time = " + t
		);

		Road d = v.pickRoad( outgoing );
		Simulator.schedule( t, (float time)->d.enter( v, time ) );

		// Bug:  Later, make sources create multiple vehicles at
		// random times.
	}

This code still only creates one vehicle per source, but it is complete enough that we can see how to upgrade it to produce more vehicles later.

Also, the output code does not say anything about which vehicle is leaving or entering intersections. We really ought to give each vehicle a serial number so we can trace which vehicle goes where.

A Test

With all of the above logic in place, we can now test the simulator. Here is an example road network:

intersection source a 999
intersection sink d 999
intersection nostop b 1
intersection nostop c 2
road a b 45
road b b 5
road b c 5
road c b 5
road c c 5
road c d 5

Running the simulator on this input gives the following simulation trace -- it is very long because the road network contains loops and the vehicle is making random turns on its way from the source at intersection a and the sink at interseciton d:

Exiting intersection source a at time = 0.0
Entering road a b 45.0 at time = 0.0
Exiting road a b 45.0 at time = 45.0
Entering intersection nostop b at time = 45.0
Exiting intersection nostop b at time = 46.0
Entering road b b 5.0 at time = 46.0
Exiting road b b 5.0 at time = 51.0
Entering intersection nostop b at time = 51.0
Exiting intersection nostop b at time = 52.0
Entering road b b 5.0 at time = 52.0
Exiting road b b 5.0 at time = 57.0
Entering intersection nostop b at time = 57.0
Exiting intersection nostop b at time = 58.0
Entering road b b 5.0 at time = 58.0
Exiting road b b 5.0 at time = 63.0
Entering intersection nostop b at time = 63.0
Exiting intersection nostop b at time = 64.0
Entering road b b 5.0 at time = 64.0
Exiting road b b 5.0 at time = 69.0
Entering intersection nostop b at time = 69.0
Exiting intersection nostop b at time = 70.0
Entering road b b 5.0 at time = 70.0
Exiting road b b 5.0 at time = 75.0
Entering intersection nostop b at time = 75.0
Exiting intersection nostop b at time = 76.0
Entering road b b 5.0 at time = 76.0
Exiting road b b 5.0 at time = 81.0
Entering intersection nostop b at time = 81.0
Exiting intersection nostop b at time = 82.0
Entering road b c 5.0 at time = 82.0
Exiting road b c 5.0 at time = 87.0
Entering intersection nostop c at time = 87.0
Exiting intersection nostop c at time = 89.0
Entering road c c 5.0 at time = 89.0
Exiting road c c 5.0 at time = 94.0
Entering intersection nostop c at time = 94.0
Exiting intersection nostop c at time = 96.0
Entering road c c 5.0 at time = 96.0
Exiting road c c 5.0 at time = 101.0
Entering intersection nostop c at time = 101.0
Exiting intersection nostop c at time = 103.0
Entering road c c 5.0 at time = 103.0
Exiting road c c 5.0 at time = 108.0
Entering intersection nostop c at time = 108.0
Exiting intersection nostop c at time = 110.0
Entering road c c 5.0 at time = 110.0
Exiting road c c 5.0 at time = 115.0
Entering intersection nostop c at time = 115.0
Exiting intersection nostop c at time = 117.0
Entering road c c 5.0 at time = 117.0
Exiting road c c 5.0 at time = 122.0
Entering intersection nostop c at time = 122.0
Exiting intersection nostop c at time = 124.0
Entering road c b 5.0 at time = 124.0
Exiting road c b 5.0 at time = 129.0
Entering intersection nostop b at time = 129.0
Exiting intersection nostop b at time = 130.0
Entering road b c 5.0 at time = 130.0
Exiting road b c 5.0 at time = 135.0
Entering intersection nostop c at time = 135.0
Exiting intersection nostop c at time = 137.0
Entering road c c 5.0 at time = 137.0
Exiting road c c 5.0 at time = 142.0
Entering intersection nostop c at time = 142.0
Exiting intersection nostop c at time = 144.0
Entering road c d 5.0 at time = 144.0
Exiting road c d 5.0 at time = 149.0

The code

Example code is available here.