From the previous discussions it follows that we want the following conditions to be fulfilled for a traffic simulation:
This includes the fact that in the future we want to be able to include task parallelization into the software.
These conditions make the use of existing software packages, such as DYNAMIT, DYNASMART, or TRANSIMS, difficult, since these software packages are already fairly complex and complicated. An alternative is the selection of a simple model for large scale microscopic network simulations, and to re-implement it. If one wants queue spill-back, there are essentially two starting points: queuing theory, and the theory of kinematic waves.
In queuing theory, one can build networks of queues and servers ((43,41,12)). Packets enter the network at an arbitrary queue. Once in a queue, they wait, typically in a first-in first-out (FIFO) queue until they are served; servers serve queues with a given rate. Once the packet was served, it will enter the next queue.
This can be directly applied to traffic, where packets correspond to vehicles, queues correspond to links, and serving rates correspond to capacity. The decision which link to enter after a vehicle was served is given by the vehicle's route plan.
A shortcoming of this type of approach is that it does not model spill-back. If queues have size restrictions, then packets exceeding that restriction are typically dropped (43). Since this is not realistic for traffic, an alternative is to refuse further acceptance of vehicles once the queue is full (``physical queues''). This however means that the serving rate of the upstream server is influenced by a full queue downstream. Such a model was for example used by Gawron (20). A detailed algorithmic description is given in Fig. 2(a).
An important issue with physical queues is that the intersection logic needs to be adapted. Since without physical queues (i.e. with ``point queues'') the outgoing links can always accept all incoming vehicles, the maximum flow through each incoming link is just given by each link's capacity. However, when outgoing links have limited space, then that space needs to be distributed to the incoming links which compete for it.
In the original algorithm (Fig. 2(a)), links are processed in arbitrary but fixed sequence. This has the consequence that the most favoured link in a given intersection is the one that is processed next after the congested outgoing link has been processed. This could for example mean that a small side road obtains priority over a large main road.
A better way to do this is to allocate flow under congested conditions according to capacity (14). For example, if there are two incoming links with capacities 2 and 4 per time step, and the outgoing link has 3 spaces available, then 1 space should be allocated to the first incoming link and 2 to the second. Sec. 4.2 will explain in more detail how this is implemented.
A shortcoming of queue models is that the speed of the backwards traveling kinematic wave (``jam wave'') is not correctly modeled. A vehicle that leaves the link at the downstream end immediately opens up a new space at the upstream end into which a new vehicle can enter, meaning that the kinematic wave speed is roughly one link per time step, rather than a realistic velocity. This becomes visible in the dissolution of jams, say at the end of a rush hour: If a queue extends over a sequence of links, then the jam should dissolve from the downstream end. In the queue model, it will essentially dissolve from the upstream end. More details of this, including schematic fundamental diagrams, can be found in (20,42).
Despite this shortcoming, we will use the queue model for its simplicity. This point will be revisited in the discussion.