Microsoft Word - ip38.doc

Size: px

Start display at page:

Download "Microsoft Word - ip38.doc"

さなえつねざき
5 years ago
Views:

1 交通ネットワーク均衡モデル求解アルゴリズムと収束判定 Algorithms for ilibrim Trnsporttion Networ Models nd vltion of Their Convergence rror 井上紳一 By hin-ichi INOU 1. はじめに 2. 収束判定指標利用者均衡配分モデルを代表とする交通ネットワーク均衡モデルは数理問題としては非線形計画問題非線形相補性問題変分不等式問題等として定式化されるこれら問題解を求めるにあたっては一般には解析的に解くことは不可能であり解更新を繰り返しながら均衡状態に近づけて行くいわゆる収束計算による求解法が用いられる収束計算によって厳密な均衡解を得るためには計算を無限に繰り返す必要があり現実には有限回繰り返しで打ち切らざるを得ないため算出される解は厳密解から誤差を多少なりとも含んだ近似解となる計算結果が含む誤差大きさと収束計算に要する時間はトレードオフ関係にありどこで収束計算を打ち切ればよいか判断は工学的には非常に重要な問題であるまた一口に収束計算と言っても実際には様々な求解アルゴリズムが開発されそれぞれに得失を持っている交通ネットワーク均衡モデル研究においては非線形計画問題や非線形相補性問題といった標準的な形式でモデルを定式化できさえすれば少なくとも何から求解法が存在することは分かるでともすると具体的なアルゴリズムについては重要視されない傾向が見受けられるしかしモデルを実務で活用するにあたっては求解アルゴリズム適切な選択も工学的には重要なテーマであるそこで本研究では収束計算における収束判定指標について定量的な分析結果に基づいて考察を加えるとともに主要な交通ネットワーク均衡モデルについて既往解法アルゴリズムを整理しそれらアルゴリズムについて実用性観点から横断的に性能比較を行ったキーワーズ : 交通ネットワーク分析正員, 修 ( 工 ), 財団法人計量計画研究所 ( 東京都新宿区市谷本村町 2-9, TL ,FAX ) 前述ように収束計算を打ち切る判断を行うにあたっては計算中解が充分に収束しているかどうかを判定する必要があるここでは代表的ないくつか判定指標について整理する以下では解を得ようとしている未知変数 ( 例えばリンク交通量など ) ベクトルを x とし厳密解 ( モデル均衡条件を厳密に満たす解 ) x が一意に存在することが保証されているもとする (1) 厳密解と乖離を表す指標 ( n) 収束計算途中 ( n 回繰り返し時点 ) で解 x が厳密解 x とど程度乖離しているかを表す指標具体的には ( n) mx x x ( 乖離最大値 ) や ( n ) x x ( ノルム ) などが考えられるこタイプ指標は指標持つ意味を解釈し易く最も素直な考え方であるまたこれら指標によって収束計算打ち切り判断を行えば得られた解に含まれる誤差 ( 厳密解と差 ) が所与範囲内に収まるように直接的にコントロールすることが可能であり実務的にも有用であるしかし通常は収束計算に先立って厳密解 x が与えられていることはあり得ないでこれら指標を収束計算打ち切り判断に用いることはできないただし研究においては予め厳密解得られている問題を分析対象とすることが可能なでアルゴリズム特性等分析にこれら指標を活用することは可能である (2) 収束計算に伴う解変化を表す指標収束計算において計算途中解は ( 単調とは限らないが ) 厳密解に徐々に近づいて行く解変化が小さくなれば収束したと見なせると考え方から計算容易な収束判定方法として ( n) ( 1) mx x n x ( 変化最大値 ) や ( n) ( n1) ( n1) mx x x x ( 変化割合最大値 ) などが広く用いられているしかしこれら指標には以下ような重大な欠点がある収束が緩慢でなかなか厳密解に近付かない

