量子アニーリングの交通最適化をもちょっとみる

交通最適化問題は有名です。しかし問題の難易度や既存コンピュータで解けるんじゃないか？という疑問も多いと思います。とりあえずざっくり問題をもちょっと分析してみます。

問題は制約条件とコスト関数からなります。

制約条件は自動車がルートを1つ選ぶというもの。コスト関数は各道路の混雑度です。

まずは、コスト関数です。

通常は上三角行列を使います。15ある非対角項のうち、0が4あるので、

11/15 = 0.733...

全体の量子ビットの接続数のうち、73%くらいの接続数があります。

制約条件を入れた最終の式は、

13/15 = 0.866...

86.7%程度の埋まり率になっています。

接続数が多いほど密になるので、D-Waveが苦手と言われています。D-Waveは元々接続がキメラグラフなので、それに沿った問題の方が良さそうです。

引用：https://arxiv.org/pdf/1805.05217.pdf

先ほどのモデルは問題が小さかったので、もちょい大きくしてみます。 まずは、制約条件から問題サイズに応じてどのように行列の粗密が変化するのかをみてみます。制約条件の方が簡単にできそうです。

制約条件の接続数は、とくべき問題の自動車の数をkとすると、1台の車あたりで選択されるルートの数nに対して、

となります。量子ビット数Nは

となります。粗密の割合は相互作用に関して、

となりました。ルート選択はn=2以上で考えて、

制約条件に関しては、ルート選択の数に対してはそんなに粗密は変わりませんでした。ルート選択の数が多くなると、その分量子ビット数も増えるので、代替ルートを10個提案しても、計算量が増えるだけで接続数は変わりません。

自動車の数に応じて制約条件は粗密が変わるようです。100台前後で1%を切る感じの疎行列になりそうです。

行列は基本的には疎行列になりやすく、自動車の台数によりました。例えば、QUBOmatrixは代替ルート3で、

代替ルート4で、

こんな感じで隣接する量子ビット同士の接続がメインになるので、制約条件に関しては密な行列にはなりません。

台数が増えると疎になりやすいです。今回はコスト関数を見てみたいと思います。

ルート提案数によってQUBOがどのように変わっていくのかみてみたいと思います。VWの論文ではルート提案数は3でした。制約条件のQUBOmatrixの粗密は提案数では大きくは変化しませんでした。

簡単なモデルで、2*2の道路ネットワークを考えてみます。

提案ルート1つごとに1量子ビットを与えます。そして、それぞれの量子ビット同士の提案ルート内に、同じ道路が含まれているかみます。

提案ルート数3で、全部提案ルートが違う場合は、

サイズが小さいので、

10/15 = 0666...

程度となりました。同じくらいの道でモデルを変えてみます。

5/15 = 0.333....

となりました。最初のモデルは、スタート地点ですでに選択肢が2つしかないので、自然と密行列になっていました。コスト関数においては、重複する道が歩かないかが大事なので、その辺りを注意したいと思います。

道路の分岐数などのモデルによって大きく行列の粗密が変化しそうです。実際には自動車の通る時間や、道路ネットワークの疎密は、解きたい場所の情報を取得するのが大事のようです。

全体最適を重視すると、個人は割りを喰う感じにもなりそうです。今回は、まだ実際の道路のデータを把握できていないので、次回は実際の道路のネットワーク構成を考慮して考えてみたいと思います。

また、混雑度を解消した代わりに、自動車全体での走行距離がどの程度増えるのかを確認したいと思います。

上記はスタート地点を同一で考えました。スタート地点は同一ではないので、変更した方がいいとは思いますが、それもイジングの最適化では道路の出現回数だけで測っていて、考慮はされていないようです。制約条件が増えるとまた正答率が下がるので、頭痛の種ではあります。当面は出現回数だけで処理をしたいと思います。

結構制約条件が多いので、結構大変な気がしてきました。数理最適では、制約条件がどうしても出るので、大規模なものをリアルタイムにモデル化して解くというので効率化を図るのは大きな違いが出にくいのではないでしょうか。もうちょっと考察してみます。

量子アニーリングの実用化を考えるために交通最適化を細かくみています。

1、制約条件は提案ルート数より自動車の数によって行列の粗密が決まる。 2、ルートのモデルによって、コスト関数の粗密が大きく変わる。 3、自動車のスタート地点を変えたりしてよりモデルを良くする。

などが必要でした。

こういうアルゴリズムが必要なのは都市圏だと思います。都内の道のネットワークを見てみて、提案ルートがいくつくらい取れて、どの程度のネットワーク構成になっているのかをみてみたいと思います。

google mapでトレースしてみました。

都内は、

こんな感じになりました。ある程度大きそうな道だけを選びました。これは、どっちかというと最適化というよりも、まずは提案ルート作成アルゴリズムが必要です。

適当に5台くらいのスタートとゴールを決めて設置して、3ルートの代替案を作ってみます。

5台で3案だと15量子ビットになります。

ざっくりで申し訳ないですが、道が重なっているところは上記のもので、23箇所程度でした。

15量子ビットの相互作用の数は、15C2なので、105となり粗密は、

23/105 = 0.21..

21%程度となりました。実際にこれを運用するには結構細かく計算する必要がありそうです。

実際には、自動車の進行方向とかを考えると、倍の10台程度で21%程度の粗密になりそうです。皇居があるので、あんまり遠回りはできませんでした。ある程度幹線道路を通る必要がありそうです。

自動車を増やすと量子ビットは3ずつ増えます。相互作用の数も増えるので、提案ルートが重なる数も増えますが、全体的に疎密はそこまで増えないかもしれません。今後検討するかもしれません。

課題は自動車の行き先を同時に取得しないと全体最適化ができませんが、なかなかそんな感じのことはしばらくはできなさそうなので実用面では厳しそうです。北京でVWが行なったのはタクシーの最適化で、タクシー会社が管理できる面では使えますが、それ以外の自動車の管理はできないので、最適化の効果はさらに限られると思います。

こう考えると、数理最適や動的計画法で交通を全体最適するのはかなりの課題がありそうです。計算で15-20%程度最適化できても、実際の効果を実感できるほどの最適化ができて、そこに投資効果があるかどうかは疑問となります。

交通最適は、題材としてある程度管理ができて、全体最適が効くところがいいと思いますが、実際にはエリア分割をすれば良いいのと、既存の計算機で十分計算できそうな範囲に収まってしまうので、よりいい題材を探したいと思います。実験としては面白いと思います。

管理できるサイズが大きければ最適化する経済効果も大きいですが、実際にはそのような数理最適で最適化できる大きなサイズを一括管理している場面は日常では少なさそうです。

以上です。