数理計画によるシステム最適化

はじめに

制御工学のブログとして始めましたが、最近は迷走気味です。
今回は数理計画法によるシステムの最適化について書いてみようと思います。

数理計画はシステムの制御と関係ないと思われるかもしれません。

制御工学は、制御目標にいかに追従するかを考えます。車で言えば、目標とする走行速度や車間距離まで、いかに早く正確にシステムの状態を変化させるかです。

一方、ドライバーは、前方の車両が減速することを予期できた場合、事前に車間距離を広げるなどして、前走車の減速の影響を小さくします。その方が、車としての効率が良かったり、乗員への負荷が低いからです。

状況に合わせて、どのような制御目標を指示してシステムを最適に稼働させるかを決定するのもシステム制御の重要なテーマです。

昔々、線形計画法のシンプレックスのプログラムを作った経験がありますが、すばらしいことにExcelには最適化問題を解くためのソルバーが実装されています。

今回は、最適化問題を解く計算手法やプログラムの説明ではなく、Excelのソルバーを利用して、システムの最適化問題をどうやって定式化して解いていくのかについて例を示しながら書いていきます。

最適化問題の対象システム

よく数理計画法の教科書に載っている例では面白くないので、交差点の交通流制御を例に考えてみたいと思います。

実際のところ、日本の主な幹線道路の信号は、交通管制システムによって交通流に合わせて信号サイクルごとに制御されています。

昨年の2022年11月に、宇都宮では交通管制システムのシステム障害で大渋滞が発生しました。
→ 参考

信号機が停止したわけではなく、交通管制システムからの指示がないので、各信号機が所定の時間で切り替わるスタンドアロン状態になったのではないかと思います。

朝の通勤時間帯のような交通容量が飽和状態に近い状況では、交通管制による交通流の最適化が行われないと大規模な渋滞が発生してしまうことになります。

数理計画法によるアプローチ

数理計画法によりシステムの最適化問題を扱う場合、システムの最適化問題を数学モデルで定式化し、数理的な手法で数学モデルに対する最適解を求めることになります。

実際の交通管制システムには、より高度な技術が採用されていると思いますが、このブログでは、 Excelの最適化問題を解くためのソルバーを利用して、数理計画法の計算手法の一つである線形計画法で最適解を求めることにします。

線形計画法では、制約条件と目的関数のすべてが一次式（一次不等式や整数条件を含む）で表される数学モデルを扱います。世の中の最適化問題の多くは一次式で近似的に表現できることが多いため、線形計画法はあらゆる分野で広く利用されているようです。

交差点の交通流制御の最適化の結果

まず最初に、交差点の交通流制御の最適化の結果を示します。

最適化した場合としなかった場合で、交差点で停止し滞留した車両の台数を比較しています。交差点で停止し滞留する車両台数を20%程度削減する効果がありました。

交差点交通流制御の数学モデル

交差点の交通流制御を下記のように単純化した数学モデルにします。

• 交通流の制御周期をT秒とします。
• 交通流の制御周期T秒間毎に交差点に到達する車両のグループを、Avenue側 A1, A2, A3、Street側 S1, S2, S3とします。最初の制御周期間 0～1T秒には、A1とS1の車両グループが交差点に到達します。同様に、1T秒～2T秒には A2とS2、2T秒～3T秒には A3とS3の車両グループが交差点に到達します。
• A1, A2, A3, S1, S2, S3の車両グループには、それぞれ所定の台数の車両が含まれ、交差点に到達の際に通過可能であれば、制御周期T秒の中で交差点を通過します。
• 交差点の交通流制御は、制御周期T秒毎に交差点に到達する車両のグループのうち、Avenue側かStreet側のいずれかを制御周期T秒間通過させます。
• Avenue側とStreet側を交互に通過させるのではなく、交差点の交通流制御として最適な制御を目指します。制御指標としては、交差点で停止し滞留する総車両台数が最も少なくなる交通流制御とします。

線形計画法によるモデル化

線形計画法で最適化問題を解きます。最初に、決定変数、制約式、目的関数について説明します。

決定変数：システムの内部状態を表す変数で、システムの状態を最適化できる決定変数が最適解になります。

制約式：システムの様々な条件を規定する条件式です。Excelのソルバーでは、全て１次式（等号または不等号）か異なる整数の条件(dif)になります。

目的関数：システムの最適化の指標になる式です。線形計画法では１次式で規定し、この式の値が最大値または最小値になる決定変数が最適解になります。

定式化の検討

目的関数ですが、交差点の交通流制御において、交差点を通過する車両台数を最大にすればよいのですが、どのように表現すればよいでしょうか。

順番に考えてみると

1Tの制御フェーズでは、A1とS1の車両グループのいずれかを通過させます。

A1を通過させた場合、S1は停止して通過できるようになるまで待機することになります。

仮に2Tの制御フェーズで、S側を通過させた場合は、待機していたS1と、2T区間のS2の車両グループが交差点を通過することになります。このとき、A2の車両グループは通過できず待機となります。

