@yuichirominato 2019.01.31更新 314views

【自動車】交通流最適化を改造して幹線道路をつけてみる


はじめに

以前フォルクスワーゲン社の交通最適化に関して、最適化計算をD-Waveを使って行いました。今回は質問があったので、それを対応してみます。

https://blog.blueqat.com/post/176

経路最適化に幹線道路を考える

上記の交通最適化の簡単なモデルを考えます。以前と同じです。

これは道の混雑を考えて、混雑を緩和します。道の条件は考えていませんので全て同じ重みで実行しています。

今回は真っ当な疑問ですが、幹線道路のように複数台が走っても大丈夫な道を考慮できないかという質問がありました。それをどのように解決するかみてみます。

まずQUBOをつくる

解く手順を復習してみます。

1、まずは自動車の取りうるルートを1台の車につき3ルート考える
2、それぞれのルートについて個別の道の混雑具合を計算するQUBOをたてる。
3、1台の車には1つのルートしか取れないという制約条件をつけて解く。

こちらを解くことによって交通最適化ができます。

QUBOに幹線道路を入れてみる

幹線道路を考える際にはQUBOを少しいじります。先ほどの道路のQUBOは、

こうなっています。それぞれの車の取りうるルートに対応する量子ビットを足し合わせてコスト算定していますが、このQUBOをいじることで幹線道路を導入できます。

まずは幹線道路を導入する前のQUBOをみてみます。Blueqatの新しい機能を使って、

from blueqat import opt
a = opt.opt()

#コスト関数
E1 = opt.optm("(q0+q1+q3+q4)^2+(q1+q4+q11)^2+(q2+q5)^2+(q0+q3+q11)^2+(q1+q4+q11)^2+(q2+q5+q7+q8)^2+(q0+q3+q8+q9)^2+q6^2+(q2+q5+q7+q10)^2+(q0+q1+q3+q4+q8+q9+q11)^2+q6^2+(q2+q5+q6+q7+q10)^2",12) 

#制約条件
E2 = opt.optm("(q0+q1+q2-1)^2+(q3+q4+q5-1)^2+(q6+q7+q8-1)^2+(q9+q10+q11-1)^2",12) 

a.qubo = E1+10*E2
a.sa()

#=>[0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0]

print(a.E[-1])
#=>-23.0

最小コストが-23ででてきました。幹線道路をつくるとこの値も変わってきそうです。下図のようにs4とs9に幹線道路をつくることにしました。片側2車線です。(これまでは片側1車線)

QUBOを調整する

行うことはQUBOの調整だけです。調整するのは簡単です。該当するセグメント道路を選び、そのかっこのなかを1/2にすれば混雑が考慮されます。2台入っても混雑コストが上がりません。対応するs4とs9に適用してみます。

新しい式は、

from blueqat import opt
a = opt.opt()

#コスト関数
E1 = opt.optm("(q0+q1+q3+q4)^2+(q1+q4+q11)^2+(q2+q5)^2+(q0+q3+q11)^2+0.25*(q1+q4+q11)^2+(q2+q5+q7+q8)^2+(q0+q3+q8+q9)^2+q6^2+(q2+q5+q7+q10)^2+0.25*(q0+q1+q3+q4+q8+q9+q11)^2+q6^2+(q2+q5+q6+q7+q10)^2",12) 

#制約条件
E2 = opt.optm("(q0+q1+q2-1)^2+(q3+q4+q5-1)^2+(q6+q7+q8-1)^2+(q9+q10+q11-1)^2",12) 

a.qubo = E1+10*E2
a.sa()

#=>[0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0]

print(a.E[-1])
#=>-26.75

この場合には、Q13,Q22,Q31,Q41が選ばれました、対応するルートは、

Q13 = s2,s5,s8,s11
Q22 = s0,s1,s4,s9
Q31 = s7,s10,s11
Q41 = s6,s9

幹線道路を作ったことで最適ルートも変わりました。以上です。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方