2 遅いアルゴリズムを用いるとむしろ指標値が小さくなり見かけ上は収束しているように見えてしまうこれら指標と計算途中解に含まれる誤差 ( 厳密解と差 ) と相関は問題設定やアルゴリズムに依存し一定ではないため解誤差を評価して収束計算打ち切り判断を行うことが困難である (3) 目的関数利用非線形計画問題として定式化できるモデルにおいては収束計算に伴って目的関数値が漸減し最終的には均衡時に目的関数値は最小となるで目的関数を評価することによって収束状況を把握できるように見える目的関数値減少幅は一般に収束が進むにつれて緩慢になって行くが前記 (2) と同様収束遅いアルゴリズムを用いた方が目的関数値減少幅も小さくなるそため目的関数値減少幅が小さくなったとしても充分に厳密解に近づいたからなか単に途中で停滞しているだけなかはどこまで目的関数値が下がるか予め分かっていないと判断できないしかし双対定理を利用すると目的関数値下界を計算することができる例えば需要固定型確定的利用者均衡配分モデルについては以下目的関数 x ( ) = t ( w) Z x dw (1) 0 A に対してそ下界は LB { } K x { x t ( x ) t ( w) dw} ( x) = min c, ( x) Ω A で計算できるまた厳密解 ( x ) 0 x 下では Z( x ) t c, LB は一致するただしはリンクコスト関数は OD 交通量は経路コスト Ω は OD ペア集合 K は経路集合であるここで (2) と x はリンク交通量 ( ) ( x) = Z( x) LB( x) = x t ( x ) min c, ( x) A Ω { } K を定義する ( ) ( ) ( ) 0 (3) x = Z x LB x = となるし x を収束判定指標として用いることが x は双対ギャップと呼ばれるまた式 (3) を変形するとたがって ( ) できる ( ) ただし { } ( x ) = f c, c, ( x) Ω K, min (4) K f, は経路交通量であるつまり ( x) は経路コストと OD 間最小コスト差総和であるで ( x) は均衡状態から旅行コスト乖離程度を表していると解釈することが可能である... 同様に需要固定型確率的利用者均衡配分モデルについては = Ω K Ω Ω f θ すなわち ( x), 1 ln θ c K, K f, exp ( θ c ) f ln,, (5) = 経路コスト総和 - 期待最小コスト総和 - エントロピー総和であり高速転換率内生化確定的利用者均衡配分モデル ( 高速道一般道選択と経路配分統合モデル ) では = A Ω Ω x t ( x ) θ ln θ すなわち ( x) ln ln ψ { exp( θ C ) + exp( θ C ψ )} (6) = 経路コスト総和 - 期待最小コスト総和 - エントロピー総和となる (4)Merit 関数利用非線形計画問題として定式化できないモデルにおいて他形式例えば非線形相補性問題 ( x) = 0, x 0 F( x) 0 Find x sch tht x F, (7) として定式化する場合を考えることき例えば ( ) = + ( ) ( ) + 2 x xi Fi x xi Fi x (8) 2 i ように Merit 関数 ( x) を定義すれば ( x) 0 つ ( x ) = 0 かとなるで式 (7) 非線形相補性問題を非線形計画問題 minimize( x) きるここで ( x) は厳密解に書き換えることがで x から解 x 乖離程度を総合的に表していると解釈できるで収束判定指標として利用することができる (5) 収束判定方法検討上で整理した収束判定指標うち指標持つ意味を解釈しやすく実務的にも有用なは (1) タイプであるが現実には利用できない一方 (3) や (4) タイプ指標は均衡点から乖離程度を総合的に表していると考えられ均衡時には値がゼロにな

