is connected by a set of
links 
. The set of links going out of node i (forward star)
is denoted 
, and the set of incoming links (backward star) is denoted
.
Heinz Spiess
EMME/2 Support Center, Haldenstrasse 16,
CH-2558 Aegerten, Switzerlandheinz@spiess.ch
June 1993
The standard transit assignment offered in EMME/2, which is based on optimal strategies, does not consider congestion effects due to limited vehicle capacity. This assignment model can be extended by taking into account the vehicle capacity by means of a volume-dependent transit time function, leading to the formulation of a transit equilibrium assignment model. In this note, we describe how the standard version of the EMME/2 Transportation Planning Software can be used to solve this assignment model. A macro has been written which implements a Frank-Wolfe descent algorithm, by combining the fixed cost transit assignment module with the network and matrix calculator modules.
In most transit assignment applications, congestion effects due to overcrowding of the vehicles are not taken into account for modeling of the route choice. This is a reasonable approach in all those cases where the goal of the planning process is to provide enough capacity for all transit passenger on the routes of their choice. There are, however, situations in which it is not feasible to provide enough transit capacity to preclude congestion. In these cases, the route choice of the transit passenger is likely to be influenced by the congestion on board the vehicles, so that some travelers will switch from congested to less congested routes, even if the latter are less attractive in terms of travel time or cost.
In this note, we describe an implementation of an equilibrium transit assignment based on the concept of optimal strategies. The congestion is modeled by means of volume dependent cost functions, similar to the volume-delay functions used in the highway equilibrium assignment. After having presented the mathematical formulation of the model, we discuss its implementation in EMME/2.
In this section we briefly describe the fixed cost transit assignment model based on optimal strategies. For a more detailed description of the model, as well as the proofs, refer to Spiess (1984) and Spiess and Florian (1989).
For the sake of easier presentation of the mathematical formulation of the
model, the transit network is assumed to be represented by a standard
node/link type network, where a set of nodes is connected by a set of
links . The set of links going out of node i (forward star)
is denoted , and the set of incoming links (backward star) is denoted
.
A travel time (or cost) 
and a service frequency 
is associated
with each network link a. The demand between nodes i and j is given by
.
Note that in this type of ``exploded'' network representation, the itineraries of the
transit lines are implicitly contained in the network topology. The set of
nodes not only contains the physical nodes of the underlying street or rail
network, but also one additional node for each transit stop of each line.
Correspondingly, the links are subdivided into various classes, such
as boarding, alighting, in-vehicle and walking links. Note that only
boarding links imply waiting, thus have a finite frequency . All other
links are served continuously ( 
).
The waiting time at a node depends on the set of attractive links
, i.e. the set of outgoing links which are considered
for travel by the travelers by boarding the first vehicle leaving on any
of these links. For any given set of attractive links 
at node i,
the combined waiting time is proportional to the combined total frequency
of these links is
and the probability of leaving node i on link a is
Given the above relations, any strategy for reaching destination r
is completely defined by the corresponding subset of attractive links
.
The optimal strategy for reaching a destination is the one which
minimizes the total expected cost. Note that the cost of a strategy is
the sum of link travel times weighted by the probability of traveling
on link a, and the waiting time at nodes i weighted by the probability
of traveling through node i. It has been shown that for fixed link travel
times , the assigning of the trips from all origins to destination r
according to the optimal strategy corresponds to solving the following
linear optimization problem:
subject to
Note that the variables 
represent the total waiting time (in person
minutes) at node i.
The problem (3) can be solved very efficiently by means of the following label-setting type algorithm:
We now turn our attention to the the variant of the transit assignment problem
in which the link travel times are no longer constants, but are
continuous non-decreasing functions of the corresponding link flows 
.
Such a dependence of the link cost on the transit volume may represent
an actual slowing down of the transit vehicle due to the number of
passengers, but it may also be interpreted as a generalize cost which
includes a ``discomfort'' term which increases as the vehicles get crowded.
In this context, the transit assignment problem is no longer separable by destination node, since the link costs depend on the total flow of passengers. The total transit volumes are the sum of the volumes bound for each of the destinations.
As the expected cost of any given strategy is no longer fixed, but depends on the total volumes, the optimal strategies are now defined by Wardrop's second principle, which implies that only strategies with minimal expected cost will be used by the travelers (Wardrop, 1952). The resulting equilibrium assignment is equivalent to the following convex minimization problem:
subject to
As has been shown by Spiess (1984), the above problem can be solved by
applying the successive linear approximation method (Frank and Wolfe, 1956).
An important advantage of this method is the fact that only total volumes
need to
be computed and stored, since the destination dependent volumes 
are dealt with implicitly.
Optimal Strategy Equilibrium Transit Assignment:
| Step 0: | (Initialization) |  |
| Step 1: | (Subproblem) |  |
| Step 2: | (Line Search) |  |
| Step 3: | (Update) |  |
The minimization in Step 2 is best implemented not by actual minimization, but by annulling the derivative, i.e. solving the equation
Note that the stopping criterion used in Step 3 of the above algorithm corresponds to the absolute gap, which is an upper bound for the difference between the objective function at the current solution and at the true optimum.
In this section we describe how the transit equilibrium assignment can be implemented in the EMME/2 Transportation Planning Software (Spiess, 1984, and INRO, 1992). An important feature of EMME/2 is its modularity. The various functionalities used in the transportation planning practice are implemented as a set of independent basic tools, all acting on a common data bank. These can easily be used individually or in combination to form more complex models. A powerful macro language is provided within the EMME/2 system, which allows the user to implement the various steps of the model and to automate the procedure.
To implement the equilibrium transit assignment discussed in the previous section, the following basic EMME/2 tools are used:
The travel cost function is given by a fixed travel time 
and a volume dependent congestion function 
in the form
The congestion function can be any non-decreasing function with d(0)=0.
It models the discomfort of traveling on a segment at a volume 
.
Since the function 
is specified as a network calculator expression,
it can access any other attribute of the transit line as well, such as:
headway, seated and total vehicle capacity, user attributes.
By default, BPR-type and conical congestion functions are provided
(Spiess, 1990), but the macro allows easy integration of other functional
forms that might be required for particular applications.
The fixed travel costs
are, as usual, coded directly into the transit time functions.
In order to enable the transit time functions to reflect congestion costs,
all transit time functions have to be multiplied with the term
*(1+US1). During the assignment steps, the user defined segment
attribute US1 will contain the value of the congestion function
.
In terms of the so defined congestion function , the objective function
of the equilibrium assignment (7) separates in a (linear) travel time
part T and a (non-linear) congestion part
The derivative of the objective function with respect to 
(12), used to compute the optimal step length 
, is
With the above preliminaries, we can now outline the implementation of the EMME/2 equilibrium transit assignment macro CONGTRAS (CONGested TRansit ASsignment):
| Step: | Description: | Module: |
| 1 | Initialize congestion costs US1 to 0. | 2.41 |
| 2 | Compute total number of transit trips
and initialize iteration counter  . | 3.21 |
| 3 | Perform uncongested fixed cost assignment to obtain  and  . | 5.11/5.31 |
| 4 | Compute congestion cost . | 2.41 |
| 5 | Increment iteration counter  . | 3.21 |
| 6 | Compute new segment congestion costs  into US1. | 2.41 |
| 7 | Perform fixed cost transit assignment with new congestion costs to obtain
 and  . | 5.11/5.31 |
