imported>APPERbot: Bot: Fix Vorlage Toter Link, siehe Wikipedia:Bots/Anfragen#Ersetzen_von_Toter_Link_inline=ja

2023-06-06T19:38:17Z

Bot: Fix Vorlage Toter Link, siehe Wikipedia:Bots/Anfragen#Ersetzen_von_Toter_Link_inline=ja

Neue Seite

Der '''Furness-Algorithmus''' ist ein von K. P. Furness entwickeltes iteratives [[Optimierung (Mathematik)|Optimierungsverfahren]] zur Lösung [[Konvexe Optimierung|konvexer Optimierungsprobleme]] mit Minimierung der [[Entropie (Informationstheorie)|Entropie]].<ref>{{Toter Link |date=2021-03-05 |url=http://vplno1.vkw.tu-dresden.de/vpl/viseva/Download/Heft-5.pdf |text=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 }} (PDF-Datei; 1,50 MB)</ref>

== Verkehrsplanung ==
In der [[Verkehrsplanung]] wird der Furness-Algorithmus zur Umlegung von [[Verkehrsstrom]]-[[Matrix (Mathematik)|Matrizen]] mit [[Elastizität (Wirtschaft)|unelastischen]] [[Randverteilung|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 [[Zielwahlmodell|Grundmodell der Zielwahl]] wird die [[Verkehrsmenge]] von <math>i</math> nach <math>j</math> mit dem [[Verkehrsmittel|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 [[Iteration|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 />

[[Kategorie:Verkehrsprognose]]
[[Kategorie:Konvexe Optimierung]]

Furness-Algorithmus - Versionsgeschichte

imported>APPERbot: Bot: Fix Vorlage Toter Link, siehe Wikipedia:Bots/Anfragen#Ersetzen_von_Toter_Link_inline=ja