3 るため数値計算上は扱いやすいがモデルによっては交通工学的な意味解釈が厄介でそままでは実務では使いにくいそこで厳密解が既知均衡問題を利用して (1) タイプ指標と (3)(4) タイプ指標と相関を分析把握しておくことより (3)(4) タイプから (1) タイプ指標を推定する方法を提案するここでは確定的利用者均衡配分モデルを例にとるまずいくつか例題 ( 表 -1 参照 ) についてモデル厳密解を求めておく先述したように厳密解を得るには無限回繰り返し計算が必要になるが実際には計算機上実数精度 (I 倍精度実数で約 1+04 リンク 1+03 交通量 1+02 厳密 1+01 解か 1+00 ら例題例題 b 乖 1-01 離例題 c R 1-02 M 例題 d 例題 e 例題 f Reltive p 図 -1 Reltive pとリンク交通量rm 誤差関係 (Frn-Wolfe 法を用いた場合 ) 1+04 リンク 1+03 交通 1+02 量厳 1+01 密解か 1+00 ら乖 1-01 例題例題 b 例題 c 例題 d 例題 e 例題 f 離 R 1-02 M Reltive p 図 -2 Reltive pとリンク交通量rm 誤差関係 (Br-er 法を用いた場合 ) 表 -1 分析に用いた例題諸元例題リンク数ノード数ゾーン数平均混雑度 1, b 2,800 1, c 3, d 3,400 1, e 12,000 3, f 22,000 8, 桁 ) による制約を受けるためこ精度に達した解を事実上厳密解と見なすことにする図 -1は横軸に Reltive p( 双対ギャップを目的関数値で除してネットワーク規模に依存しないように基準化したも ) をとり縦軸にリンク交通量 RM 誤差 ( リンク交通量厳密解と乖離平方平均平方根 ) をとり複数例題設定下で両者関係を比較したもである図 -1から分かるように二つ指標には強い相関があり且つ例題設定に依らずほぼ共通直線上に乗っておりリンク交通量 RM 誤差は Reltive p 約 10 5 倍となっているただし完全に共通線上に乗っているわけではなく入力条件を変えるとグラフが左上または右下に移動してしまうため横軸双対ギャップをより適切に基準化するよう改良余地があり今後研究課題であるまた求解に用いるアルゴリズムによってもこ相関グラフ形状は異なる図 -1は Frn-Wolfe 法を用いたときもであるが図 -2に示すように Br-er 法を用いたときにはグラフは左上に移動し入力条件による差異も広がっているしたがって双対ギャップからリンク交通量誤差を推定する関係式はアルゴリズムごとに分析する必要がある 3. アルゴリズム性能比較 (1) 確定的利用者均衡配分アルゴリズム比較次に交通ネットワーク均衡モデル求解に用いるアルゴリズム性能比較を行うここでは交通ネットワーク均衡モデル中でも特に多くアルゴリズムが開発されている確定的利用者均衡配分モデルを例にとるアルゴリズムに関する既往論文では勿論それぞれ性能検証が行われているが総じて以下ような問題がある Frn-Wolfe 法をベンチマークにして比較を行っているもが殆どである Frn-Wolfe 法は遅い部類に入るアルゴリズムであり高速なアルゴリズム評価に用いる比較対照としては適切ではないまた新しいアルゴリズム同士横並び比較ができない検証に用いる例題がそれぞれ論文で異なっていることが多く共通入力条件下で横並び比較ができないまた小規模例題を用いていることが多く実践的な性能が分からない既往論文でよく見かける iox Flls ネットワークは実在都市もではあるが高々 24ゾーン76リン

