# Fundamentals of Transportation/Destination Choice

Everything is related to everything else, but near things are more related than distant things. - Waldo Tobler's 'First Law of Geography’
Destination Choice (or trip distribution or zonal interchange analysis), is the second component (after Trip Generation, but before Mode Choice and Route Choice) in the traditional four-step transportation forecasting model. This step matches tripmakers’ origins and destinations to develop a “trip table”, a matrix that displays the number of trips going from each origin to each destination. Historically, trip distribution has been the least developed component of the transportation planning model.
Table: Illustrative Trip Table :
| Origin \ Destination | 1 | 2 | 3 | Z |
| 1 | T$_{11}$ | T$_{12}$ | T$_{13}$ | T$_{1Z}$ |
| 2 | T$_{21}$ | | | |
| 3 | T$_{31}$ | | | |
| Z | T$_{Z1}$ | | | T$_{ZZ}$ |
Where: $T_{ij}\,\!$ = Trips from origin i to destination j.
Work trip distribution is the way that travel demand models understand how people take jobs. There are trip distribution models for other (non-work) activities, which follow the same structure.

## Fratar Models

The simplest trip distribution models (Fratar or Growth models) simply extrapolate a base year trip table to the future based on growth, $T_{ij,y+1}=g*T_{ij,y}\,\!$
where:
* $T_{ij,y}\,\!$ - Trips from $i$ to $j$ in year $y$
* $g\,\!$ - growth factor
Fratar Model takes no account of changing spatial accessibility due to increased supply or changes in travel patterns and congestion.

## Gravity Model

The gravity model illustrates the macroscopic relationships between places (say homes and workplaces). It has long been posited that the interaction between two locations declines with increasing (distance, time, and cost) between them, but is positively associated with the amount of activity at each location (Isard, 1956). In analogy with physics, Reilly (1929) formulated Reilly's law of retail gravitation, and J. Q. Stewart (1948) formulated definitions of demographic gravitation, force, energy, and potential, now called accessibility (Hansen, 1959). The distance decay factor of $distance^{-1}$ has been updated to a more comprehensive function of generalized cost, which is not necessarily linear - a negative exponential tends to be the preferred form. In analogy with Newton’s law of gravity, a gravity model is often used in transportation planning.
The gravity model has been corroborated many times as a basic underlying aggregate relationship (Scott 1988, Cervero 1989, Levinson and Kumar 1995). The rate of decline of the interaction (called alternatively, the impedance or friction factor, or the utility or propensity function) has to be empirically measured, and varies by context.
Limiting the usefulness of the gravity model is its aggregate nature. Though policy also operates at an aggregate level, more accurate analyses will retain the most detailed level of information as long as possible. While the gravity model is very successful in explaining the choice of a large number of individuals, the choice of any given individual varies greatly from the predicted value. As applied in an urban travel demand context, the disutilities are primarily time, distance, and cost, although discrete choice models with the application of more expansive utility expressions are sometimes used, as is stratification by income or auto ownership.
Mathematically, the gravity model often takes the form:
$T_{ij}=r_{i}s_{j}T_{O,i}T_{D,j}f(C_{ij})\,\!$
$\sum _{j}{T_{ij}=T_{O,i}},\sum _{i}{T_{ij}=T_{D,j}}\,\!$
$r_{i}=({\sum _{j}{s_{j}T_{D,j}f(C_{ij})}})^{-1}\,\!$
$s_{j}=({\sum _{i}{r_{i}T_{O,i}f(C_{ij})}})^{-1}\,\!$
where
* $T_{ij}\,\!$ = Trips between origin $i$ and destination $j$
* $T_{O,i}\,\!$ = Trips originating at $i$
* $T_{D,j}\,\!$ = Trips destined for $j$
* $C_{ij}\,\!$ = travel cost between $i$ and $j$
* $r_{i},s_{j}\,\!$ = balancing factors solved iteratively.
* $f\,\!$ = impedance or distance decay factor
It is doubly constrained so that Trips from $i$ to $j$ equal number of origins and destinations.

## Balancing a matrix

