エクセル配送順番計算

Question

お世話になります。

出発点から１０店配送します。
最短距離での順番を計算します。

（例）
出発点：世田谷区上野毛１

顧客１：世田谷区等々力１
顧客２：目黒区自由が丘１
顧客３：世田谷区尾山台１
顧客４：目黒区八雲１
・・・
顧客１０：目黒区柿の木坂１

出発点から顧客１０のうち最短距離での順番を出そうとしています。
ルールは出発点から最短距離→顧客１
顧客１から最短距離顧客３
顧客３から最短距離顧客２

このような感じで
それぞれから最短距離を計算し顧客１０までの順番を出します。

エクセルで可能でしょうか？
ご存じの方よろしくお願いいたします。

saburo0 · Accepted Answer

いや、各地点間の距離などのコストが正確に分かってるなら、単純に考え得るすべての経路を探索して、最短を求めるだけですよ。
そのコスト（距離等）さえ出して貰えば、できる人にはできるので、（本当に出せるなら）ココに出して頂ければ誰かが回答をくれるでしょう。

fujillin · Answer

ANo3、4です。

なんだか誤解を招きそうな雰囲気があるので、少しだけ補足を…

No3にも示しましたように、基本的には最適解を求めるロジックを利用するべきものと思います。
No4は可能であることの一例として、「総当たり方式」による解法の一例を示したつもりですが、「いつも固定の10店舗を回るのだけれど、どの経路が一番効率的なのだろう？」というように、一回（手間をかけても）解を求めておけば、後々利用できるような場合には、総当たり方式であっても試みる価値はあるだろうという意味です。
具体的な算出方法について、No4ではマクロを用いた方法を示しましたが、関数式等を用いて順次計算するようにしても同じ結果が得られるはずです。
（単純に、全通りを計算するだけなので考え方としては簡単ですね。…実際にやるのは面倒ですが。）

No7様がしきりにおっしゃっているように、各地点間のデータ表は必要となりますが、固定の店舗間のデータであれば取得することは可能であろうと想像します。（多少の時間や手間は必要かもしれませんが）
実質的な運用を想像すると、距離データというよりは所要時間ベースでの評価になるのではないかと思いますが、No4にも書きましたように、地点Ａ→ＢとＢ→Ａは必ずしも同じ値とはならないことが予想できます。（さらに、時期や時間帯の影響も受ける可能性もあります）
基本データをどう扱うかは質問者様におまかせするしかありませんが、往路、復路の違いを反映させたい場合には、表を半分ではなく全部埋めるようにして、例えば縦軸が出発側、横軸が到着側となるような形式にしておくことで、往復の違いも反映して計算することもできると思います。

一方で、『今から、あそことここのｎ店を回るのだけれどどの経路が一番良いのか？』や『新たに指定されたｎ箇所のポイントを回らなければならないのだけれど・・・？』というように即時の解が必要となる場合は、計算に時間がかかる方法では役に立たないので、効率の悪い総当たり方式では間に合わない可能性があります。
とはいうものの、No4でテストしてみたところでは5店舗程度であれば1秒ぐらいでしたので、その程度の範囲ならば実用にも使えそうな気がします。
箇所数が増えると経路数は階乗で効いてくるため、No3にも示しましたように、計算する順路が飛躍的に増加してゆき、計算に時間がかかることになります。

また、No3でご紹介しました「巡回セールスマン問題」は出発点に戻るまでを考慮しているものですが、No4で例示したコードは、（経路をご覧になればわかると思いますが）行ったきりで戻るまでは考慮していません。
もしも、ご質問の主旨が「出発点に戻る」までを含んでいるおつもりでしたら、そのまま「巡回セールスマン問題」に当てはまることになります。
総当たり方式でも同様の考え方で（効率さえ気にしなければ）解を求めることが可能ですが、その場合は、No4で示した内容に出発点に戻る計算を付け加えて評価する必要があります。

saburo0 · Answer

10か所ならば、まずは、10+9+8+7+6+5+4+3+2+1の55ルートを実測して、
その移動時間を距離に置き換えれば、簡単にできるかもしれません。
シュミレーションするより、実測するのが一番てっとりばやいかと思われます。

あとは、巡回セールスマン問題に基づき計算すればいいだけですね。

saburo0 · Answer

#4様が才能の無駄遣いで大変参考になります。
ただしこれを利用するには、#1のお礼欄にあるように、各地点間の距離情報の取得ができなければ、
残念ながらどうにもできないということですね。
あとは道路には制限速度や赤信号、その他通行規制等がありますので、これらも考慮にいれないとまずいですね。

fujillin · Answer

ANo3です。

言った手前、総当たりで求める方法を試してみました。(笑)

10か所だと数が多すぎるので、5か所でテストしていますが、同じ方法で解けることは解けるはずです。
ただし、ANo3にも書きましたように、時間がどのくらいかかるかは不明です。

考え方としては、各地点間の距離の表があるものとして、経路を順に総当たりで求め、表を参照して合計距離を求めるという単純なものです。
startを除いて5地点で試していましたが、経路の数が120になるので、添付図に入りきらないため、添付図では4か所の例にして載せています。（表には5地点ありますが、Ｅ地点を除いて4地点で計算しています）

