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

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

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

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

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

我們可以隨機畫畫一些點，自己畫線串點就容易發現，以上不一定對。如下。

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

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

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

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

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

三、先隨機畫幾種方案

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

四、解決方案設想一

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

五、解決方案設想二

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

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

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

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

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

五、解決方案設想三

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

六、解決方案設想四

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

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