This page is open for editing because it is part of the Incubator. Have something to add? Please register so you can contribute. Have an option you would like to share? Please click on the 'Talk' button to enter the dialogue. The TF Resource Volunteers appreciate your feedback and interest.

Three primary theoretical starting points for developing destination choice models dominate current practice:

• Gravity models.
• Entropy maximization (also known as information minimization) models.
• Random utility models.

These three modeling approaches are, under appropriate assumptions, mathematically equivalent, and so are special cases of what can be generally called spatial interaction models. All these models attempt to address the same problem, as illustrated in Figure 1, in which spatial interactions (usually trips) between locations in space (typically traffic zones) are to be predicted, given limited, more macro, information concerning these interactions, such as the number of trips originating in each zone and/or the number of trips destined to each zone.

Figure 1: The Spatial Interaction Problem

## Gravity Models

Gravity models have been in use by geographers, market researchers, transportation modelers and many others for well over a hundred years. The starting point for these models, as the name implies, is Newton’s Law of Gravity:

F_ij =Gm_i m_j d_ij^(-2) (1)

where Fij is the gravitation force between bodies i and j, mx is the mass of body x, dij is the distance between bodies i and j, and G is the gravitational constant. That is, the gravitational force (or interaction) between the bodies is proportional to their masses (size) and inversely related to the distance between them: bigger bodies closer together have a greater interaction.

Gravity models of human spatial interaction adopt the same assumption: the amount of interaction between two locations (usually represented by trips, but could also be flows of money, information, etc.) is proportional to the “size” (“attractiveness”) of the two locations and the extent of their physical separation (measured in distance or travel time). That is, gravity models assume:

T_ij ∝X_i T_ij ∝X_j T_ij ∝f_ij or, T_ij =kX_i X_j f_ij (2)

where Tij is the number of trips between origin i and destination j, Xi is some measure of the “size” of location i, fij is a measure of the “impedance” (difficulty of travel) between locations i and j, and k is a constant of proportionality. Fij is an inverse function of distance or travel time; that is, for example if t_ij is the travel time from i to j, then: (df_ij)/(dt_ij ) <0.

The constant k is chosen so that (2) satisfies known constraints on the interactions being predicted. If, for example, Xi = Oi, the number of shopping trips predicted by a trip generation model to originate in zone i, then it is reasonable to impose the constraint on our model that:

∑_j'▒T_ij' = O_i ∀ i (3)

Substituting (2) into (3) and solving for k yields:

k =1 / ∑_j'▒X_j' f_ij' or T_ij=O_i X_j f_ij / ∑_j'▒X_j' f_ij' (4)

Equation (4) is called a singly-constrained gravity model, since only a single constraint (equation (3)) has been imposed on the model. Very many examples of singly-constrained destination choice models exist, in a variety of applications. In particular, note that instead of constraining the predicted trips to match predetermined trip origin totals (an origin-constrained model), it would have been possible to constrain the trips to sum to predetermined trip destination totals instead (a destination constrained model).

In some cases, such as predicting work locations, it may make sense to constrain the predicted origin-destination (O-D) trips to equal both trip origin and trip destination totals (as typically determined by trip generation models). In this case, Xj is usually defined as Dj, the predetermined number of trips destined to location j, and, in addition to constraint (3), a second constraint is added that equation (2) must also satisfy:

∑_i'▒T_i'j = D_j ∀ j (5)

Imposing both constraints (3) and (5) on the model results in a doubly-constrained gravity model, which can be expressed as:

T_ij=O_i D_j^* f_ij / ∑_j'▒D_j'^* f_ij' (6)

where D*j is a modified attraction term that is iteratively defined so that constraint (5) is satisfied for all destinations j.

## Entropy Maximization Models

While it is intuitively plausible that should trips go to “bigger” (more attractive) destinations as well as to destinations that are closer to, rather than farther from, the trip origin, gravity models have always been criticized for their apparently ad hoc derivation: why should human interactions necessarily follow the same “law” as gravitational bodies? Beginning with Alan Wilson’s seminal paper in 1967,[1] a sound statistical theory underlying gravity models was developed. Wilson showed that the statistically most likely trip matrix, T, is given by maximizing the entropy function:

max┬T⁡∑_i▒∑_j▒〖T_ij ln⁡(T_ij 〗) (7)

subject to known constraints. In the case of a doubly-constrained model, at a minimum, these are constraints (3) and (5), plus typically a third constraint which often takes the form:

(∑_i▒〖∑_j▒T_ij t_ij 〗)/T= t ̅ ∀ i,j (8)

where T is the (known) total number of trips in the system, and t ̅ is the observed average travel time. In other words, equation (8) states that a feasible predicted trip matrix is one in which the predicted average travel time (the left-hand side of (8) equals the observed average travel time).

Solving this mathematical program yields the following trip distribution model:

T_ij = A_i B_j O_i D_j e^(βt_ij ) (9)

