サイト内の現在位置

量子コンピュータを用いた交通流最適化の改良を研究

量子コンピュータの一つの方式としてアニーリング方式と呼ばれるものがあり、組合せ最適化問題を解くための技術として注目されています。解くことができる組合せ最適化問題は数多くありますが、そのうちの一つとして経路最適化が都市交通制御や無人搬送車（AGV）の制御などに応用できる最適化問題として知られています。従来知られていた量子アニーリングを用いた都市交通制御は、各車両の移動速度や各道路での通過時刻を考慮しない疑似的な問題設定を前提としているものでした[1],[2]。単純に各車両の経路がお互い重なっていればいるほど交通渋滞とみなしたうえで、交通渋滞が緩和されるよう車両の経路の組み合わせを最適化するものであり、その点では実用的とは言えないものでした。今回の研究では、車両の移動速度や通過時刻を考慮するように定式化の改良を行いました。

下図に示す簡単な問題を用いて従来手法の課題とそれを改良する提案手法のメリットを説明します。2台の車両A、Bが同時刻に同じ速度で出発するとして、それぞれ三通りの経路の候補があるとします。太線の経路は最短経路であり、点線の経路は迂回する経路を示しています。従来手法で経路の最適化を計算すると、車両の通過時刻を考慮しないため、車両Bは迂回する経路を選択する結果になります。その一方で提案手法を使うと、車両A・Bともに最短経路を選ぶ結果になります。経路が重なっている部分がありますが、同時に通過することはないので、それを考慮した最適化結果となり、従来手法に比べて全車両の経路の長さの和を短縮することになるわけです。この研究成果は、第198回ハイパフォーマンスコンピューティング・第14回量子ソフトウェア合同研究発表会で講演発表しました[3]。

参考：
[1] Florian Neukart, Gabriele Compostella, Christian Seidel, David Von Dollen, Sheir Yarkoni, Bob Parney: Traffic Flow Optimization Using a Quantum Annealer. Frontiers ICT 4: 29 (2017).
[2] https://www.nec-solutioninnovators.co.jp/rd/event/event_20.html
[3] https://www.ipsj.or.jp/kenkyukai/event/hpc198qs14.html