Furness-Algorithmus
Der Furness-Algorithmus ist ein von K. P. Furness entwickeltes iteratives Optimierungsverfahren zur Lösung konvexer Optimierungsprobleme mit Minimierung der Entropie.<ref>Professur für Theorie der Verkehrsplanung, TU Dresden:„Ermittlung von Verkehrsströmen mit n-linearen Gleichungssystemen unter Beachtung von Nebenbedingungen einschließlich Parameterschätzung (Verkehrsnachfragemodellierung: Erzeugung, Verteilung, Aufteilung)“ S. 97 (Seite nicht mehr abrufbar, festgestellt im März 2021. Suche im Internet Archive ) (PDF-Datei; 1,50 MB)</ref>
Verkehrsplanung
In der Verkehrsplanung wird der Furness-Algorithmus zur Umlegung von Verkehrsstrom-Matrizen mit unelastischen Randsummenbedingungen benutzt. In diesen Matrizen sind das Quellverkehrsaufkommen <math>Q_i</math>, das Zielverkehrsaufkommen <math>Z_i</math> und das Gesamtverkehrsaufkommen der einzelnen Verkehrsmodi <math>A_k</math> bekannt.
Grundmodell der Zielwahl
Nach dem Grundmodell der Zielwahl wird die Verkehrsmenge von <math>i</math> nach <math>j</math> mit dem Modus <math>k</math> berechnet sich hierbei aus der Multiplikation der Bewertungsfunktion mit den Faktoren für <math>i</math>, <math>j</math> und <math>k</math>. <math>v_{i,j,k}=B_{i,j,k} \cdot fq_i \cdot fz_j \cdot fa_k</math>
Das Quellverkehrsaufkommen von <math>i</math> ausgehend sei definiert als
- <math>Q_i=\sum_j \sum_k {v_{i,j,k}}.</math>
Das Zielverkehrsaufkommen nach <math>j</math> gehend sei definiert als
- <math>Z_j=\sum_i \sum_k {v_{i,j,k}}.</math>
Das Verkehrsaufkommen eines Verkehrsmodus <math>k</math> sei definiert als
- <math>A_k=\sum_i \sum_j {v_{i,j,k}}.</math>
Furness-Algorithmus
Die Faktoren <math>fq_i</math>,<math>fz_j</math> und <math>fa_k</math> werden iterativ mit dem Furness-Algorithmus berechnet:
Zu Beginn werden alle Faktoren auf 1 gesetzt. <math>fq_i(0)=fz_j(0)=fa_k(0)=1</math>
Anschließend wird der Quellverkehrsfaktor <math>fq_i (p+1)</math> wie folgt berechnet: <math>fq_i (p+1)=\frac{Q_i}{\sum_j \sum_k {B_{i,j,k} \cdot fz_j(p) \cdot fa_k(p)}}</math>
Dieser Faktor wird zur Berechnung des Zielverkehrsfaktor <math>fz_j (p+1)</math> benutzt:<math>fz_j (p+1)=\frac{Z_j}{\sum_i \sum_k {B_{i,j,k} \cdot fq_i(p+1) \cdot fa_k(p)}}</math>
Im dritten Schritt werden diese beiden Faktoren zur Berechnung des Modusfaktors <math>fa_k (p+1)</math> benutzt:<math>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)}}</math>
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:
<math> \begin{matrix} & & & V_j & & \sum\\ & & 1 & 2 & 3& \\ & 1& ? & ? & ?& 25\\ Q_i& 2& ? & ? & ? & 75\\
& 3 & ? & ? & ?&200\\
\sum & & 50 & 100 & 150 & 300 \end{matrix}</math>
und folgende Bewertungsmatrix:
<math> \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}</math>
Im ersten Schritt berechne man nun <math>f_\text{q1}(1),f_\text{q2}(1)</math> und <math>f_\text{q3}(1)</math>:
<math>f_\text{q1}(1)=\frac{25}{0{,}5*1+0{,}75*1+0{,}25*1}=16{,}667</math>
<math>f_\text{q2}(1)=\frac{75}{0{,}75*1+0{,}5*1+1*1}=33{,}333</math>
<math>f_\text{q3}(1)=\frac{200}{0{,}25*1+1*1+0{,}5*1}=114{,}286</math>
Im zweiten Schritt berechne man nun <math>f_\text{z1}(1),f_\text{z2}(1)</math> und <math>f_\text{z3}(1)</math>:
<math>f_\text{z1}(1)=\frac{50}{0{,}5*16{,}667+0{,}75*33{,}333+0{,}25*114{,}286}=0{,}808</math>
<math>f_\text{z2}(1)=\frac{100}{0{,}75*16{,}667+0{,}5*33{,}333+1*114{,}286}=0{,}697</math>
<math>f_\text{z3}(1)=\frac{150}{0{,}25*16{,}667+1*33{,}333+0{,}5*114{,}286}=1{,}585</math>
Aus diesen Faktoren berechne man nun die erste Aufteilung der Verkehrsströme nach folgendem Muster: <math>v_\text{2,1}=B_\text{2,1}*fq_\text{2,1}*_\text{2,1}=0{,}75*33{,}333*0{,}808=20{,}2</math>
<math> \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}</math>
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:
<math> \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}</math>
mit <math>f_\text{q1}(2)=18{,}896</math>, <math>f_\text{q2}(2)=29{,}533</math> und <math>f_\text{q3}(2)=118{,}238</math>, sowie <math>f_\text{z1}(2)=0{,}818</math>, <math>f_\text{z3}(2)=0{,}679</math> und <math>f_\text{z3}(2)=1{,}606</math>.
Einzelnachweise
<references />