Balancing a matrix can be done using what is called the Furness Method, summarized and generalized below.
1. Assess Data, you have $T_{O,i}\,\!$,$T_{D,j}\,\!$, $C_{ij}\,\!$
2. Compute $f(Cij)\,\!$, e.g.
* $f(C_{ij})=C_{ij}^{-2}\,\!$
* $f(C_{ij})=e^{-\beta C_{ij}}\,\!$
3. Iterate to Balance Matrix
(a) Multiply Trips from Zone $i\,\!$ ($T_{i}\,\!$) by Trips to Zone $j\,\!$ ($T_{j}\,\!$) by Impedance in Cell $ij\,\!$ ($f(C_{ij})\,\!$) for all $ij\,\!$
(b) Sum Row Totals $T'_{O,i}\,\!$, Sum Column Totals $T'_{D,j}\,\!$
(c) Multiply Rows by $N_{O,i}=T_{O,i}/T'_{O,i}\,\!$
(d) Sum Row Totals $T'_{O,i}\,\!$, Sum Column Totals $T'_{D,j}\,\!$
(e) Compare $T_{O,i}\,\!$ and $T'_{O,i}\,\!$, $T_{D,j}\,\!$ $T'_{D,j}\,\!$ if within tolerance stop, Otherwise goto (f)
(f) Multiply Columns by $N_{D,j}=T_{D,j}/T'_{D,j}\,\!$
(g) Sum Row Totals $T'_{O,i}\,\!$, Sum Column Totals $T'_{D,j}\,\!$
(h) Compare $T_{O,i}\,\!$ and $T'_{O,i}\,\!$, $T_{D,j}\,\!$ and $T'_{D,j}\,\!$ if within tolerance stop, Otherwise goto (b)

## Issues
### Feedback

One of the key drawbacks to the application of many early models was the inability to take account of congested travel time on the road network in determining the probability of making a trip between two locations. Although Wohl noted as early as 1963 research into the feedback mechanism or the “interdependencies among assigned or distributed volume, travel time (or travel ‘resistance’) and route or system capacity”, this work has yet to be widely adopted with rigorous tests of convergence or with a so-called “equilibrium” or “combined” solution (Boyce et al. 1994). Haney (1972) suggests internal assumptions about travel time used to develop demand should be consistent with the output travel times of the route assignment of that demand. While small methodological inconsistencies are necessarily a problem for estimating base year conditions, forecasting becomes even more tenuous without an understanding of the feedback between supply and demand. Initially heuristic methods were developed by Irwin and Von Cube (as quoted in Florian et al. (1975) ) and others, and later formal mathematical programming techniques were established by Evans (1976).

### Feedback and time budgets

A key point in analyzing feedback is the finding in earlier research by Levinson and Kumar (1994) that commuting times have remained stable over the past thirty years in the Washington Metropolitan Region, despite significant changes in household income, land use pattern, family structure, and labor force participation. Similar results have been found in the Twin Cities by Barnes and Davis (2000).
The stability of travel times and distribution curves over the past three decades gives a good basis for the application of aggregate trip distribution models for relatively long term forecasting. This is not to suggest that there exists a constant travel time budget.
In terms of time budgets:
* 1440 Minutes in a Day
* Time Spent Traveling: ~ 100 minutes + or -
* Time Spent Traveling Home to Work: 20 – 30 minutes + or -
Research has found that auto commuting times have remained largely stable over the past forty years, despite significant changes in transportation networks, congestion, household income, land use pattern, family structure, and labor force participation. The stability of travel times and distribution curves gives a good basis for the application of trip distribution models for relatively long term forecasting.

## Examples
### Example 1: Solving for impedance

You are given the travel times between zones, compute the impedance matrix $f(C_{ij})\,\!$, assuming $f(C_{ij})=C_{ij}^{-2}\,\!$.
Travel Time OD Matrix ($C_{ij}\,\!$) :
| Origin Zone | Destination Zone 1 | Destination Zone 2 |
| 1 | 2 | 5 |
| 2 | 5 | 2 |
Compute impedances ($f(C_{ij})\,\!$)
Impedance Matrix ($f(C_{ij})\,\!$) :
| Origin Zone | Destination Zone 1 | Destination Zone 2 |
| 1 | ${\frac {1}{2^{2}}}=0.25\,\!$ | ${\frac {1}{5^{2}}}=0.04\,\!$ |
| 2 | ${\frac {1}{5^{2}}}=0.04\,\!$ | ${\frac {1}{2^{2}}}=0.25\,\!$ |

### Example 2: Balancing a Matrix Using Gravity Model