次に3Tの制御フェーズですが、Avenue側ではA2が滞留していて、そこにA3が到着します。しかし、それらの台数よりも、Street側のS3の車両グループの台数が多ければ、S3の車両グループを通過させた方がトータルの滞留台数は少なくなります。

このように考えると、交差点を通過する車両台数を最大にする交通流制御というのは、交差点で停止し滞留する車両の台数を最小にする制御といえます。

また、 A1, A2, A3, S1, S2, S3の車両グループは、1T～4Tの4回の制御フェーズで通過できることから、最適制御とは、交差点で停止し滞留する車両の台数が最小になるように、各車両グループの通過タイミング（1～４のいずれの制御フェーズで通過させるか）を決定することになります。

決定変数

A1, A2, A3, S1, S2, S3の車両グループが、それぞれ交差点を通過する制御フェーズを Pa1, Pa2, Pa3, Ps1, Ps2, Ps3 とします。これが決定変数になります。

目的関数 

更に、A1, A2, A3, S1, S2, S3 の車両グループの台数を Na1, Na2, Na3, Ns1, Ns2, Ns3 とすると、目的関数である交差点で停止し滞留する車両の総台数は

minimize

 z = (Pa1-1)× Na1+(Pa2-2)× Na2+(Pa3-3)× Na3+(Ps1-1)× Ns1+(Ps2-2)× Ns2+(Ps3-3)× Ns3

と表現できます。

制約式

A1, A2, A3, S1, S2, S3 の車両グループが、それぞれ交差点を通過する制御フェーズ Pa1, Pa2, Pa3, Ps1, Ps2, Ps3 の関係を式で規定します。各車両グループが交差点に到達するタイミングから

　Ps1  ≧　1
　Pa1  ≧　1
　Ps2  ≧　2
　Pa2  ≧　2
　Ps3  ≧　3
　Pa3  ≧　3

前後関係は逆転しないので

　Ps2 - Ps1　≧　0
　Pa2 - Pa1　≧　0
　Ps3 - Ps2　≧　0
　Pa3 - Pa2　≧　0

次に、S側とA側は同時に通過させられないので、通過タイミングは異なる必要があります。

　Ps1≠Pa1 
　Ps2≠Pa2 
　Ps3≠Pa3 
　Ps1≠Pa2 
　Ps1≠Pa3 
　Ps2≠Pa1 
　Ps2≠Pa3 
　Ps3≠Pa1 
　Ps3≠Pa2 

線形計画法では、基本的に制約条件は１次式（等式か不等式）が基本です。異なる(≠)という条件設定はできません。

このため、通過タイミングは１～4のいずれかという条件も考慮して、Excelのソルバーが持つAll different (dif)条件を使って下記のように条件設定をしています。

　Ps1≠Pa1  →　Ps1, Pa1, x1, y1 dif
　Ps2≠Pa2  →　Ps2, Pa2, x2, y2 dif
　Ps3≠Pa3  →　Ps3, Pa3, x3, y3 dif
　Ps1≠Pa2  →　Ps1, Pa2, x4, y4 dif
　Ps1≠Pa3  →　Ps1, Pa3, x5, y5 dif
　Ps2≠Pa1  →　Ps2, Pa1, x6, y6 dif
　Ps2≠Pa3  →　Ps2, Pa3, x7, y7 dif
　Ps3≠Pa1  →　Ps3, Pa1, x8, y8 dif
　Ps3≠Pa2  →　Ps3, Pa2, x9, y9 dif 

ここで、xn,yn は補助的な変数で、All different (dif)条件が１～4のいずれかの異なる整数を割り当てるという機能を満たすために導入しているだけで制御上の意味はありません。

All different (dif)は、変数セルの指定が必要なため、決定変数のセルとAll different (dif)条件のセルの値は等しいという条件も追加しています。

Excelファイルのダウンロードと実行結果

Excelファイルは →こちら からダウンロードできます。
Sheet1の F7 セルが目的関数になっています。

実行には、Excelのアドインでソルバーが選択されている必要があります。
データのタグから、ソルバーを選択すると、目的関数（目的セル）や、決定変数（変数セル）、制約条件を確認できます。線形計画法を利用するため、解決方法の選択は シンプレックスLP を選択しています。

スタートスイッチを押すと、Ns1, Ns2, Ns3, Na1, Na2, Na3 にランダムに1～10の車両台数を設定し、計算を実行します。初期設定では、５回演算し最適化した制御の場合と、交互交通の総滞留台数の比較結果を更新します。

既に冒頭で提示しているグラフは、100回演算した結果です。

最適化した制御の場合は、総滞留台数の分布が少ない側にズレており、交通流の改善効果が確認できます。総滞留台数の削減効果としては、20%程度の効果がありました。

最後まで読んでいただきありがとうございました。
非線形なシステムに対する最適化手法としては逐次２次計画法があります。

逐次２次計画法のプログラムSQPは、こちら で公開しています。