在城市配送中或者快遞員送貨，都會存在一個問題，怎么跑路徑最短。當然現(xiàn)實中送貨都是靠司機的經(jīng)驗，或者看下地圖大概就知道怎么跑了，沒有人真的去算路徑是不是最短。但是從物流管理者角度，還是有必須知道邏輯，這樣才能合理決策。

今天先分享下單環(huán)模型（TSP），即就一輛車剛好裝滿，一輛車出去跑多個點送貨，然后再回到起點?，F(xiàn)實中更多是多輛車出發(fā)跑不同的點，即多環(huán)模型（VRP），多環(huán)模型出來后，具體到單個司機還是得用單環(huán)模型來設(shè)計路線。

在如何設(shè)計距離最短，有個著名的原理大家一定要先懂，這個初中的時候都學過：三角形兩邊之和大于第三邊。這個很好理解，因為已經(jīng)是我們的常識了。但是立馬想到跟最短路徑關(guān)系，還是有點難度。我們做個簡單的例子：從倉庫出發(fā)送2-3個客戶，然后回倉庫。如下圖：

我們做個簡單的判斷：路徑不能有交叉，交叉會產(chǎn)生三角形，就會存在兩邊之和大于第三邊，即路徑不是最短。

我們把上面的判斷當成一個原則，即要路徑最短必須遵守這個原則。接下來再想想如何路徑最短。目前流行的最簡單算法是最近鄰點法，這個算法很容易接受，也很容易感覺是對的（小編一段時間都覺得這個方法很好），但是不一定對的。它的做法就是從倉出發(fā)，先到最近的點，下一步判斷還是最近的點，以此類推。就會給人一種每一步?jīng)Q策都是最短路徑，所以加起來就是最短路徑。但是，這結(jié)論實際有2個疑點：①每一步最短全程就是最短嗎？②即使①是最短，最后一步回倉路徑加進去也是最短嗎？下面我們舉例證明。

我們可以隨機畫畫一些點，自己畫線串點就容易發(fā)現(xiàn)，以上不一定對。如下。

從證明過程可以看出。最近鄰點法，前面每一段都是最短不一定全程是最短的，它違背了上面所說的原則：路徑規(guī)劃不能有交叉，否則就不是最短。以上提供了2種案例，而這2種案例在現(xiàn)實中概率也挺大的。另外，最近鄰點法還存在一個問題，就是當在一個點上，出現(xiàn)多個同樣距離的點，如何做選擇？

以上，只是小編在用最近鄰點法的時候發(fā)現(xiàn)的幾個特例。目前關(guān)于最短路徑的算法很多（Dijkstra算法，Bellman-Ford算法，F(xiàn)loyd算法和SPFA算法等都是聽起來很高大上的算法，但是都沒有找到能用簡單的數(shù)學說明清楚的，也可能是我自己沒有找到），大部分都是高等的數(shù)學計算，所以最近鄰點法還是比較適合多數(shù)人簡單的規(guī)劃路徑。

那么具體如何操作呢？（小編邊想邊寫，希望這個是異議很大的文章，說明大家都有更好的解決邏輯）

一、做個簡單的各點相互之間的里程表。如下圖：

二、畫個簡單的坐標圖（地圖）更直觀看到各點位置

三、先隨機畫幾種方案

第1種就是用最近鄰點法來畫的是40步，第3張圖是38步更短。這個只是小編隨機畫幾個，看能否找到規(guī)律，結(jié)果證明最近鄰點法還是不奏效。

四、解決方案設(shè)想一

通過上圖小編想了是否能畫出的圖的面積表示路徑最短，這個好像計算更復(fù)雜，也不好數(shù)據(jù)證明這個猜想是對的（但是是否用直觀感覺圖3的面積更小，你用所有外圍的點看成一個面積，這個是同樣的大小，減去凹進去部分面積，凹進去面積大就說明畫圖的面積?。?。

五、解決方案設(shè)想二

先把倉以外的所有點連成一個環(huán)，這個最短路徑的步數(shù)肯定得大于這個周長步數(shù)，因為倉肯定得先到一個點，再從隔壁的一個點回去，這樣他們的路徑肯定大于這2個點的距離。

那么接就就得算一個值，如果倉與相鄰的2個點之間距離和減去這2個點之間的距離得出的值最小，說明是最短路徑。這樣就得再制作一個表格出來，才能快速看到這個結(jié)果。

根據(jù)上述的猜測得出的2個線路圖都是40步，其中一個跟最近鄰點法結(jié)果一樣。說明這個方案假設(shè)還是有不足之處，無法得出最短路徑。

但是這個邏輯上感覺還是能講得通的，為什么不是最短？需要再驗證下輸入的條件是否對，邏輯是否對。①先說條件一：我畫的36步的外環(huán)是不是最少步數(shù)的外環(huán)（這個證明要跟題目一樣了）②條件二，再對比38步的那個圖會發(fā)現(xiàn)，我們要移動框框的步數(shù)跟現(xiàn)實的直線算距離不一樣，從38步圖可以看出倉到F加上倉到H的距離是等于F和H的距離，所以才會出現(xiàn)這個圖是最短（小編為了好體現(xiàn)距離，用了推箱子的步數(shù)來代替）。

所以轉(zhuǎn)了一圈感覺沒有得出什么。這個邏輯的前提是我能知道不含倉的環(huán)是最短的，如果把其中的點當成倉就直接可以畫出最短路徑了。我把我要證明的東西當成前提了，然后再證明怎么做能得出它。（最近腦子真不好使，哈哈）

五、解決方案設(shè)想三

將錯就錯，為什么在解決方案假設(shè)二的時候我會感覺自己找到對的方法，因為常識不是邏輯，感覺很容易就可以畫出一個圈，就是他們該有的距離（最短的圈）。如果我隨機畫的點沒有H這個點，相信大家都覺得這個就是最短的一個圈了，那如果分步驟來做，先把H當成倉，畫外圍常識下認為最短的圈，再用解決方案假設(shè)二的邏輯來連線。邏輯上應(yīng)該可以得出最短的路徑。

六、解決方案設(shè)想四

窮舉法，把各種可能性都列出來，當然這個就沒有太大的意義，無法找到快速解決問題的方案。除非有一種方式能自動窮舉，這樣也是不錯。

今天“找不到邏輯”得思考了這些，感覺應(yīng)該會有很大爭議，我就當拋磚了，歡迎大家向我砸玉。|