A simulation API for traffic modeling

A SIMULATION API FOR TRAFFIC MODELING

This document describes an application programming lib= rary for constructing the dynamic pieces of a traffic simulation. It is me= ant to complement a complete traffic modeling tool set that includes data import and export capabilities, traffic routing algorithms, and visualization tool= s.

This software library provides an abstract framework f= or 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 element= s of a traffic model

Three basic elements of a traffic model are represented abstractly in the modeling framework. Traffic sources represent locat= ions 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 segme= nt can represent an intersection, a one way street, a multi-lane highway, or a= ny 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 num= ber of vehicles) and a destination. Population units originate at traffic sources and are ultimately deposited at traffic sinks. They travel fr= om 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 congest= ion, 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 documenta= tion

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 sho= wn 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 automa= tically when they reach a Sink. A PopUnit can onl= y be delivered to a single Sink! Attempts to access the PopUnit= object after is has been destroyed at a Sink will have undefined (and proba= bly 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 objec= t is going to be propagated back through the network, a new copy of the object m= ust be created prior to propagating the event. Attempting to access the object after the callback that delivered it has returned will have an undef= ined (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 ro= ad network. Every network has a unique net_componen= t_id_t that is used throughout the simulation library. It is also possible to obtain the list of identifiers for the NetworkComponen= t 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 th= e NetworkComponent. These are pure abstract metho= ds 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 adja= cent 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 generato= rs, every NetworkComponent object has a method initialize() that is called at the very beginning of t= he simulation run, and a method finalize() that is called at the very end of the simulati= on 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 clas= s

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 c= alled.

The Segment c= lass

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 sched= ule 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 t= he same time that the population leaves the calling segment, it will arrive at the destination segment. The arrival is indicated by the populationArrived(wh= o: PopUnit) event. At any time, the population uni= t can only be scheduled to arrive at a single destination.

A scheduled departure can be canceled in two ways.&nbs= p; The departure of a specific population unit can be effected with the method cancelDeparture(who: PopUnit).

The cancellation of all scheduled departures can be do= ne with the method cancelAllDeparture= s().

Creating a ne= twork

The Network class is used to describe the interconnect= ion of road components.

The Network class has three methods for doing this.&nb= sp; The addComponent(c:

NetworkComponent) method s= imply adds a node to the network. The node can be a

Sink or Segment object. The connectComponents(src: Segment, dst: Segmen= t) allows two road segments to be connected. Segment's can model population sou= rces, 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 l= ist containing all of the nodes in the network.

Running a sim= ulation

The NetworkSimulator class= is used to execute a simulation. Prior to running a simulation, a Network mod= el is attached to the simulator with the initialize_model(model: Network) method. This causes the components of the network to be initialized a= nd 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 creat= e 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.<= /p>

class = MySource: public Segment

{

&nbs= p; public:

&nbs= p; &= nbsp; /// Constructor

&nbs= p; &= nbsp; MySource():

&nbs= p; &= nbsp; Segment()

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; }

&nbs= p; &= nbsp; /// This method is called at the beginning of a run<= /p>

&nbs= p; &= nbsp; void initialize()

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; &nbs= p; /// Schedule the first population unit to leave

&nbs= p; &= nbsp; &nbs= p; /// in 1 time unit

&nbs= p; &= nbsp; &nbs= p; NetworkComponent sink =3D getAdjComponents().f= ront();

&nbs= p; &= nbsp; &nbs= p; scheduleDeparture(new PopUnit(),sink,1.0);<= /p>

&nbs= p; &= nbsp; }

&nbs= p; &= nbsp; /// This method is called at the end of a run

&nbs= p; &= nbsp; void finalize()

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; &nbs= p; /// Write out final statistics

&nbs= p; &= nbsp; }

&nbs= p; &= nbsp; /// This is a source, so nothing arrives.

&nbs= p; &= nbsp; void populationArrived(PopUnit who)

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; }

&nbs= p; &= nbsp; /// This is called when a something leaves the sourc= e

&nbs= p; &= nbsp; void populationLeft(PopUnit who)

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; &nbs= p; /// Schedule the next population unit to go

&nbs= p; &= nbsp; &nbs= p; NetworkComponent sink =3D getAdjComponents().f= ront();

&nbs= p; &= nbsp; &nbs= p; scheduleDeparture(new PopUnit(),sink,1.0);<= /p>

&nbs= p; &= nbsp; }

&nbs= p; &= nbsp; /// If the sink generated state updates, they would = be

&nbs= p; &= nbsp; /// reported here.

&nbs= p; &= nbsp; void componentStateChanged= (ComponentState new_state)=

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; }

&nbs= p; &= nbsp; /// Destructor

&nbs= p; &= nbsp; ~MySource()

&nbs= p; &= nbsp; {

&nbs= p; &= nbsp; }

};

The MySink model would hav= e a similar implementation, but would be derived from

Sink instead of Segment. The network could be cr= eated and simulated as shown in the following code snippet.

...

// Create the network model=

Network network;

MySink sink;

MySource source;

network.addCo= mponent(sink);

network.addCo= mponent(source);

network.conne= ctComponents(source,sink);

// Simulate the network mod= el

NetworkSimulator sim;

sim.initialize_model(network);

while (sim.executeNextEvent() < simulation_end_time)

{

&nbs= p; // Draw new state of model

}

sim.finalize_= model();

...

Jim Nutaro