Editing Trip distribution (section)

== Entropy analysis ==

Wilson (1970) gives another way to think about zonal interchange problem.  This section treats Wilson’s methodology to give a grasp of central ideas.

To start, consider some trips where there are seven people in origin zones commuting to seven jobs in destination zones.  One configuration of such trips will be:

{| border="1" cellpadding="5" cellspacing="0" align="center"
|+'''Table: Configuration of trips'''
!zone
!1
!2
!3
|-				
|1	
|2
|1
|1
|-
|2	
|0
|2
|1
|-
|}

: <math>
w\left( {T_{ij} } \right) = \frac{{7!}}
{{2!1!1!0!2!1!}} = 1260
</math>

where 0!&nbsp;=&nbsp;1.

That configuration can appear in 1,260 ways.  We have calculated the number of ways that configuration of trips might have occurred, and to explain the calculation, let’s recall those coin tossing experiments talked about so much in elementary statistics.

The number of ways a two-sided coin can come up is <math>2^n</math>, where n is the number of times we toss the coin.  If we toss the coin once, it can come up heads or tails, <math>2^1 = 2</math>. If we toss it twice, it can come up  HH, HT, TH, or TT, four ways, and <math>2^2 = 4</math>. To ask the specific question about, say, four coins coming up all heads, we calculate <math>4!/(4!0!) = 1</math>.  Two heads and two tails would be <math>4!/(2!2!) = 6</math>. We are solving the equation:

: <math>
w = \frac{{n!}}
{{\prod_{i = 1}^n {n_i !} }}
</math>

An important point is that as ''n'' gets larger, our distribution gets more and more peaked, and it is more and more reasonable to think of a most likely state.

However, the notion of most likely state comes not from this thinking; it comes from statistical mechanics, a field well known to Wilson and not so well known to transportation planners.  The result from statistical mechanics is that a descending series is most likely.  Think about the way the energy from lights in the classroom is affecting the air in the classroom.  If the effect resulted in an ascending series, many of the atoms and molecules would be affected a lot and a few would be affected a little.  The descending series would have many affected not at all or not much and only a few affected very much.  We could take a given level of energy and compute excitation levels in ascending and descending series.  Using the formula above, we would compute the ways particular series could occur, and we would conclude that descending series dominate.

