等粒度クラスタリング技術を用いた 大規模交通シミュレータの高速化 株式会社ＮＴＴデータ 技術開発本部 エボリューショナルITセンタ 大谷 智洋 Copyright © 2016 NTT DATA Corporation 発表の流れ • NTTデータの取組み紹介（交通シミュレーション） • 交通シミュレーションの課題とボトルネック • 等粒度クラスタリング技術を用いた分割アプローチ • 評価結果 • まとめ Copyright © 2016 NTT DATA Corporation 2 渋滞予測・信号制御シミュレーション 目的 交通管理者が行う交通需要マネジメントを支援するため、 計画ごとの渋滞予測情報および信号変更タイミング情報を提供する 提案法 新興国では感知器（センサ）が利用できないことを想定し、GPSプローブに基づく交通 シミュレーションを行うことで、予測情報を生成し適正な信号変更のタイミングを決定 ビッグデータ 道路センサ/プローブ （センサデータ） 見える化 予測 事故状況表示 制御 渋滞予測 1 ×事故渋滞 ×自動車事故 8 ４ 交通情報（テキスト） 渋滞状況表示 9 1 6 8 ４ Copyright © 2016 NTT DATA Corporation 信号制御 3 交通 シミュレーション 3 シミュレーションによる最適信号制御方式選択のイメージ 現状の信号設定を改善し得る信号パラメータ候補に対して、シミュレーションにより 渋滞緩和効果を評価し、最適パラメータを選択。実際の信号機に設定を反映・制御 することで渋滞緩和を実現。 交通シミュレーションによる信号パラメーター最適化のイメージ 分析用データ 信号パラメーター候補、設定候補 道路情報 シミュレータ パラメーターセット１ パラメーターセット２ 交通量情報 ・ ・ ・ パラメーターセットn バスGPS データ 信号連動エリア 信号現示 信号パラメータ 等の組合せ 渋 滞シ 緩ミ 和ュ のレ ー 程シ 度ョ をン 評で 価 最 適 パ ラ メ ー タ ー を 選 択 実環境 信号機へ反映 ・制御実施 ネットワーク化されていない信号機に対しては手動で設定 この方式を用いて昨年度、中国吉林市で実証実験を実施 Copyright © 2016 NTT DATA Corporation 4 吉林市内の混雑の様子 吉林市の交通現状 渋滞によりバス運行に 遅れが発生している。 信号設定の不備が 渋滞の原因となっている。 吉林市のねらい 安全かつ便利な公 共交通の実現 交通渋滞の少ない 交通環境の醸成 Copyright © 2016 NTT DATA Corporation 5 昨年度における実証実験の実績 市が抱える課題解決ため、 吉林市内のバスGPSを用いて実証実験を実施 バスの運行時間改善効果 課題 最大 ２７％改善 130% バ 120% ス 運 行 110% 時 間 100% 改 善 率 90% 平均 ６％改善 バス8路線の平均 実験前 130路 • • • • 吉林市は事故が多発 月曜日に病院が混みやすい 天気に対応できない より広い範囲で実証の実証 リアルタイムに信号を制御するこ とで、この課題に対処 実験後 適切な信号パラメタを設定することで 最大２７％改善を確認 過去の統計情報ではなく、最新情報を 用いたシミュレーションが重要になる 実証実験を通じて信号制御の有効性を確認したと共に 渋滞緩和を向上させるための課題（リアルタイム制御）を確認した Copyright © 2016 NTT DATA Corporation 6 リアルタイム制御に必要な目標値の設定 リアルタイムの信号制御に必要な時間 ①プローブ(GPS)情報収集 ④信号制御実施 車載機から1分に1回、 携帯回線を通じてDBに送信 プローブ 信号管制のパラメタ更新間隔 ②プローブ情報を道路（地図）へ貼付 信号パラメタ候補を用意 （周期・スプリット・オフセット） 90・40・5 パ ラ 90・60・10 メ タ ・ ・ 候 ・ 120,50,20 補 信号機へ最適 なパラメタ を送信し、 制御実施 ③シミュレーション処理 将来の渋滞緩和の程度を評価し、 最適なパラメタを選択 90・40・5 シミュレーション処理 地図 並列 統合 分割 分散 90・60・10 ・ ・ ・ 120,50,20 現在のシミュレーション処理よりも 半分の時間でシミュレーションを行うことを目標値として設定 Copyright © 2016 NTT DATA Corporation 7 シミュレーションの概要とボトルネック 広範囲・100万規模の車両台数の計算を複数の汎用サーバで実現 地図分割処理 1メッシュのデータを1コアで処理 車両台数が平準に なるように分割 約8% 道路ネットワーク イメージ 並列分散処理 分割した地図を CPU1コアに割り当て 約90% 並列処理で1メッシュの 計算は早く終わる！ 統合処理 スケジューリング機能 を付与 約2% 親コア データ集約のタイミングをずらして コネクションエラーを回避 並列分散処理の処理時間を短縮させる必要がある Copyright © 2016 NTT DATA Corporation 8 ボトルネック検証 分散処理時間を短縮させるため分割数の増加を行うアプローチを実施 分割数と処理時間の関係 1400 1200 800 頻 度 車両数が過多の メッシュが存在 400 道路数 200 地図範囲 0 交差点数 平準化した はずなのに・・ 1000 車両数 Frequency 処理時間 シミュレーション Histogram of probes 400分割時のヒストグラム 要因 600 分割数と実行速度 要因分析を実施 0 100 200 300 400 分割数 0 5000 10000 15000 車両数 probes 分割数が増加しても 200分割以上で速度が伸びない 平準化した分割をしたはずが 車両の数に偏りがあった 様々な要因を分析した結果 各メッシュに含まれる車両数に偏りがあることを確認 Copyright © 2016 NTT DATA Corporation 9 ボトルネック検証 車両数が処理時間にどう影響を及ぼすかを調査 高速化に向けた対策立案 車両数と処理時間の関係 現状 理想 正比例 車 両 数 処 理 時 間 処理時間 が依存 メッシュ番号 車両数 車両数が処理時間を決める 時間同期のため 全体のパフォーマンス が低下する 車 両 数 メッシュ番号 分散処理のパフォーマンス を発揮するため各メッシュで 同量の車両数を処理 理想形の場合計算時間が約1/3に短縮 各メッシュに含まれる車両数の平準化（等粒度化）を行うことで 並列分散処理を高速化 Copyright © 2016 NTT DATA Corporation 10 アプローチの策定と実践① 調査したボトルネックを解消する要件である “等粒度化”を満たすアプローチを実施 既存のグラフ分割ツール選定 高 速 性 要件を 満たす ゾーン 1.6秒 Metis 課 題 ① 各メッシュ内の車両数に偏りがあり、並列処 理で負荷が偏る ② クラスタ数を指定できないため、十分な並列 多重度が得られない 対 策 案 bin-packingアルゴリズムの策定 予めビンを用意し、地図を多めに分割し車両数 が均等になるようビンに詰め、等粒度化を図る ビンに分割した地図を入れるイメージ 27.4秒 メッシュ数3の場合 等粒度性 ※I/O処理含 ＮＴＴと連携してGraponの 改善余地が有ることを確認 bin-packingアルゴリズムによる 等粒度化を策定 等粒度な分割方法を実現 Copyright © 2016 NTT DATA Corporation 11 アプローチの策定と実践② 等粒度性を求めすぎて分割数を多くしてしまうと シミュレーション処理時間が余計にかかってしまう 理 由 処理時間の増加理由 ・車の地図間移動が多くなり通信コストが増加 ・統合処理に時間がかかる ・最適なパラメタ値のチューニング 工 夫 点 - 分割の細かさを決める分割パラメタと、平準化す る指標のパラメタ(交差点数、車両数、なし)の組合 せから通信コスト、処理速度、偏りを測定 - まとまりよく分割されているか見るために1つ1つ メッシュの色分けによる確認を実施 分割における最適なパラメータをチューニングし 最も高速かつ等粒度な分割を探索 Copyright © 2016 NTT DATA Corporation 12 結果と評価 車両数の平準化によって交通シミュレーションの 並列分散処理パフォーマンスを最大に活かすグラフ分割を実現 各メッシュに含まれる車両数 12000 sd=2387.02 10000 車 8000 両 6000 数 4000 旧grapon 等粒度クラスタリング技術適用 metis sd=1527.52 シミュレーション時間 500 450 目標値より 高速化！ 400 350 300 ※従来の値 を100として 換算 250 sd=387.67 200 133.3 100 150 2000 100 0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15 1617 181920 21 22 23 24 50 メッシュ番号（24メッシュに分けた場合） 0 従来技術と比較すると各メッシュに 含まれるプローブ数の偏りが減少 40.0 旧grapon metis 目標値 34.2 等粒度クラスタリ 新grapon ング技術適用 シミュレーション時間を 約3倍の高速化を達成！ 汎用サーバを用いてリアルタイムに信号制御が 可能なレベルまでシミュレーションの高速化に成功した Copyright © 2016 NTT DATA Corporation 13 今後について UKの交通管制システムとの連携により リアルタイムでの信号制御を目標とする共同研究を実施 NTTデータ シミュレーションでの信号制御 マルチエージェントシミュレーション ・GPS+センサ ベース ・ニアリアルタイ ム信号制御 ・大規模シミュ レーションで広 域制御が可能 Imtech交通管制・信号制御SCOOT ・センサベース ・動的信号制御 ・施設運用が高額 ・狭域の制御(主要幹線 道路) ・40年の実績 シミュレーション上で最適信号制御を決定 信号制御シミュレーションと交通管制システムの連携構築を目指している。 等粒度クラスタリング技術を用いた分割手法を取り込んだシミュレーション により、リアルタイムでの交通制御を実現させる。 グラフマイニングの活用により、社会課題の解決に繋げる Copyright © 2016 NTT DATA Corporation 14 Copyright © 2011 NTT DATA Corporation Copyright © 2016 NTT DATA Corporation 本資料には、当社の秘密情報が含まれております。当社の許可なく第三者へ開示することはご遠慮ください。
© Copyright 2024 ExpyDoc
