[PR]当サイトはアフィリエイト広告を利用しています。
※2021/08/28に公開した当記事ですが、隣接行列関連の説明をよりわかりやすくするために、少し追記しました。その他文章のこまごまとした言い回しなども修正して、2022/10/06に再度公開しました。
※さらに導入部分をよりイメージしやすくするために、少し加筆修正して2022/10/31に再度公開しました。
言うは易く行うは難しな巡回セールスマン問題
あなたはポスティングを業務とする企業のマネージャーだとしましょう。
顧客から印刷物を受けとって、それを従業員に配達させています。
印刷物を配達した量で企業の売り上げが変わる、出来高制とします。
あなたがマネージャーなら、従業員にどう配達させますか？
当然ながら時間を目いっぱい使って、最大量配達したいですよね。
従業員は24時間働き続けることはできませんから、一日８時間業務に従事するとしましょう。
すると８時間で最大量配達したいと考えるのは自然です。
そこで考えたいのが、配達するルートです。
最悪なのは、最初に出発点から最大の距離の場所に行ってから、反対方向の最も遠い場所に行って、そこからまた反対方向の３番目に遠い場所に行く。こんなルートです。
普通に考えて、出発点から近いところに行って、そこからまた近いところに行って、また近くに行く。そんなルートのほうが、移動距離が短くなりますね。
でもこれって、実際に考えてみると、あーでもない、こーでもないとなります。
それもそのはず。
このルートを決める問題は「巡回セールスマン問題」と言われており、効率的に解く方法が見つかっていません。
総当たりであらゆるルートから総移動距離が一番短いルートを見つけようとすると、周る場所（ポストを入れる住所）が増えれば増えるほど途方もない組み合わせを計算する必要があるのです。
だからスーパーコンピュータで無理だから、量子コンピュータで解こうとかそういう話になっていきます。
人間の頭で「一番良いルート」を考えるのは、かなり困難なのです。
スパコンに人間の筆算で挑むような無謀さがあります。
それでも何とか一般的なコンピュータで解けないかと試行錯誤しているのがオペレーションズ・リサーチという学問分野です。
今回は線形計画法という手法で近似的に、そこそこ良い答えをコンピュータに計算させようという回です（厳密解を確実に得られるというものではありません）。
使うのはエクセルのソルバー。線形計画法で実装します。
ちなみにエクセルソルバーで解く今回のやり方は、原理的な解説となっているので、「原理なんていいから、実用的なソフトはないの？」という方はGoogleのOR-Toolsというソフトがありますのでそちらをどうぞ。
当サイトでも少し扱っております。よろしければそちらもどうぞ。
実際のやり方
式の立て方で参考にしたのは以下。
(1)ウィリアム・J・クック.（2013）.『驚きの数学 巡回セールスマン問題』.松浦俊輔（訳）.青土社.
身近なところに問題が見つからなかったので仮の問題で解きます。
この6つの地点を最も効率よく回るにはどういう順番が良いかということを計算します。
まず地点を結びます。
それぞれのノードがそれぞれのノードとつながっている状態を考えます。
この辺はグラフ理論の基礎知識が必要なので、興味のある方は勉強してみるといいかもしれません。
それぞれの枝の長さを格納した隣接行列を作成します。
D5が枝（1,2）の長さを表しています。対称行列です。
枝の長さの数値は今回の解説用に適当に設定しています。
実際は問題ごとに地点と地点の距離が入ります。
次に変数の作成。
x21やx32は対称なので変数にはしません。
つまり、枝12と枝21は同じなので、片方だけわかればいいです、という話です。
変数として0と1が並んでいますけど、これは初期値として適当な値を入れているだけです。
x12はノード1からノード2までの枝があるかないかを表しています。
あるかないか、なので「ある」なら1、「ない」なら0の二択です。
求めたい解はこの枝の長さの合計が、最小になるような0と1の組み合わせです。
最初はわからないので、適当に0と1を入力しています。
そして変数を隣接行列風に表した行列を作ります。
x(i,i)は0です。
D12=C2、E12=D2、…、E13=H2、…
とやります。
対称行列なので
C13=D12、…、E16=G14、…
とやります。
そして文献(1)より、一筆書きできるとき、各頂点に入る枝と出る枝の和は2という制約があるので、
J12=SUM(C12:H12)、J13=SUM(C13:H13)、…
とします。これがそれぞれ2になればよいです。
隣接行列風の行列に関しては、例えば１行目がノード1から伸びる枝があるかないかの全てを表していることに注意してください。
2行目はノード2から伸びる枝のすべてを表しています。
隣接行列風の行列の行の右側で合計しているのは、枝の合計が2となれば、ノードに入る枝とノードから出る枝が１本ずつとなるため、それを算出するためです。
目的関数は
M6=D5*D12+E5*E12+F5*F12+G5*G12+H5*H12+E6*E13+F6*F13+G6*G13+H6*H13+F7*F14+G7*G14+H7*H14+G8*G15+H8*H15+H9*H16
です。
対称行列の対称成分の片方と枝のコストをかけたものを足します。これを最小化します。
ソルバーの設定は以下。
変数セルはバイナリ、解決方法は線形計画なのでシンプレックスLPを選択します。
解決すると
目的関数は13で、下のようなグラフになります。変数セルはこれまでの画像で出てきたC2からQ2セルの値です。
ソルバーで解かなくてもたぶんもっと効率の良いアルゴリズムがあるみたいですが、巡回セールスマン問題の勉強になりました。
線形計画の練習にもなりましたし。
やはりエクセルソルバーはすごいです。
線形計画問題も整数制約で解けますし。
当ブログ（シルルスのコードおきば）ではエクセルソルバー関係の記事を他にも執筆しています。参考になりましたら幸いです。
●ソルバーをVBAで繰り返す【初期値を変えて複数解を自動探索】
●エクセルソルバーで複数解を求める方法【初期値を変えるしかないです】
●エクセルソルバーと組み合わせ最適化問題【解法例と基礎知識】
●Support Vector Regressionをエクセルのソルバーで作ってみた