4 クであり小さ過ぎる収束判定指標に不適切なもを使っている場合がある例えば前章 (1) タイプ指標は収束程度を表すには不適切である上指標自体挙動がアルゴリズムに大きく依存するアルゴリズム自体性能差他にプログラミング際実装優劣も影響している可能性があるそこで本研究では同一計算機環境と同一例題を用いて既往主要なアルゴリズム横断的な 1+05 リン 1+04 ク交 1+03 通 1+02 量 1+01 厳密 1+00 解か 1-01 ら 1-02 乖離 R M リン 1+03 ク交 1+02 通量 1+01 厳 1+00 密解 1-01 から 1-02 乖 1-03 離 1-04 R M 逐次平均法 Frn-Wolfe 法打ち切り二次計画法 PARTAN 法打ち切り二次計画法 +PARTAN 法 LCFW 法リンク交通量パターンによる D 法経路交通量による D 法 Br-er 法計算時間 ( 秒 ) 図 -3 主要アルゴリズム速度比較 ( 例題 ) 逐次平均法 Frn-Wolfe 法打ち切り二次計画法 PARTAN 法打ち切り二次計画法 +PARTAN 法 LCFW 法リンク交通量パターンによる D 法経路交通量による D 法 Br-er 法計算時間 ( 秒 ) 図 -4 主要アルゴリズム速度比較 ( 例題 d) 1+04 リン1+03 ク交 1+02 通量 1+01 厳 1+00 密解 1-01 から1-02 乖 1-03 離1-04 R M Frn-Wolfe 法 LCFW 法リンク交通量パターンによる D 法経路交通量による D 法 Br-er 法計算時間 ( 秒 ) 図 -5 主要アルゴリズム速度比較 ( 例題 e) 比較を行ったプログラム実装とコーディングは全て筆者が独自に行ったもであるため実装優劣に起因する性能差は小さいと考えられる収束状況を表す指標にはリンク交通量厳密解から乖離 RM 平均を用いた結果一部を図 -3~5に示す両対数目盛グラフ上で Frn-Wolfe 法はかなり正確に傾き 1直線となっているすなわち誤差を半減させるためには計算時間が2 倍必要になることを示しており一次収束よりも更に遅いまた Frn-Wolfe 法や PARTAN 法など目的関数一階微分しか利用しないアルゴリズムでは同様に傾きがほぼ 1であり性能は Frn-Wolfe 法と大差ない LCFW 法は Frn-Wolfe 法発展型で目的関数一階微分しか利用しないタイプであるが Frn-Wolfe 法よりも高い性能を示している D 法や Br-er 法は目的関数二階微分を利用するアルゴリズムであり収束が進むにつれて Frn-Wolfe 法と性能差が大きくなるまた D 法よりは Br-er 法方が高速であるがそ差はネットワーク規模が大きいほど顕著になるただし収束初期 ( 初期解から数回分 ) はどアルゴリズムも速度に大差はない (2) アルゴリズムに関する課題我が国ネットワーク研究者間ではより高速なアルゴリズム開発必要性に対する認識が充分でないように見受けられる一方で実務者多くは未だに Frn-Wolfe 法などプリミティブな解法に安住または手一杯であり高速なアルゴリズムに対する理解と利用は残念ながら進んでいないしかしながら以下理由からより高速なアルゴリズムへニーズは潜在的なもも含めて非常に大きいと考えられる実務においては数万 ~ 数十万リンクにおよぶ大規模なネットワークで交通量推計を行う場合があり既存アルゴリズムでは1ケース計算だけで数日を費やすことになる実務においては多数ケース計算を短期間にこなさなければいけない場合がある同時に複数ケースを進められる場合には複数 PC を投入することで解決できるが 1ケース計算するごとに入力データやパラメータ調整を繰り返すような逐次作業となることも多く計算は速いに越したことはない単なる交通量配分だけでなくネットワーク