where  ( < 0) is an estimated parameter and Ai and Bj are “balancing factors” that are iteratively defined so that constraints (3) and (5) are both satisfied:

A_i =1 /∑_(j^')▒B_(j^' ) D_(j^' ) e^(βt_ij' ) (10.1)

B_j =1 /∑_(i^')▒A_(ij^' ) O_(ij^' ) e^(βt_i'j ) (10.2)

It can be shown that BjDj = D*j, the “modified attraction term” in the gravity model formulation, equation (6). Noting this and substituting (10.1) into (9) yields:

T_ij=O_i D_j^* e^(βt_ij ) / ∑_j'▒D_j'^* e^(βt_ij' ) (11)

This is exactly the doubly-constrained gravity model (equation (6)) with the specific impedance function f_ij = e^(βt_ij ). In other words, the “ad hoc” gravity model, “properly specified” is the statistically most likely model of a trip O-D matrix, given known constraints. This provides very strong theoretical support for “gravity-like” spatial interaction models. Other important points to note include: A specific entropy model specification is determined by the choice of constraints imposed on the model. The general procedure for specifying an entropy model is defined below. Arbitrarily complex specifications can be generated, providing that an appropriate constraint set can be specified. In particular, the impedance functional form derives from the constraint(s) written concerning transportation level-of-service variables. In the example above, imposing the constraint that the predicted system-wide average travel should equal the observed average time in the base data yields a negative exponential impedance function. If instead, one wrote a constraint in which the predicted average of ln(Tij) equals the observed average value, then the resulting impedance function would take the form of a negative power function (tij)-b.

## Random Utility Models

By far the most common type of destination choice model used in practice is some form of random utility model, usually a multinomial logit model or a nested logit model (e.g., a nested destination-mode choice model). Random utility (discrete choice) models are used throughout travel demand modeling given their strong theoretical foundations in microeconomic theory and their practical and efficient analytical function forms.

A typical logit destination choice model for the probability that destination j is chosen given trip origin i (Pj|i) is often generically expressed as: P_(j|i) =e^(V_(j|i) )/(∑_j'▒e^(V_(j^' |i) ) ) (12)

where Vj|i is the systematic utility of destination j given origin i. Logit destination choice models are widely used for a variety of reasons including: Flexibility in specifying the utility function (any relevant variable can be readily included). Readily available parameter estimation software. Familiarity with the method. Computational efficiency. Support for both disaggregate (person-level) and aggregate (trip flows) formulations.

Detailed discussion of the specification and use of logit destination choice models is provided on many other pages throughout this wiki.

Mathematical Equivalence of Gravity, Entropy and Logit Models

It is commonplace in the literature to state that “destination choice” (i.e., disaggregate logit) models are superior in performance to “gravity models”. This, however, is a somewhat misleading statement in that it reflects the common practice in terms of how “gravity” and “logit” models are typically implemented, rather than fundamental differences in the mathematics of the two approaches. In practice, “gravity” models are often aggregate (based on O-D flows instead of individual trips) and very simply specified in terms of both attraction/size variables and impendence functions (including sometimes the use of distance rather than travel times). “Logit” models, on the other hand, are usually disaggregate (based on individual trips) and can have an extensive set of explanatory attraction variables in the utility function. Given this typically more extensive set of explanatory variables, it is not surprising that such “logit” models outperform the more simply specified “gravity” models.

But, as Anas (1983)[2] first observed, “gravity” models as derived through entropy maximization can be formulated at the disaggregate (individual trip) level as well, and can incorporate any number of explanatory variables. In particular, any linear-in-the-parameters utility function typically used in logit destination choice models can be replicated in an entropy model. Further, if consistently defined at the same level of aggregation, the same set of explanatory variables and the same base data are used for parameter estimation, then it can be shown that the estimated parameters for the two models will be identical. Thus, logit and entropy (gravity) models are, in fact, not different models but are mathematically the same model.

As a simple illustration of this, equation (4) can be rearranged to yield:

