First draft! -- Subject to revision! 
Please let me know of any errors and typos you find - thanks!
Heinz Spiess
EMME/2 Support Center, Haldenstrasse 16, CH-2558 Aegerten, Switzerland
November 1996
In this note we extend the mixed mode logit model for intermediate destination choice to a similar model in which an explicit capacity is associated with each intermediate destination. This leads to a more realistic approach for modeling park&ride trips, since (in contrast to Kiss&Ride trips) the capacity of an intermediate zone is limited by the parking capacity it offers. We first show that this model can be expressed as a convex minimization problem. Then we look at the dual formulation and show that it can be solved efficiently with a coordinate descent method. A solution algorithm is proposed and its properties are discussed in detail. Finally, special attention is given to the practical aspects of applying such a model for real life projects, and a general implementation of the model in the form of a macro for the EMME/2 transportation planning package is outlined.
First draft! -- Subject to revision!
Please let me know of any errors and typos you find - thanks!
A PDF version of this document is also available.
In Spiess (1993) the problem of modeling the intermediate destination choice for mixed mode trips (such as park&ride or kiss&ride) has been discussed as one example of a distribution model based on an activity chain. It was shown how such models, if based on a logit distribution, can be implemented efficiently by the use of simple algebraic matrix multiplications.
The purpose of this note is to focus on the intermediate destination choice for park&ride trips in particular, i.e. on modeling a logit type choice of a convenient parking lot. After a brief recapitulation of the model without parking capacities in section 2, the remainder of this note concentrates on the problem in the presence of explicit capacities at the parking lots and shows how this problem can be formulated and solved efficiently.
While we will refer to the model discussed here specifically as a ``park&ride'' model, it should be noted that the same model is of course also applicable to other kinds of mixed mode travel which impose some capacity constraints at the intermediate destinations. In particular, it can be applied to ferry choice models, such as the one used by the Washington State Ferries (see Dehghani and Gihring, 1995).
In the absence of any parking capacity constraints a simple logit type parking lot choice model for park&ride trips is given by the following formula:
where 
is the number of trips between p and q
choosing parking site k, according to the (properly weighted) mode specific
travel impedances 
for the first leg and 
for the second leg of
the mixed mode trip. The total park&ride demand for O-D pair pq
is 
.
Note that the above formulation does not include an explicit impedance term for the parking lots (e.g. to model the effects of parking cost). Dropping this term does not cause any loss of generality of the following development, as it can be thought already included in one of the leg impedances.
See Spiess (1993) for a more ``practical'' discussion of this uncapacitated mixed mode model (as a special case of an activity chain model), including details on its implementation using the convolution module of the EMME/2 software (Spiess 1984; INRO 1996). A practical application of this model for the Puget Sound Regional Council has been reported by Blain (1994).
From a mathematical programming point of view, it is important to note that the above parking lot choice model is equivalent to the following convex minimization problem:
subject to
By applying the Kuhn-Tucker optimality conditions (see e.g. Luenberger 1984), it can be shown that (1) corresponds indeed to the optimal solution of the above optimization problem.
We now turn our attention to the parking lot choice model in which
an explicit capacity 
is associated with each parking lot k.
To formulate the model, we simply add an additional constraint
to the uncapacitated problem, yielding
subject to
In order for the above problem to be feasible, it is of course necessary that the total demand for park&ride trips does not exceed the total amount of parking space available at the parking lots, i.e.
The less slack there is in the above inequality, the harder the problem will
become to solve. To avoid problems of degeneracy we also assume that
0 for all 
.
By introducing the dual variables 
for the constraints (5) and
for constraints (6) and applying again the Kuhn-Tucker
optimality conditions, we obtain a model of the following functional form:
From this, we can obtain the dual problem formulation as follows:
subject to , .
The Kuhn-Tucker optimality conditions of the dual problem can be written as follows:
The optimal values of the dual variables associated with the parking
capacity constraints, 
, are the shadow prices associated
with the ``last'' parking space on parking lot k. They correspond to the
additional impedance (or weighted cost) which would need to be imposed at the
parking lot in order to defer enough potential trips to other parking lots
to meet the given capacity .
For parking lots which do not reach capacity ( 
) this
cost is obviously zero. For a parking lot which is capacity bound,
can be used as an indicator of the cost imposed
to the system by limiting its capacity to .
As the dual problem (9) does not have any explicit constraints, other
than the non-negativity of 
, it can be solved efficiently by using
the successive coordinate descent method for the dual variables 
and
. Thus, the optimal solution to the capacitated parking choice model
can, in principle, be found by iteratively solving the equations (10)
and (11) for and .
From a practical point of view, it is preferable not to formulate the
solution algorithm in terms of the dual variables and 
, but instead
use the following variable substitution
and 
.
In a similar way, the exponential terms
related to the first and second leg impedances can be evaluated ahead of time,
which leads to the substitutions
and 
.
This way, the algorithm will become easier to understand and
implement, avoiding the evaluation of any exponentials or logarithms
during the execution of the algorithm. In addition, this allows expressing
the operations in terms of simple matrix products (as shown in Spiess 1993)
-- even though this type of representation is not used here.
Using the above substitutions, a successive coordinate descent algorithm for the dual problem (9) can be formulated as follows:
for .
:and use the results to compute
then STOP.
From a practical point of view, it is important to note that step 1 of the
algorithm corresponds exactly to solving an uncapacitated parking choice
model with a parking lot impedance 
. Thus, this step can be implemented
using the same procedures or macros which are already available for
the problem without capacities.
Even if the above algorithm is terminated before complete convergence is
reached, the solution obtained will always satisfy the conservation
of flow constraint (5),
whereas some of the capacity constraints (6) may still be violated
by a certain amount. This is typical for dual based algorithms, and also
has the additional advantage that the algorithm will even converge to a
solution if the primal problem is infeasible, i.e. if the total park&ride
demand exceeds the available total parking space ( 
).
In the later case, the algorithm simply converges to a solution in which
--loosely speaking-- the parking capacity constraints are violated the least
possible.
If they are needed, the shadow prices can be computed
as 
once the algorithm has terminated.
These values (converted back into cost or impedance values by dividing by
the appropriate model coefficients) can be very
useful for analyzing the sensitivity of existing capacities or for deciding
where to locate additional parking capacity.
While the previous sections looked at the posed problem from an abstract and theoretical point of view, let us now turn our attention to the practical implementation and use of such a model.
First, it is important to note that the variables used in the
mathematical formulation are not easy to handle in real life (there are
far too many of them!), nor are they really pertinent in practice. The
problem, as it is posed in practice, is to split the given park&ride
demand matrix into two intermediate demand matrices 
and
: for the first leg (usually the auto part) of the trip,
and for the second leg (usually the transit part). These
intermediate matrices can be obtained as follows
by using the before-mentioned substitutions in (8) and
summing over p or q:
Fortunately, the explicit knowledge of the variable is also not
required for carrying out the solution algorithm, it suffices to know
the values for the total parking lot usage for each lot,
which can easily be obtained from either first or second leg demand matrix
as
The model and the solution algorithm described in the previous sections
have been implemented in the EMME/2 transportation planning package
(Spiess 1984, INRO 1996) in the form of a macro entitled PARKRIDE.
This macro uses the matrix convolution module of EMME/2 to implement
the algebraic matrix multiplications (i.e. the sums) in (12),
(14) and (15) and the matrix calculator module
to compute all other (element by element) operations. For improved efficiency,
only the first leg matrix is computed at each iteration of the
algorithm. The second leg matrix needs only be computed once, at
the very end of the algorithm.
Furthermore, the macro allows the explicit specification of fixed
impedance or disutility term for each parking lot, which e.g. can be used
for representing parking costs.
The macro
PARKRIDE is available via Internet on the
Web site of the EMME/2 Support Center.
We have shown that the problem of a logit type intermediate destination choice for mixed mode trips can indeed be extended to include capacity constraints. The resulting model is ``well behaved'' in all important aspects: It has a consistent mathematical formulation, a solution algorithm which is known to produce an optimal solution and which can be (and has been) implemented efficiently even for large scale real-life applications.
