Modeling and Simulation
By Kenroy Williamson
Dr. Jim Nutaro

A SIMULATION API FOR TRAFFIC MODELING

This document describes an application programming library for constructing the dynamic pieces of a traffic simulation. It is meant to complement a complete traffic modeling tool set that includes data import and export capabilities, traffic routing algorithms, and visualization tools.

This software library provides an abstract framework for constructing event driven models of traffic dynamics. It is based on the DEVS modeling and simulation framework, and will be implemented using ADEVS discrete event simulation package.

Basic elements of a traffic model

Three basic elements of a traffic model are represented abstractly in the modeling framework. Traffic sources represent locations from which traffic can enter a road network. Traffic sinks are destination locations where traffic can leave a road network. Road segments represent traversable pieces of a road network. A road segment can represent an intersection, a one way street, a multi-lane highway, or any other navigable piece of the road system.

The road system is navigated by population units. Population units are characterized by a size (e.g., number of people or number of vehicles) and a destination. Population units originate at traffic sources and are ultimately deposited at traffic sinks. They travel from source to sink through a road segment graph. The paths taken by the population unit, and the time required for a population unit to traverse a road segment, are determined by the user of the modeling framework. The modeling framework provides event scheduling, feedback for modeling congestion, and other time and structure related services that are needed to perform the actual simulation. These services are accessed by the end user via the object oriented simulation API presented in this document.

API documentation

The API is comprised of seven classes. Three of these are used to represent sinks, sources, and road segments. One class represents population units. Another class represents the state of sinks, sources, and road segments. This class can be used to implement feedback into the road network dynamics. The last two classes is used to describe the road network and run the simulation. These classes and their essential relationships are shown in the attached UML class diagram.

The PopUnit and ComponentState classes

These classes are base classes that can be extended, as needed, by the end user.
PopUnit objects (or its derivatives) can only be created at Segments, and they are destroyed automatically when they reach a Sink. A PopUnit can only be delivered to a single Sink! Attempts to access the PopUnit object after is has been destroyed at a Sink will have undefined (and probably undesirable) results.
ComponentState objects (or its derivatives) can be created at any time. They are destroyed after being delivered to all of the NetworkComponents that supply inputs to this component. If a ComponentState object is going to be propagated back through the network, a new copy of the object must be created prior to propagating the event. Attempting to access the object after the callback that delivered it has returned will have an undefined (and probably undesirable) result.

The NetworkComponent class

The NetworkComponent, Sink, and Segment classes are used to describe the elements of a road network. The NetworkComponent class is the base class for every road network. xEvery network has a unique net_component_id_t that is used throughout the simulation library. It is also possible to obtain the list of identifiers for the NetworkComponent objects that are directly adjacent to it. Every class derived from the NetworkComponent class inherits three event handlers and one event generator. Two event handlers are concerned with the motion of population units. These are populationArrived(who: PopUnit) and populationLeft(who: PopUnit). These methods are activated when a population unit arrives at and leaves the NetworkComponent. These are pure abstract methods that must be defined by the end user.

The third event handler is componentStateChanged(new_State: ComponentState).
This method is activated when a component that is adjacent to this component generates a component change event. Component change events can be generated by calling the componentStateUpdate(new_State: ComponentState). Taken together, these methods allow for feedback to be built into the road network dynamics (e.g., to prevent traffic from entering a segment that is at capacity).

In addition to these event handlers and event generators, every NetworkComponent object has a method initialize() that is called at the very beginning of the simulation run, and a method finalize() that is called at the very end of the simulation run.

All of the events associated with the NetworkComponent object are instantaneous events, and they require no time to execute or to propagate. These event handlers (in fact all event handlers in this library) execute atomically (i.e., they can not be interrupted).

The Sink class

The sink class is derived from the NetworkComponent class. A sink represents a destination in the network. As such, population units can not leave a sink and are destroyed after the populationArrived(who: PopUnit) method is called.

The Segment class

The segment class adds three event generating methods to its NetworkComponent base class. The scheduleDeparture(who: PopUnit, dst: net_component_id_t, t: double) is used to schedule the arrival of a population unit at a specific destination in t units of time. This method can fail with an exception if the destination is not adjacent to the calling node or if the time t is less than zero. The population unit will leave the calling segment in t units of time, and this departure will be accompanied by a populationLeft(who: PopUnit) event. At the same time that the population leaves the calling segment, it will arrive at the destination segment. The arrival is indicated by the populationArrived(who: PopUnit) event. At any time, the population unit can only be scheduled to arrive at a single destination.

A scheduled departure can be canceled in two ways. The departure of a specific population unit can be effected with the method cancelDeparture(who: PopUnit).
The cancellation of all scheduled departures can be done with the method cancelAllDepartures().

Creating a network

The Network class is used to describe the interconnection of road components.
The Network class has three methods for doing this. The addComponent(c:
NetworkComponent) method simply adds a node to the network. The node can be a
Sink or Segment object. The connectComponents(src: Segment, dst: Segment) allows two road segments to be connected. Segment's can model population sources, intersections, highways, one way roads, etc. The method connectComponents(src: Segment, dst: Sink) is used to attach a Sink to a Segmentmodel. The list of nodes in the network can be obtained with the method getComponents(): list<NetworkComponent>, which returns a list containing all of the nodes in the network.

Running a simulation

The NetworkSimulator class is used to execute a simulation. Prior to running a simulation, a Network model is attached to the simulator with the initialize_model(model: Network) method. This causes the components of the network to be initialized and the simulation data structures to be initialized. The simulator can be executed event by event with the executeNextEvent(): double method. This method causes the next scheduled event to be processed and returns the time at which that event occurred (i.e., the current simulation time). When the simulation is complete (e.g., when the current simulation time is infinity or some other user defined condition has been met), then the finalize() method is called to indicate the end of the simulation run. Repeated simulation runs with the same model can be done by repeating these steps.

Sketch of how to construct a simulator using this framework

The end user of this library will create classes to represent individual pieces of the road network. These pieces will be constructed by deriving new models from the Sink and Segment class and implementing all of the abstract functions.

For the sake of illustration, suppose we want to create a network with a single source and a single sink. Call these models MySource and MySink. The implementations of the MySource model might appear as follows.

class MySource: public Segment
{
public:
/// Constructor
MySource():
Segment()
{
}
/// This method is called at the beginning of a run
void initialize()
{
/// Schedule the first population unit to leave
/// in 1 time unit
NetworkComponent sink = getAdjComponents().front();
scheduleDeparture(new PopUnit(),sink,1.0);
}
/// This method is called at the end of a run
void finalize()
{
/// Write out final statistics
}
/// This is a source, so nothing arrives.
void populationArrived(PopUnit who)
{
}
/// This is called when a something leaves the source
void populationLeft(PopUnit who)
{
/// Schedule the next population unit to go
NetworkComponent sink = getAdjComponents().front();
scheduleDeparture(new PopUnit(),sink,1.0);
}
/// If the sink generated state updates, they would be
/// reported here.
void componentStateChanged(ComponentState new_state)
{
}
/// Destructor
~MySource()
{
}
};
The MySink model would have a similar implementation, but would be derived from
Sink instead of Segment. The network could be created and simulated as shown in the following code snippet.

...
// Create the network model
Network network;
MySink sink;
MySource source;
network.addComponent(sink);
network.addComponent(source);
network.connectComponents(source,sink);
// Simulate the network model
NetworkSimulator sim;
sim.initialize_model(network);
while (sim.executeNextEvent() < simulation_end_time)
{
// Draw new state of model
}
sim.finalize_model();
...

Jim Nutaro

home | about me | research | mentor | images | links