5 均衡条件下で上位問題 ( 最適政策分析など ) を解く MPC (Mthemticl Progrmming with ilibrim Constrints) アプローチを用いる場合上位最適化問題を解く過程で下位ネットワーク均衡問題を何度も繰り返し解く必要があり高速なアルゴリズム必要性が極めて高い海外研究論文をレビューする限り確定的利用者均衡配分モデルについては多くアルゴリズムが開発され近年でもまだ新たなアルゴリズムが登場しているただし大規模ネットワークに適用可能で収束計算初期段階で速度が高いアルゴリズムへニーズが高いと思われ今後に期待したい確率的利用者均衡配分モデルについては高速化以前問題として Dil 配分 Mrov chin 配分 D 法いずれも経路選択肢集合に関連する欠点を抱えており安心して使えるアルゴリズムが存在しないことがモデル普及に向けた大きな課題である高速転換率内生化利用者均衡配分モデルや交通ネットワーク統合モデル更には非線形計画問題として定式化できないモデルなどより複雑高度なモデル解法については既往研究も多くはないがより優れたアルゴリズムを適宜開発してゆく必要があると思われるまた近年 PC 用 CPU ではマルチコア化が急速に進み安価に手軽に並列計算を行える環境が出現したネットワーク均衡分析アルゴリズムでは並列処理と親和性が高い部分も多くマルチコア CPU 活用が期待できる並列処理と言うと一起点多終点経路探索を複数起点から同時に実行することをまず思いつくがそれに留まらずアルゴリズム全体を並列化に適したもにするアプローチが考えられる 4. おわりに本研究では未だ分析が不十分であり問題提起に留まっている部分が多いが今後も引き続き分析を続けて行きたい特に適切な収束判定については交通ネットワーク均衡モデルが普及してゆく上で重要な要素であり本稿が呼び水となって更に多様な研究が進展すれば幸いである参考文献 1) Y. heffi (1985), Urbn Trnsporttion Networs: ilibrim Anlysis with Mthemticl Progrmming Methods, Prentice-Hll 2) M. Ptrisson (1994), The Trffic Assignment Problem: Models nd Methods, VP, The Netherlnds 3) D. Boyce, B. Rlevic-Deic nd H. Br-er (2004), Convergence of trffic ssignments: How mch is enogh?, Jornl of Trnsporttion ngineering, AC, Vol. 130, Isse 1, pp ). Rose, M.. Dsin nd F.. Koppelmn (1988), An exmintion of convergence error in eilibrim trffic ssignment models, Trnsporttion Reserch, Prt B, Vol. 22, No. 4, pp ) L. J. LeBlnc,. K. Morlo nd W. P. Piell (1975), An efficient pproch to solving the rod networ eilibrim trffic ssignment problem, Trnsporttion Reserch, Vol. 9, pp ) L. J. LeBlnc, R. V. Helgson nd D.. Boyce (1985), Improved fficiency of the Frn-Wolfe Algorithm for Convex Networ Problems, Trnsporttion cience, Vol. 19, No. 4, pp ) M. Florin, J. elt nd H. piess (1987), An efficient implementtion of the PARTAN vrint of the liner pproximtion method for the networ eilibrim problem, Netwo Vol. 17, pp ) Y. Arezi nd D. Vn Vliet (1990), A fll nlyticl implementtion of the PARTAN/Frn-Wolfe Algorithm for ilibrim Assignment, Trnsporttion cience, Vol. 24, No. 1, pp ) R.. Dembo nd U. Tlowitzi (1988), Compting eilibri on lrge mlticommodity networs: Appliction of trncted drtic progrmming lgorithms, Netwo Vol. 18, pp ) D.-H. Lee nd Y. Nie (2001), Accelerting strtegies nd compttionl stdies of the Frn-Wolfe lgorithm for the trffic ssignment problem, Trnsporttion Reserch Record, 1771, pp ). Lwphongpnich nd D. W. Hern (1984), implicil decomposition of symmetric trffic ssignment problem, Trnsporttion Reserch, 18, pp ) D. W. Hern,. Lwphongpnich nd J. A. Ventr (1987), Restricted simplicil decomposition: Compttion nd extensions, Mthemticl Progrmming tdy, 31, pp ) T. Lson nd M. Ptrisson (1992), implicil decomposition with disggregted representtion for the trffic ssignment problem, Trnsporttion

6 cience, Vol. 26, pp ) R. Jyrishnn, W. K. Tsi, J. N. Prsher nd. Rjdhysh (1994), Fster Pth-Bsed Algorithm for Trffic Assignment, Trnsporttion Reserch Record, 1443, pp ) H. Br-er (1999), Origin-bsed lgorithms for trnsporttion networ modeling, Ph.D. thesis, Univeity of Illinois t Chicgo (NI Technicl Report No. 103, 16) H. Br-er (2002), Origin-bsed lgorithm for the trffic ssignment problem, Trnsporttion cience, Vol. 36, pp ) R. B. Dil (2006), A pth-bsed ser-eilibrim trffic ssignment lgorithm tht obvites pth storge nd enmertion, Trnsporttion Reserch, Prt B, Article in press

168. W rdrop. W rdrop ( ).. (b) ( ) OD W rdrrop r s x t f c q δ, 3.4 ( ) OD OD OD { δ, = 1 if OD 0

168. W rdrop. W rdrop ( ).. (b) ( ) OD W rdrrop r s x t f c q δ, 3.4 ( ) OD OD OD { δ, = 1 if OD 0 167 p (n) im p(n+1) im p (n+1) im p(n) im < ε (3.264) ε p (n+1) im 1 4 [1],, :, Vol.43, pp.14-21, 2001. [2] Rust, J., Optiml Replcement of GMC Bus Engines: An Empiricl Model of Hrold Zurcher, Econometric,