T_ij= O_i {X_j f_ij/∑_j'▒〖X_j' f_ij' 〗} = O_i P_(j|) where: P_(j|i) =(X_j f_ij)/(∑_(j^')▒〖X_(j^' ) f_(ij^' ) 〗)=e^(ln⁡(X_j )+ln⁡(f_ij ) )/(∑_j'▒e^(ln⁡(X_j' )+ln⁡(f_ij' ) ) ) (13)

If we assume that: f_ij= e^(βt_ij ) then equation (13) becomes: P_(j|i) =e^(ln⁡(X_j )+ βt_ij )/(∑_j'▒e^(ln⁡(X_j' )+ βt_ij' ) ) (14)

Equation (14) is a simple logit destination choice model.

This mathematical equivalency with entropy models only holds for multinomial logit models, not for random utility models in general. The ability to theoretically derive logit models from two very different starting points, one behavioral (people choose alternatives so as to maximize their personal utility) and one statistical (deriving most likely choice probabilities given known constraints on these probabilities), however, is striking and arguably reinforces the case for use of logit models in applications where the underlying assumptions of the model (e.g., statistical independence of the alternatives) holds.

## Other Destination Choice Model Formulations

Historically, other approaches to destination choice models have been developed, including intervening opportunities models and competing opportunities models. In general, these approaches tend to be computationally more intensive without generating improved fits to observed data than more conventional methods and so are rarely used in current practice. Brief descriptions of these methods are provided here for historical documentation.

### Intervening Opportunities Models

Eric Miller to provide.

### Competing Opportunities Models

Eric Miller to provide.

## Doubly-Constrained Gravity/Entropy Models

### Gravity Formulation

Given observed or predicted trip origins, Oi and destinations, Dj, for a set of zones, the spatial interaction modeling problem is to predict the origin-destination trips, Tij, between every origin zone i and destination zone j. The predicted trips must satisfy the following two constraints:

∑_j'▒T_ij' = O_i ∀ i (15) ∑_i'▒T_i'j = D_j ∀ j (16)

If we assume that these trips are proportional to a zone-to-zone impedance function, fij, then the following gravity model will always satisfy constraint (15);

T_ij=O_i D_j f_ij/∑_(j^')▒D_(j^' ) f_(ij^' ) (17)

Equation (17), however, will not satisfy constraint (16) except, perhaps, in the most trivial cases. The only way that a spatial interaction model can satisfy both the “row constraints” (15) and the “column constraints” (16) is through an iterative solution procedure in which the actual “attraction term” (Dj) is replaced by a “modified attraction term” Dj*,k :

D_j^(*,k+1) = D_j^(*,k) (D_j/∑_i▒T_ij^k ) (18.1) D_j^(*,0)= D_j (18.2)

T_ij^(k+1)=O_i D_j^(*,k) f_(ij )/ ∑_(j^')▒D_(j^')^(*,k) f_(ij^' ) (19)

Where T_ij^k is the predicted trips from zone i to zone j in the kth iteration and the procedure iterates until: (D_j/∑_i▒T_ij^k ) ≤ ϵ ∀ j (20)

### Entropy Formulation

The equivalent entropy formulation involves solving the following mathematical program:

max┬T⁡∑_i▒∑_j▒〖T_ij ln⁡(T_ij 〗) (21) Subject to: Constraints (15) and (16)

(∑_i▒〖∑_j▒T_ij t_ij 〗)/T= t ̅ ∀ i,j (22)

Using the method of Lagrange to maximize (21) subject to the equality constraints (15), (16) and (22) eventually yields the solution:

T_ij = A_i B_j O_i D_j e^(βt_ij ) (23)

where  ( < 0) is an estimated parameter and Ai and Bj are “balancing factors” that are iteratively defined so that constraints (3) and (5) are both satisfied:

A_i =1 /∑_(j^')▒B_(j^' ) D_(j^' ) e^(βt_ij' ) (10.1)

B_j =1 /∑_(i^')▒A_(ij^' ) O_(ij^' ) e^(βt_i'j ) (10.2)

To numerically compute the balancing factors, the Bj terms can be initialized to 1.0, the Ai terms can be computed given these Bj’s, and the algorithm iterates until the factors converge to stable values.

A common criticism of doubly-constrained gravity models is the supposedly ad hoc nature of the balancing procedure using the “modified attraction terms” described above. As shown by the entropy model formulation, however, a doubly-constrained matrix can only be computed iteratively: no analytical closed-form solution is possible. Further, with manipulation, it can be shown that BjDj = Dj* , the “modified attraction term” in the gravity model formulation, equation (19). Hence the gravity model balancing procedure is not, in fact “ad hoc” but rather the correct method for computing a doubly-constrained matrix.

## Estimating Gravity/Entropy Model Parameters

Various ad hoc procedures are sometimes used to estimate gravity model parameters. Given the entropy interpretation of the gravity model, however, the method for parameter estimation is unambiguous: parameters must be chosen so that the underlying constraints of the model hold. For example, for the simple doubly-constrained model given by equation (23) the parameter  must be chosen so that associated constraint generating this parameter, equation (22) holds. This problem can be solved using the standard Newton-Raphson root-finding method to find the value of  that satisfies equation (22).

Further, in the case of singly-constrained models gravity/entropy models the set of constraints generating the set of parameters to be estimated are exactly the set of equations defining the first-order conditions for maximizing the long-likelihood function for the corresponding multinomial logit model. Thus, standard logit model parameter estimation procedures can be used.

# References

{{Content Charrette: Destination Choice Models]]

1. Wilson, A.G., “A Statistical Theory of Spatial Distribution Models”, Chapter 3 in R. Quandt (ed) The Demand for Travel: Theory and Measurement, Lexington, Mass: Lexington Books, 1970, . 55-82.
2. Anas, A., “Discrete choice theory, information theory, and the multinomial logit and gravity models”, Transportation Research B 17, 1983, 13-23.