| 8 | Compute stopping criterion GAP. | 2.41 |
| 9 | Perform line search for obtaining optimal step length . This
is implemented using the secant method to annul (15). | 2.41 |
| 10 | Update transit volumes  . | 2.41 |
| 11 | Update total travel time  . | 3.21 |
| 12 | Test normalized gap stopping criterion. If GAP  then STOP, else continue with step 5. | 2.41 |
[1]For technical reasons, this step is implemented in the macro not in module 2.41, but using low level data manipulations in module 1.11.
In its current form, the CONGTRAS macro only considers crowding within the transit vehicles. But of course, as can be seen from the model formulation in the previous section, it is also possible to include congestion discomfort outside the transit vehicles, such as crowding on the platforms and on the pedestrian walk link - as long as the discomfort function is symmetric (i.e. the same travelers that are causing the congestion are also suffering the effects of it).
We have shown that it is possible to implement a true equilibrium transit assignment within the framework of the standard EMME/2 system. A variant of the macro outlined above is being used at London Transport for modeling crowding in the London Underground. Instead of using one of the default congestion functions which are based on nominal capacity, the macro has been modified for taking into account the actual profile of train density and passenger load during peak period. The details of this project are described in Abraham and Kavanagh (1992).
It can be argued with good reason, that the modeling congestion should be done using asymmetric congestion functions, e.g. as the perceived frequency of a line for a boarding passenger depending on the number of passengers already on board, or the dwell time of a line at a node depending on the number of boarding and alighting passengers. While it is indisputable that such phenomena occur in reality, including them into assignment models as the one described here unfortunately leads to models with non-unique solutions. Since the uniqueness of the solution is a primordial requirement for any assignment model, such asymmetric models, even those for which convergent algorithms are available, are of very limited practical use.