That is more-or-less [[Boltzmann's Law]],

: <math>
p_j  = p_0 e^{\beta e_j } 
</math>

That is, the particles at any particular excitation level ''j'' will be a negative exponential function of the particles in the ground state, <math>p_0</math>, the excitation level, <math>e_j</math>, and a parameter <math>\beta</math>, which is a function of the (average) energy available to the particles in the system.

The two paragraphs above have to do with ensemble methods of calculation developed by Gibbs, a topic well beyond the reach of these notes.

Returning to the O-D matrix, note that we have not used as much information as we would have from an O and D survey and from our earlier work on trip generation.  For the same travel pattern in the O-D matrix used before, we would have row and column totals, i.e.:
{| border="1" cellpadding="5" cellspacing="0" align="center"
|+'''Table: Illustrative O-D matrix with row and column totals'''
!
!zone	
!1
!2
!3
|-
|zone
|''T<sub>i</sub> \T<sub>j</sub>''
|2
|3
|2
|-
|1
|4
|2
|1
|1
|-
|2
|3
|0
|2
|1
|-
|}

Consider the way the four folks might travel, 4!/(2!1!1!) = 12; consider three folks, 3!/(0!2!1!) = 3.  All travel can be combined in 12×3 = 36 ways.  The possible configuration of trips is, thus, seen to be much constrained by the column and row totals.

We put this point together with the earlier work with our matrix and the notion of most likely state to say that we want to

: <math>
\max w\left( {T_{ij} } \right) = \frac{{T!}}
{{\prod_{ij} {T_{ij}!} }} 
</math>

subject to

: <math> 
\sum_j {T_{ij}  = T_i } ;
\sum_i {T_{ij}  = T_j }  
</math>

where:

: <math>
T = \sum_j {\sum_i {T_{ij} } }  = \sum_i {T_i }  = \sum_j {T_j } 
</math>

and this is the problem that we have solved above.

Wilson adds another consideration; he constrains the system to the amount of energy available (i.e., money), and we have the additional constraint,

: <math>
\sum_i {\sum_j {T_{ij} C_{ij}  = C} } 
</math>

where ''C'' is the quantity of resources available and <math>C_{ij}</math> is the travel cost from ''i'' to ''j''.

The discussion thus far contains the central ideas in Wilson’s work, but we are not yet to the place where the reader will recognize the model as it is formulated by Wilson.

First, writing the <math>\Lambda</math> function to be maximized using [[Lagrangian multipliers]], we have:

: <math>
\Lambda(T_{ij},\lambda_i,\lambda_j) = \frac{{T!}}
{{\prod_{ij} {Tij!} }} + \sum_i {\lambda _i \left( {T_i  - \sum_j {T_{ij} } } \right)}  + \sum_j {\lambda _j \left( {T_j  - \sum_i {T_{ij} } } \right) + \beta \left( {C - \sum_i {\sum_j {T_{ij} C_{ij} } } } \right)} 
</math>

where  <math>\lambda_i, \lambda_j</math> and <math>\beta</math> are the Lagrange multipliers, <math>\beta</math> having an energy sense.

Second, it is convenient to maximize the natural log (ln) rather than  <math>w(T_{ij})</math>, for then we may use [[Stirling's approximation]].

: <math>
\ln N! \approx N\ln N - N
</math>

so

: <math>
\frac{{\partial \ln N!}}
{{\partial N}} \approx \ln N
</math>

Third, evaluating the maximum, we have

: <math>
\frac{{\partial \Lambda(T_{ij},\lambda_i,\lambda_j) }}
{{\partial T_{ij} }} =  - \ln T_{ij}  - \lambda _i  - \lambda _j  - \beta C_{ij}  = 0
</math>

with solution

: <math>
\ln T_{ij}  =  - \lambda _i  - \lambda _j  - \beta C_{ij} 
</math>

: <math>
T_{ij}  = e^{ - \lambda _i  - \lambda _j  - \beta C_{ij} } 
</math>

Finally, substituting this value of <math>T_{ij}</math>  back into our constraint equations, we have:

: <math>
\sum_j {e^{ - \lambda _i  - \lambda _j  - \beta C_{ij} } }  = T_i;
\sum_i {e^{ - \lambda _i  - \lambda _j  - \beta C_{ij} } }  = T_j
</math>

and, taking the constant multiples outside of the summation sign

: <math>
e^{ - \lambda _i }  = \frac{{T_i }}
{{\sum_j {e^{ - \lambda _j  - \beta C_{ij} } } }};e^{ - \lambda _j }  = \frac{{T_j }}
{{\sum_i {e^{ - \lambda _i  - \beta C_{ij} } } }}
</math>

Let

: <math>
\frac{{e^{ - \lambda _i } }}
{{T_i }} = A_i ;\frac{{e^{ - \lambda _j } }}
{{T_j }} = B_j 
</math>

we have

: <math>
T_{ij}  = A_i B_j T_i T_j e^{ - \beta C_{ij} } 
</math>

which says that the most probable distribution of trips has a gravity model form, <math>T_{ij}</math> is proportional to trip origins and destinations.  The constants <math>A_i</math>, <math>B_j</math>, and <math>\beta</math> ensure that constraints are met.

Turning now to computation, we have a large problem.  First, we do not know the value of ''C'', which earlier on we said had to do with the money available, it was a cost constraint.  Consequently, we have to set <math>\beta</math> to different values and then find the best set of values for <math>A_i</math> and <math>B_j</math>.  We know what <math>\beta</math> means – the greater the value of <math>\beta</math>, the less the cost of average distance traveled.  (Compare <math>\beta</math> in Boltzmann's Law noted earlier.)  Second, the values of <math>A_i</math> and <math>B_j</math> depend on each other.  So for each value of <math>\beta</math>, we must use an iterative solution.  There are computer programs to do this.

Wilson's method has been applied to the [[Lowry model]].