【最短経路検索】Excelのソルバー機能を使って線形計画法で解いてみた

2022年1月18日2024年10月6日

最短経路検索問題は線形計画法で解ける

最短経路検索問題はダイクストラ法で解くことができ、Google地図ルート検索やYahoo!路線情報等、私たちの身の回りにあるアプリにもこのアルゴリズムが使われています。

前々回の記事では、このアルゴリズムをExcelで実装してみました。

【最短経路検索】ダイクストラ法を理解してExcelに実装してみた。

 

一方、この問題は線形計画法でも解くことができます。

ダイクストラ法は最短経路検索にしか使えませんが、線形計画法はもっと汎用性がありいろいろな問題を解くことができるため、このやり方も興味ありますね。

そこで、前々回と同じ最短経路検索問題を線形計画法で解いてみました。

 

最短経路検索問題を線形計画法に定式化する

次の問題を解きます。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

１から６に移動するのに、最もコストが安くなるルートはどれでしょうか？

但し、黒字は各ノード間を移動するコストとします。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

 

新たな変数を導入して目的関数を定義する

この問題の答えは１⇒４⇒３⇒６のルートで、その時のコストは４＋２＋６＝１２です。

ここで、新たな変数x_ijを次のように定義します。

x_ij＝１（ノードiからノードjへの矢印を通過した場合）

x_ij＝０（ノードiからノードjへの矢印を通過しなかった場合）

すると、先ほどの最短経路のコストは次式で表すことができます。

4x₁₄＋2x₄₃＋6x₃₆＝12

 

これら３つの矢印はすべて通ったのでx_ijは１ですが、それ以外のx_ijはゼロです。

従って、

2x₁₂＋5x₂₃＋9x₂₄＋4x₁₄＋8x₁₅＋3x₃₄＋2x₄₃＋4x₄₅＋8x₅₄＋6x₃₆＋10x₄₆＋5x₅₆＝12

のように書いても同じです。

従って、これらの変数を使って最短経路検索問題を表すと、下記の目的関数を最小化する問題になります。

目的関数＝2x₁₂＋5x₂₃＋9x₂₄＋4x₁₄＋8x₁₅＋3x₃₄＋2x₄₃＋4x₄₅＋8x₅₄＋6x₃₆＋10x₄₆＋5x₅₆

このようにすれば、通らなかった矢印のコストにはゼロが掛けられるため、通った矢印のコストだけが足されることになりますね。

それが最小になるようなx_ijの組み合わせを求めれば良いわけです。

 

制約条件を設定する

但し、何の制約条件もなければx_ijがすべてゼロの場合に目的関数がゼロになり、これが最小になってしまいます。

でもこれではどの矢印も通らないことになるため、１から６に辿り着けません。

そこで１から６に辿り着くための制約条件を付けてあげます。

 

まずノード１が出発点になるためには、ノード１から出ている３本の矢印のうちの１本だけを通らなくてはいけませんね。

ですので、

x₁₂＋x₁₄＋x₁₅＝1

という式が成り立ちます。

またノード６が終着点になるためには、ノード６に入っている３本の矢印のうちの１本だけを通ることになります。

ですので、

x₃₆＋x₄₆＋x₅₆＝1

という式が成り立ちます。

 

その他のノードについてはどうでしょうか？

ノード２を見てみましょう。

ノード２を通るとすれば、x₁₂から入ってx₂₃かx₂₄のいずれかの矢印から出ていくはずです。

つまり入力の数と出力の数はバランスするはずで、次式が成り立ちます。

x₁₂－x₂₃－x₂₄＝0

 

更に、この式はノード２を通っても通らなくても成り立ちます。

その他のノードについても同様に考えることができますので、制約式をまとめると次のようになります。

x₁₂＋x₁₄＋x₁₅＝1・・・①

x₁₂－x₂₃－x₂₄＝0・・・②

x₂₃－x₃₄＋x₄₃－x₃₆＝0・・・③

x₂₄＋x₁₄＋x₃₄＋x₅₄－x₄₅－x₄₃－x₄₆＝0・・・④

x₁₅＋x₄₅－x₅₄－x₅₆＝0・・・⑤

x₃₆＋x₄₆＋x₅₆＝1・・・⑥

 

但しx_ijは０または１です。

これで線形計画法の問題に定式化できました。

 

Excelのソルバーでシンプレックス法を簡単に解く

この問題は拡大係数行列を作ってシンプレックス法で解くことができます。

【線形計画法②】シンプレックス法でトラックの積載率が最大になる条件を求めてみた

 

でも、掃き出し法によって連立方程式を解くのは結構面倒です。

そこで、Excelに付いているソルバー機能を使います。

ソルバー機能の中には、シンプレックス法を計算する機能も付いています。

 

まず制約式①～⑥を表にしてみましょう。

SUMPRODUCT関数を使うと、次のように表すことができます。

 

ここでC列はx_ijの値を表していて、その矢印を通れば１、通らなければ０です。

これらの初期値はすべて０にしていますが、この値をこれからソルバーで最適化していきます。

 

次に、最適化の基準となる目的関数を表に入力します。

目的関数＝2x₁₂＋5x₂₃＋9x₂₄＋4x₁₄＋8x₁₅＋3x₃₄＋2x₄₃＋4x₄₅＋8x₅₄＋6x₃₆＋10x₄₆＋5x₅₆

これも各ノード間（各矢印）のコストをJ列に入力すれば、同じようにSUMPRODUCT関数を使って次のように計算できます。

 

これで情報は入力しましたので、これをソルバーで最適化計算します。

まずはデータ⇒ソルバーをクリックして、ソルバー画面を表示させます。

 

次に、目的セルには目的関数の値を、変数セルにはx_ijの値を、制約条件にはSUMPRODUCT関数で計算した入出力バランスの値をそれぞれ入力します。

 

制約条件の中に「$C$4:$C$28=バイナリ」が一番上に入力してありますが、これはx_ijの値が０または１にしかならないようにするための条件です。

後は「解決」ボタンをクリックすれば、シンプレックス法で最適化計算をしてくれます。

結果はこのようになりました。

 

ダイクストラ法で解いた結果と同じになりました。

このように線形計画法は適用範囲が広く、計算もExcelのソルバーで簡単に計算できるため大変便利です。