Furness algorithm

The Furness algorithm is an iterative optimization method developed by KP Furness to solve convex optimization problems while minimizing entropy .

Traffic planning

In the traffic planning of Furness algorithm for assignment of is traffic flow - matrices with inelastic edge sum conditions used. The source traffic volume , the target traffic volume and the total traffic volume of the individual traffic modes are known in these matrices . ${\displaystyle Q_{i}}$ ${\displaystyle Z_{i}}$ ${\displaystyle A_{k}}$

Basic model of target choice

According to the basic model of destination selection , the traffic volume from to with the mode is calculated here by multiplying the evaluation function with the factors for , and . ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle v_{i,j,k}=B_{i,j,k}\cdot fq_{i}\cdot fz_{j}\cdot fa_{k}}$

The source traffic volume from the starting point is defined as ${\displaystyle i}$

${\displaystyle Q_{i}=\sum _{j}\sum _{k}{v_{i,j,k}}.}$

The target traffic volume behind is defined as ${\displaystyle j}$

${\displaystyle Z_{j}=\sum _{i}\sum _{k}{v_{i,j,k}}.}$

The traffic volume of a traffic mode is defined as ${\displaystyle k}$

${\displaystyle A_{k}=\sum _{i}\sum _{j}{v_{i,j,k}}.}$

Furness algorithm

The factors , and are calculated iteratively with the Furness algorithm: ${\displaystyle fq_{i}}$ ${\displaystyle fz_{j}}$ ${\displaystyle fa_{k}}$

At the beginning, all factors are set to 1. ${\displaystyle fq_{i}(0)=fz_{j}(0)=fa_{k}(0)=1}$

The source traffic factor is then calculated as follows: ${\displaystyle fq_{i}(p+1)}$ ${\displaystyle fq_{i}(p+1)={\frac {Q_{i}}{\sum _{j}\sum _{k}{B_{i,j,k}\cdot fz_{j}(p)\cdot fa_{k}(p)}}}}$

This factor is used to calculate the destination traffic factor : ${\displaystyle fz_{j}(p+1)}$ ${\displaystyle fz_{j}(p+1)={\frac {Z_{j}}{\sum _{i}\sum _{k}{B_{i,j,k}\cdot fq_{i}(p+1)\cdot fa_{k}(p)}}}}$

In the third step, these two factors are used to calculate the mode factor : ${\displaystyle fa_{k}(p+1)}$ ${\displaystyle fa_{k}(p+1)={\frac {A_{k}}{\sum _{i}\sum _{j}{B_{i,j,k}\cdot fq_{i}(p+1)\cdot fz_{j}(p+1)}}}}$

These factors are then used for the next iteration step.

example

Note: For simplicity, only one mode is calculated.

The following source-destination matrix is ​​given:

${\displaystyle {\begin{matrix}&&&V_{j}&&\sum \\&&1&2&3&\\&1&?&?&?&25\\Q_{i}&2&?&?&?&75\\&3&?&?&?&200\\\sum &&50&100&150&300\end{matrix}}}$

and the following evaluation matrix:

${\displaystyle {\begin{matrix}B_{\text{i,j}}&1&2&3&\\1&0{,}5&0{,}75&0{,}25\\2&0{,}75&0{,}5&1\\3&0{,}25&1&0{,}5\\\end{matrix}}}$

In the first step you now calculate and : ${\displaystyle f_{\text{q1}}(1),f_{\text{q2}}(1)}$ ${\displaystyle f_{\text{q3}}(1)}$

${\displaystyle f_{\text{q1}}(1)={\frac {25}{0{,}5*1+0{,}75*1+0{,}25*1}}=16{,}667}$

${\displaystyle f_{\text{q2}}(1)={\frac {75}{0{,}75*1+0{,}5*1+1*1}}=33{,}333}$

${\displaystyle f_{\text{q3}}(1)={\frac {200}{0{,}25*1+1*1+0{,}5*1}}=114{,}286}$

In the second step you now calculate and : ${\displaystyle f_{\text{z1}}(1),f_{\text{z2}}(1)}$ ${\displaystyle f_{\text{z3}}(1)}$

${\displaystyle f_{\text{z1}}(1)={\frac {50}{0{,}5*16{,}667+0{,}75*33{,}333+0{,}25*114{,}286}}=0{,}808}$

${\displaystyle f_{\text{z2}}(1)={\frac {100}{0{,}75*16{,}667+0{,}5*33{,}333+1*114{,}286}}=0{,}697}$

${\displaystyle f_{\text{z3}}(1)={\frac {150}{0{,}25*16{,}667+1*33{,}333+0{,}5*114{,}286}}=1{,}585}$

From these factors, calculate the first division of the traffic flows according to the following pattern: ${\displaystyle v_{\text{2,1}}=B_{\text{2,1}}*fq_{\text{2,1}}*_{\text{2,1}}=0{,}75*33{,}333*0{,}808=20{,}2}$

${\displaystyle {\begin{matrix}&&&V_{j}&&\sum _{\text{ber}}&\sum _{\text{geg}}\\&v_{\text{i,j}}&1&2&3&&\\&1&6{,}7&8{,}7&6{,}6&22{,}1&25\\Q_{i}&2&20{,}2&11{,}6&52{,}8&84{,}6&75\\&3&23{,}1&79{,}7&90{,}6&193{,}3&200\\\sum _{\text{ber}}&&50{,}0&100{,}0&150{,}0&300\\\sum _{\text{geg}}&&50&100&150&&300\\\end{matrix}}}$

After the first step, the marginal sums of the target page are adhered to very precisely. However, the marginal sums of the source side still deviate significantly from the specifications of the source-target matrix. After a further step, however, this will be observed much more precisely:

${\displaystyle {\begin{matrix}&&&V_{j}&&\sum _{\text{ber}}&\sum _{\text{geg}}\\&v_{\text{i,j}}&1&2&3&&\\&1&7{,}7&9{,}6&7{,}6&24{,}9&25\\Q_{i}&2&18{,}1&10{,}0&47{,}4&75{,}6&75\\&3&24{,}2&80{,}3&94{,}9&199{,}4&200\\\sum _{\text{ber}}&&50{,}0&99{,}9&150{,}0&300\\\sum _{\text{geg}}&&50&100&150&&300\\\end{matrix}}}$

with , and , as well as , and . ${\displaystyle f_{\text{q1}}(2)=18{,}896}$ ${\displaystyle f_{\text{q2}}(2)=29{,}533}$ ${\displaystyle f_{\text{q3}}(2)=118{,}238}$ ${\displaystyle f_{\text{z1}}(2)=0{,}818}$ ${\displaystyle f_{\text{z3}}(2)=0{,}679}$ ${\displaystyle f_{\text{z3}}(2)=1{,}606}$

Individual evidence

1. ↑ Professorship for Theory of Transport Planning, TU Dresden: "Determination of traffic flows with n-linear systems of equations taking into account constraints including parameter estimation (traffic demand modeling: generation, distribution, division)" p. 97  ( page no longer available , search in web archives )  Info: The link was automatically marked as broken. Please check the link according to the instructions and then remove this notice. (PDF file; 1.50 MB)