Furness-Algorithmus

Der Furness-Algorithmus ist ein von K. P. Furness entwickeltes iteratives Optimierungsverfahren zur Lösung konvexer Optimierungsprobleme mit Minimierung der Entropie.

Verkehrsplanung

In der Verkehrsplanung wird der Furness-Algorithmus zur Umlegung von Verkehrsstrom-Matrizen mit unelastischen Randsummenbedingungen benutzt. In diesen Matrizen sind das Quellverkehrsaufkommen $Q_{i}$, das Zielverkehrsaufkommen $Z_{i}$ und das Gesamtverkehrsaufkommen der einzelnen Verkehrsmodi $A_{k}$ bekannt.

Grundmodell der Zielwahl

Nach dem Grundmodell der Zielwahl wird die Verkehrsmenge von $i$ nach $j$ mit dem Modus $k$ berechnet sich hierbei aus der Multiplikation der Bewertungsfunktion mit den Faktoren für $i$, $j$ und $k$. $v_{i,j,k}=B_{i,j,k}\cdot fq_{i}\cdot fz_{j}\cdot fa_{k}$

Das Quellverkehrsaufkommen von $i$ ausgehend sei definiert als

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

Das Zielverkehrsaufkommen nach $j$ gehend sei definiert als

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

Das Verkehrsaufkommen eines Verkehrsmodus $k$ sei definiert als

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

Furness-Algorithmus

Die Faktoren $fq_{i}$,$fz_{j}$ und $fa_{k}$ werden iterativ mit dem Furness-Algorithmus berechnet:

Zu Beginn werden alle Faktoren auf 1 gesetzt. $fq_{i}(0)=fz_{j}(0)=fa_{k}(0)=1$

Anschließend wird der Quellverkehrsfaktor $fq_{i}(p+1)$ wie folgt berechnet: $fq_{i}(p+1)={\frac {Q_{i}}{\sum _{j}\sum _{k}{B_{i,j,k}\cdot fz_{j}(p)\cdot fa_{k}(p)}}}$

Dieser Faktor wird zur Berechnung des Zielverkehrsfaktor $fz_{j}(p+1)$ benutzt:$fz_{j}(p+1)={\frac {Z_{j}}{\sum _{i}\sum _{k}{B_{i,j,k}\cdot fq_{i}(p+1)\cdot fa_{k}(p)}}}$

Im dritten Schritt werden diese beiden Faktoren zur Berechnung des Modusfaktors $fa_{k}(p+1)$ benutzt:$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)}}}$

Diese Faktoren werden anschließend für den nächsten Iterationsschritt verwendet.

Beispiel

Anmerkung: Der Einfachheit halber wird nur ein Modus berechnet.

Gegeben sei folgende Quelle-Ziel-Matrix:

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

und folgende Bewertungsmatrix:

${\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}}$

Im ersten Schritt berechne man nun $f_{\text{q1}}(1),f_{\text{q2}}(1)$ und $f_{\text{q3}}(1)$:

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

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

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

Im zweiten Schritt berechne man nun $f_{\text{z1}}(1),f_{\text{z2}}(1)$ und $f_{\text{z3}}(1)$:

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

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

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

Aus diesen Faktoren berechne man nun die erste Aufteilung der Verkehrsströme nach folgendem Muster: $v_{\text{2,1}}=B_{\text{2,1}}*fq_{\text{2,1}}*_{\text{2,1}}=0{,}75*33{,}333*0{,}808=20{,}2$

${\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}}$

Nach dem ersten Schritt werden die Randsummen der Zielseite bereits sehr genau eingehalten. Die Randsummen der Quellseite weichen jedoch noch deutlich von den Vorgaben der Quelle-Ziel-Matrix ab. Nach einem weiteren Schritt wird diese jedoch schon deutlich genauer eingehalten:

${\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}}$

mit $f_{\text{q1}}(2)=18{,}896$, $f_{\text{q2}}(2)=29{,}533$ und $f_{\text{q3}}(2)=118{,}238$, sowie $f_{\text{z1}}(2)=0{,}818$, $f_{\text{z3}}(2)=0{,}679$ und $f_{\text{z3}}(2)=1{,}606$.