A1:G7が距離の表です。（時間でも距離でも良いです）
実際にはＡ→Ｂの時間とＢ→Ａの時間が異なるような条件もありうると思いますが、テストなのでどちらも同じとして表は半分だけ埋めています。
根拠が何もないと表が作成できないので、左下の図のような位置関係と距離を想定してから表を作成しています。

計算結果はＩ列、Ｊ列に出力しています。
ポイント数が多くなっても、基本的に同じマクロで計算は可能なはずですが、行数溢れなどの可能性があるので調整が必要になるでしょう。
また、計算にかかる時間も不明です。ちなみに5か所（120経路）の計算では、感覚的には1秒かかっていない感じでした。（正確に測ってはいません）

得られた結果のなかから、最短値を求めてとりあえず黄色表示にするようにしています。
添付図の4ヶ所の例では、最短経路は1経路で、18行目の『start→C→D→A→B』の順になります。
E地点を含めた5ヶ所での計算では、最短経路が2ルートみつかりました。

以下、使用したマクロです。
何かのご参考にでもなれば・・・

Private index(5)
Private Const nMax = 4

Sub main()
　Dim i As Integer
　Dim r As Long
　Dim d As Single
　
　For i = 0 To nMax
　　index(i) = i + 1
　Next i
　Cells(2, 9).Resize(130, 2).ClearContents
　Cells(2, 9).Resize(130, 2).Interior.ColorIndex = xlColorIndexNone
　Call permu(1)

' 最短経路を強調表示(黄色表示)
　r = Cells(Rows.Count, 9).End(xlUp).Row
　d = WorksheetFunction.Min(Cells(2, 10).Resize(r - 1))
　For i = 2 To r
　　If Cells(i, 10).Value = d Then
　　　Cells(i, 9).Resize(, 2).Interior.ColorIndex = 6
　　End If
　Next i
End Sub

' 再帰呼び出しで順列（経路）を作成
Sub permu(ByVal n)
　Dim i As Integer
　If n < nMax + 1 Then
　　For i = n To nMax
　　　Call swap(n, i)
　　　Call permu(n + 1)
　　　Call swap(n, i)
　　Next i
　Else
　　Call calcRoot
　End If
End Sub

' 配列要素入れ替え処理
Sub swap(i, j)
　Dim tmp
　tmp = index(i)
　index(i) = index(j)
　index(j) = tmp
End Sub

' 1経路分の計算と出力
Sub calcRoot()
　Dim i As Integer, r As Long
　Dim tmp As Integer
　Dim root As String, dist As Single

dist = 0
　tmp = index(0)
　root = Cells(1, tmp + 1).Value

For i = 1 To nMax
　　root = root & "→" & Cells(1, index(i) + 1).Value
　　If tmp < index(i) Then
　　　dist = dist + Cells(tmp + 1, index(i) + 1)
　　Else
　　　dist = dist + Cells(index(i) + 1, tmp + 1)
　　End If
　　tmp = index(i)
　Next i

r = Cells(Rows.Count, 9).End(xlUp).Row + 1
　Cells(r, 9).Value = root
　Cells(r, 10) = dist
End Sub

fujillin · Answer

こんにちは

回答ではありませんが、ヒントにでもなれば・・・

＞最短距離での順番を計算します。
とのことですが、ご質問文でご提示のアルゴリズムでは最短を得られる保証が無いように思います。
一般に『巡回セールスマン問題』と言われているものの応用のように思いますので、以下、ご参考までに。
https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83%AB%E3%82%B9%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C

少なくとも、各店相互間の距離情報（あるいは移動の所要時間？）が必要と思われます。
また、随時解を得るためにはプログラムを作成する必要がありそうです。

固定の10店を回る最短経路を求めておきたいというご質問であるならば、1回だけ計算しさえすればすみますので、エクセルの力技で、全通りの計算を行ってしまい、最小値を探すという方法でも求められるかもしれません。
ただし、10か所を巡る順序は全部で 10！＝3628800通りの計算になってしまいますが、式さえうまく作成できれば不可能ではなさそうですね。
数が多いので、最初の通過点別に列を分けて計算するといったような工夫も必要になってくるかもしれません。（フィルコピーも大変そうですが・・・）

全部の組み合わせを試す方式なら、いっそのことマクロで行っても比較的簡単なコードですむものと思われます。
ただし、このプログラムは効率が良いとは言えませんので、全部を処理するのにどのくらいの時間がかかるか不明です。
そのため、解は得られますが随時の処理には使えない可能性はあります。
（仮に、1順路を1/100秒で処理できたとして、全部で10時間ほどかかる）

saburo0 · Answer

仮に＃１の情報があったとしても、エクセルでは難しいでしょうね
ソフトウェア会社や、カーナビ等のメーカなどに業務委託されることをお勧めします。

saburo0 · Answer

少なくとも、道路情報と、住所とリンクした経度緯度の情報が必要ですね。
これらは用意できますでしょうか。

エクセル 配送順番 計算

いや、各地点間の距離などのコストが正確に分かってるなら、単純に考え得るすべての経路を探索して、最短を求めるだけですよ。

ANo3、4です。

10か所ならば、まずは、10+9+8+7+6+5+4+3+2+1の55ルートを実測して、

#4様が才能の無駄遣いで大変参考になります。

ANo3です。

こんにちは

仮に＃１の情報があったとしても、エクセルでは難しいでしょうね

少なくとも、道路情報と、住所とリンクした経度緯度の情報が必要ですね。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

エクセル配送順番計算