株式会社豊田中央研究所と東京大学の2者は、2月10日、量子コンピューターの一種であるカナダ・D-Wave社製「量子アニーリングマシン」を用いて、ひとつの都市圏に設置されている多数の信号機を、まとめて制御する手法を開発したと発表した。これを用いれば、交通流を約10%改善させることが可能だという。 【写真で解説】量子コンピューターは一体何がスゴい？
すべての信号機の青信号の時間を、交通量に合わせて最適化できれば、渋滞をもっと緩和できると思ったことはないだろうか。実はすでに一部の信号機は、周辺の交通量を把握し、状況に合わせて青信号の点灯時間を変えている。さらに都市全域で最適なタイミング制御ができるようになれば、交通の流れがよりスムーズになるのは間違いない。 しかしその実現には、技術的な困難さが立ちはだかる。その理由は、制御するためには数学の「組み合わせ最適化問題」が必要となるからである。組み合わせ最適化問題は、条件によっては、最新のスーパーコンピューターで延々と計算しても終わらないという、膨大な計算処理が必要な問題なのだ。
「巡回セールスマン問題」でわかる組み合わせ最適化問題の“クセモノ“ぶり
組み合わせ最適化問題を理解するには、その代表である「巡回セールスマン問題」がわかりやすい。これはセールスマンが、たとえば5つの都市を1回ずつ訪問して出発地の都市に戻るとき、複数あるルートの中から、どういう順序で都市を回っていけば最短距離となるのかを選び出す問題のことだ。 都市の数が少ないうちは一見すると簡単に見える。しかし都市をどの順序で回るかという組み合わせの数は、見た目に反したところがあり、計算してみるとその大変さがわかる。都市間の距離などはひとまず置いておき、単純にルートが何通りあるか計算すると、5都市の場合は5×4×3×2×1=120通りとなる。そして120通りすべての距離を算出し、どれが最も短距離かを比較して見極めれば最短ルートがわかるというわけだ。この程度の数なら、パソコンでも計算できるだろう。 しかし、これが10都市だとどうだろうか。10×9×...2×1=362万8800通りとなる。都市の数は2倍になっただけだが、組み合わせは3万240倍だ。3倍の15都市だとどうなるか。なんと、1兆3076億7436万8000通りとなる。都市の数は3倍に過ぎないが、組み合わせの数は108億9728万6400倍である。このように、組み合わせが爆発的に増えていくのが特徴で、実際に計算してみないとその大変さが分かりづらいところが、“クセモノ“なのである。 そしてどのルートが最短距離なのかを算出するには、実際に1兆3076億7436万8000通りの全ルートの距離を算出して比較する必要がある。仮に1ルートの距離を算出するのにかかる時間が0.0001秒だとしても、15都市の全ルートを算出するには4年以上もかかってしまう計算だ。 都市圏全体の信号機をまとめて制御するということは、単純に考えると、巡回セールスマン問題の都市の数を信号機に置き換えればよい。厳密には、どの信号機を通るかというルートの話ではないのだが、組み合わせ最適化問題で扱うことが可能だ。しかし、信号機の数が増えれば増えるほど、計算に膨大な時間を必要とすることは同じである。 まして信号機制御の演算は、リアルタイム性を求められることから、可能なら毎秒、遅くても10秒に1回程度は交通状況の取得と計算を行うのが望ましいはずだ。そうすると、ひとつの組み合わせにかけられる時間は、信号が15しかないとしても、1307億6743万6800分の1秒しかない（厳密には比較などの時間もあるので、もっと早く計算する必要がある）。信号機の数がひとつ増えるだけで、組み合わせの数は1桁増えたりするので、50、100と増えていったら、1回の計算にかけられる時間はとてつもなく短くなっていく。つまり、これまでは都市全体の信号機を制御したくても、できないというのが実情だったのである。
からの記事と詳細 ( 量子コンピューターの一種で渋滞緩和を目指す。都市全体の信号機制御を最適化（くるくら） - Yahoo!ニュース - Yahoo!ニュース )
https://ift.tt/2NGpfKD
No comments:
Post a Comment