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 f{q}_i\cdot f{z}_j\cdot f{a}_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 $f{q}_i$,$f{z}_j$ und $f{a}_k$ werden iterativ mit dem Furness-Algorithmus berechnet:

Zu Beginn werden alle Faktoren auf 1 gesetzt. $f{q}_i(0)=f{z}_j(0)=f{a}_k(0)=1$

Anschließend wird der Quellverkehrsfaktor $f{q}_i(p+1)$ wie folgt berechnet: $f{q}_i(p+1)=\frac{Q_i}{\sum _j\sum _k{B}_{i,j,k}\cdot f{z}_j(p)\cdot f{a}_k(p)}$

Dieser Faktor wird zur Berechnung des Zielverkehrsfaktor $f{z}_j(p+1)$ benutzt:$f{z}_j(p+1)=\frac{Z_j}{\sum _i\sum _k{B}_{i,j,k}\cdot f{q}_i(p+1)\cdot f{a}_k(p)}$

Im dritten Schritt werden diese beiden Faktoren zur Berechnung des Modusfaktors $f{a}_k(p+1)$ benutzt:$f{a}_k(p+1)=\frac{A_k}{\sum _i\sum _j{B}_{i,j,k}\cdot f{q}_i(p+1)\cdot f{z}_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{array}{cccccc}& & & V_j& & \sum \\ & & 1& 2& 3& \\ & 1& ?& ?& ?& 25\\ Q_i& 2& ?& ?& ?& 75\\ & 3& ?& ?& ?& 200\\ \sum & & 50& 100& 150& 300\end{array}$

und folgende Bewertungsmatrix:

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

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}}*f{q}_{\text{2,1}}{*}_{\text{2,1}}=0,75*33,333*0,808=20,2$

$\begin{array}{ccccccc}& & & 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{array}$

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{array}{ccccccc}& & & 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{array}$

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$.