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

2022年9月26日

【スポンサーリンク】

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

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

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

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

 

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

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

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

 

業務改善/ロジスティクスエンジニアリングの求人数が多いのはここだ!

 

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

次の問題を解きます。

*****************************

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

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

*****************************

 

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

この問題の答えは1⇒4⇒3⇒6のルートで、その時のコストは4+2+6=12です。

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

xij=1(ノードiからノードjへの矢印を通過した場合)

xij=0(ノードiからノードjへの矢印を通過しなかった場合)

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

4x14+2x43+6x36=12

 

これら3つの矢印はすべて通ったのでxijは1ですが、それ以外のxijはゼロです。

従って、

2x12+5x23+9x24+4x14+8x15+3x34+2x43+4x45+8x54+6x36+10x46+5x56=12

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

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

目的関数=2x12+5x23+9x24+4x14+8x15+3x34+2x43+4x45+8x54+6x36+10x46+5x56

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

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

 

制約条件を設定する

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

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

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

 

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

ですので、

x12+x14+x15=1

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

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

ですので、

x36+x46+x56=1

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

 

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

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

ノード2を通るとすれば、x12から入ってx23x24のいずれかの矢印から出ていくはずです。

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

x12-x23-x24=0

 

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

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

x12+x14+x15=1・・・①

x12-x23-x24=0・・・②

x23-x34+x43-x36=0・・・③

x24+x14+x34+x54-x45-x43-x46=0・・・④

x15+x45-x54-x56=0・・・⑤

x36+x46+x56=1・・・⑥

 

但しxijは0または1です。

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

 

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

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

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

 

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

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

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

 

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

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

 

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

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

 

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

目的関数=2x12+5x23+9x24+4x14+8x15+3x34+2x43+4x45+8x54+6x36+10x46+5x56

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

 

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

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

クリックすると拡大します

 

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

クリックすると拡大します

 

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

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

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

クリックすると拡大します

 

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

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

 

業務改善/ロジスティクスエンジニアリングの求人数が多いのはここだ!

無料の運行管理システムAI-Contactフリート

このような最短経路検索のアルゴリズムは輸送管理システム(TMS)の一機能として含まれている場合があります。

このTMSは幅広い概念ですが、運行管理動態管理を含む場合もあります。

そして、この運行管理や動態管理を完全無料のクラウドサービスで提供している会社があります。

 

通常、無料というのは眉唾もので、始めは無料だけども、どこかの携帯電話会社みたいに途中で有料化宣言するとか、気づかないうちにいつの間にか有料になっていたということが多いですね。

でも、この会社は永久に無料で提供することを宣言しています。

そのシステムの名はAI-Contactフリートです。

これは「運行管理」、「動態管理」、「車両管理」等をオールインワンで提供するクラウドサービスです。

運送業を行っている物流会社だけでなく、自社トラックで輸送を行っている荷主会社自社のサービスエンジニアを多く抱える電気設備会社、更には社用車を多く抱える一般会社等、様々な会社に適用可能です。

またこれだけの機能が詰まっていて無料なので、中小企業だけでなくダイハツ工業メイデンアイシン戸田建設NTT東日本等の大企業にも採用されています。

Web説明会も毎日開催されているようです。

少しでも興味のある方は、お気軽に問い合わせてみてはいかがでしょうか。