| 学籍番号 | 90189129 | 所属研究室 | 藤重研 |
| 氏名 | 幡 本 賢 史 | ||
| タイトル | 逆最短路問題による道路課金の分析 | ||
|
1. 序論 交通渋滞問題の対策の一つに，道路課金（ロードプライシング）が挙げられる．尼崎市や東京都での導入が検討されており，近年注目を集めている渋滞対策の方法である． 道路課金において，実現すべき交通が与えられれば，その交通を実現する問題は，逆最適化の問題設定理論が適用できることが指摘されている[1]．逆最適化問題とは与えられた最適化問題とその一つの実行可能解に対し，その実行可能解が最適解になるような，元の最適化問題に対する変更を求める問題である． 本研究は，渋滞を起こさない交通の決定の部分に，ネットワーク最適化における古典的な問題である多品種フロー問題を利用した場合について，道路課金を逆最短路問題で決定する数理モデルを立て，その有効性について検討を行う． まず, 逆最適化問題のモデルにおいては，課金だけでは実現できない交通が存在することが確認できた. これをふまえ, 目標となる交通を定める多品種フロー問題に，実現不可能な交通を解として生じにくくする工夫を加えて，道路課金による交通の実現可能性を，計算機実験を通じて検討する． さらに，多品種フロー問題に適用した工夫の効果，および求められた課金に関して考察する． 2. 問題 本論文では道路課金問題を以下のようにモデル化する． 有向グラフG=(V,A)と，各枝の枝長l:A -> R_{++}および容量u:A -> R_{++}でネットワークN=(G=(V,A),l,u)を表す． このネットワークの利用状況として,始点s_i，終点t_i，交通量d_iの組(s_i,t_i,d_i) が i = 1,...,K について与えられるとする．また, 課金と距離との変換係数r が与えられるとする. このとき，課金alpha:A -> R_{+}で，枝長をl_a+r*alpha_aとした場合の最短路のみを用いて，(s_i,t_i)間に値d_iのフローを，同時に，各枝の容量を越えないよう流せる，という条件を満たすものを求める． 3. 問題の解法 上の問題を2段階に分けて考える．まず1段階として，利用状況として与えられた(s_i,t_i,d_i)に対して，枝容量条件と交通量d_iを満たす，(s_i,t_i)-フローx^i:A -> R_{+}をi = 1,...,Kについて求める部分を，多品種フロー問題として解く．出来るだけ最短フローに近いものを求めるための工夫として，フロー全体の枝長の総和を最小化する目的関数を設置している． Min sum_{a in A } sum_{1 <= i <= K}l_{a}x^{i}_{a} s. t. sum_{a in delta^{+}{v} }x^{i}_{a} - sum_{a in delta^{-}{v} }x^{i}_{a}=0 ( v != s_i,t_i, i=1,...,K ) sum_{a in delta^{+}{v} }x^{i}_{a} - sum_{a in delta^{-}{v}}x^{i}_{a}=d_i ( v = s_i,i=1,...,K ) sum_{a in delta^{+}{v} }x^{i}_{a} - sum_{a in delta^{-}{v} }x^{i}_{a}=-d_i ( v = t_i,i=1,...,K )&& x^{i}_a >= 0 ( a in A, i=1,...,K ) sum_{1 <= i <= K}x^{i}_{a} <= u_{a} (a in A) 次に2段階目として，得られたフローx^iに対して，r=1として次の逆最短路問題を解き，1段階目のフローで表される交通を実現する課金を求める． Min sum_{a in A} alpha_a s. t. y^i_v-y^i_w <= l_(v,w)+alpha_(v,w) (x^i_(v,w}=0, (v,w) in A, i=1,...,K ) y^i_v-y^i_w = l_(v,w)+alpha_(v,w) (x^i_(v,w)>0, (v,w)\in A, i=1,...,K ) alpha_a >= 0 (a in A) 4. 計算機実験とその結果} 1段階目で求めたフローがどの程度，課金で実現できる交通となっているかを計算機実験により検討する ランダムに発生させた，30点，枝60本のグラフ，30点，枝84本のグラフをそれぞれ3種類用意し，各枝に枝長，容量を与え，すべての2点間に交通量を割り当てた問題例を使用した． それぞれのグラフに対して，異なる枝の容量を用いて実験を繰り返した．その結果，1段階目で求まるすべてのフローが，課金により実現可能なものであった． また多品種フロー問題に対し，目的ベクトルに関する工夫の効果を確認するため，目的ベクトルを0ベクトルとした場合と比較した． その結果，目的ベクトルに工夫を施した場合に比べ枝の容量を2倍程度に設定しないと，課金により実現可能なフローが求まらないという結果が得られた． 以上のことから, 本論文の方法の有効性が確認できた. 参考文献 [1] R. K. Ahuja and J. B.Orlin. Inverse optimization. Working Paper SWP 4002, Sloan School of Management, MIT, 1998. |
|||