You are given the travel times between zones, trips originating at each zone (zone1 =15, zone 2=15) trips destined for each zone (zone 1=10, zone 2 = 20) and asked to use the classic gravity model $f(C_{ij})=C_{ij}^{-2}\,\!$
Travel Time OD Matrix ($C_{ij}$) :
| Origin Zone | Destination Zone 1 | Destination Zone 2 |
| 1 | 2 | 5 |
| 2 | 5 | 2 |
(a) Compute impedances ($f(C_{ij})$)
Impedance Matrix ($f(C_{ij})$) :
| Origin Zone | Destination Zone 1 | Destination Zone 2 |
| 1 | 0.25 | 0.04 |
| 2 | 0.04 | 0.25 |
(b) Find the trip table
Balancing Iteration 0 (Set-up) :
| Origin Zone | Trips Originating | Destination Zone 1 | Destination Zone 2 |
| Trips Destined | | 10 | 20 |
| 1 | 15 | 0.25 | 0.04 |
| 2 | 15 | 0.04 | 0.25 |
Balancing Iteration 1 ($T_{ij,iteration1}=T_{O,i}T_{D,j}f(C_{ij})$) :
| Origin Zone | Trips Originating | Destination Zone 1 | Destination Zone 2 | Row Total $T'_{O,i}$ | Normalizing Factor $N_{O,i}=T_{O,i}/T'_{O,i}$ |
| Trips Destined | | 10 | 20 |
| 1 | 15 | 37.50 | 12 | 49.50 | 0.303 |
| 2 | 15 | 6 | 75 | 81 | 0.185 |
| Column Total | | 43.50 | 87 |
Balancing Iteration 2 ($T_{ij,iteration2}=T_{ij,iteration1}*N_{O,i,iteration1}$) :
| Origin Zone | Trips Originating | Destination Zone 1 | Destination Zone 2 | Row Total $T'_{O,i}$ | Normalizing Factor $N_{O,i}=T_{O,i}/T'_{O,i}$ |
| Trips Destined | | 10 | 20 |
| 1 | 15 | 11.36 | 3.64 | 15.00 | 1.00 |
| 2 | 15 | 1.11 | 13.89 | 15.00 | 1.00 |
| Column Total | | 12.47 | 17.53 |
| Normalizing Factor $N_{D,j}=T_{D,j}/T'_{D,j}$ | | 0.802 | 1.141 |
Balancing Iteration 3 ($T_{ij,iteration3}=T_{ij,iteration2}*N_{D,j,iteration2}$) :
| Origin Zone | Trips Originating | Destination Zone 1 | Destination Zone 2 | Row Total $T'_{O,i}$ | Normalizing Factor $N_{O,i}=T_{O,i}/T'_{O,i}$ |
| Trips Destined | | 10 | 20 |
| 1 | 15 | 9.11 | 4.15 | 13.26 | 1.13 |
| 2 | 15 | 0.89 | 15.85 | 16.74 | 0.90 |
| Column Total | | 10.00 | 20.00 |
| Normalizing Factor = $N_{D,j}=T_{D,j}/T'_{D,j}$ | | 1.00 | 1.00 |
Balancing Iteration 4 ($T_{ij,iteration4}=T_{ij,iteration3}*N_{O,i,iteration3}$) :
| Origin Zone | Trips Originating | Destination Zone 1 | Destination Zone 2 | Row Total $T'_{O,i}$ | Normalizing Factor $N_{O,i}=T_{O,i}/T'_{O,i}$ |
| Trips Destined | | 10 | 20 |
| 1 | 15 | 10.31 | 4.69 | 15.00 | 1.00 |
| 2 | 15 | 0.80 | 14.20 | 15.00 | 1.00 |
| Column Total | | 11.10 | 18.90 |
| Normalizing Factor = $N_{D,j}=T_{D,j}/T'_{D,j}$ | | 0.90 | 1.06 |
Balancing Iteration 16 ($T_{ij,iteration16}=T_{ij,iteration15}*N_{D,i,iteration5}$) :
| Origin Zone | Trips Originating | Destination Zone 1 | Destination Zone 2 | Row Total $T'_{O,i}$ | Normalizing Factor $N_{O,i}=T_{O,i}/T'_{O,i}$ |
| Trips Destined | | 10 | 20 |
| 1 | 15 | 9.39 | 5.61 | 15.00 | 1.00 |
| 2 | 15 | 0.62 | 14.38 | 15.00 | 1.00 |
| Column Total | | 10.01 | 19.99 |
| Normalizing Factor = $N_{D,j}=T_{D,j}/T'_{D,j}$ | | 1.00 | 1.00 |
So while the matrix is not strictly balanced, it is very close, well within a 1% threshold, after 16 iterations. The threshold refers to the proximity of the normalizing factor to 1.0.

## Additional Questions

* Homework
* Additional Questions

## Variables

* $T_{O,i}$ - Trips leaving origin $i$
* $T_{D,j}$ - Trips arriving at destination $j$
* $T'_{D,j}$ - Effective Trips arriving at destination $j$, computed as a result for calibration to the next iteration
* $T_{ij}$ - Total number of trips between origin $i$ and destination $j$
* $r_{i}$ - Calibration parameter for Origins
* $s_{j}$ - Calibration parameter for Destinations
* $f(C_{ij})$ - Cost function between origin $i$ and destination $j$

## Further reading

* Background
* A.W. Evans (1970) "Some properties of trip distribution methods". Transportation Research Volume 4, Issue 1, April 1970, Pages 19–36

## Videos

* Destination Choice
* Matrix Math
* Solving for Impedance
* Balancing a Matrix