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

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

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

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

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

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

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

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

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

一、做個(gè)簡(jiǎn)單的各點(diǎn)相互之間的里程表。如下圖：

二、畫(huà)個(gè)簡(jiǎn)單的坐標(biāo)圖（地圖）更直觀看到各點(diǎn)位置

三、先隨機(jī)畫(huà)幾種方案

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

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

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

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

先把倉(cāng)以外的所有點(diǎn)連成一個(gè)環(huán)，這個(gè)最短路徑的步數(shù)肯定得大于這個(gè)周長(zhǎng)步數(shù)，因?yàn)閭}(cāng)肯定得先到一個(gè)點(diǎn)，再?gòu)母舯诘囊粋€(gè)點(diǎn)回去，這樣他們的路徑肯定大于這2個(gè)點(diǎn)的距離。

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

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

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

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

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

將錯(cuò)就錯(cuò)，為什么在解決方案假設(shè)二的時(shí)候我會(huì)感覺(jué)自己找到對(duì)的方法，因?yàn)槌ＷR(shí)不是邏輯，感覺(jué)很容易就可以畫(huà)出一個(gè)圈，就是他們?cè)撚械木嚯x（最短的圈）。如果我隨機(jī)畫(huà)的點(diǎn)沒(méi)有H這個(gè)點(diǎn)，相信大家都覺(jué)得這個(gè)就是最短的一個(gè)圈了，那如果分步驟來(lái)做，先把H當(dāng)成倉(cāng)，畫(huà)外圍常識(shí)下認(rèn)為最短的圈，再用解決方案假設(shè)二的邏輯來(lái)連線。邏輯上應(yīng)該可以得出最短的路徑。

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

窮舉法，把各種可能性都列出來(lái)，當(dāng)然這個(gè)就沒(méi)有太大的意義，無(wú)法找到快速解決問(wèn)題的方案。除非有一種方式能自動(dòng)窮舉，這樣也是不錯(cuò)。

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