友情提示：本文將在上一篇推送的基礎(chǔ)上探討有條件的多旅行商問題，因此在閱讀本篇內(nèi)容前請先觀看上一篇的內(nèi)容：

模擬退火解決“多旅行商問題”

（點擊上方標(biāo)題查看）

上一篇推送中，我介紹了用模擬退火求解MTSP(多旅行商問題)的思路，模擬退火里面最重要的一個步驟就是如何定義解以及怎么去產(chǎn)生新解，假設(shè)現(xiàn)在有n+1個城市，第0號為起始城市，其他城市編號為1至n，一共有m個可以派遣的旅行商，那么我們生成的解應(yīng)該為：

m-1個0 和 1至n 組成的一個隨機排序

而產(chǎn)生新解的方法和TSP中一致，分別是交換法，移位法和倒置法。

如果大家動手編程實現(xiàn)了上文的思路的話，應(yīng)該會發(fā)現(xiàn)下面這個現(xiàn)象：無論初始旅行商的個數(shù)是多少，我們得到的最優(yōu)解中都只有一個旅行商參與了旅行，其他的旅行商都不出門（也就是最終得到的解中，m-1個0位于整個序列的最前面或者最后面），那么這時候的MTSP問題退化為了TSP問題。

為什么會出現(xiàn)這個現(xiàn)象呢？其實你好好考慮下也不難理解：MTSP中多個旅行商都要從起始城市出發(fā)最終再返回到起始的城市，這里面實際上就造成了旅行效率的降低。

以2個旅行商為例，假設(shè)起始城市用圖中紅色的*表示，下圖是兩個旅行商都參與旅行時繪制出來的圖像，如果我們只讓一個旅行商參與旅行的話，得到的總旅行距離一定會小于等于現(xiàn)在的距離。

我們只需要利用初中學(xué)的兩邊之和大于第三邊就能證明這一點，將下圖中原來的x和y兩個邊去掉，并增加一個新的邊z，很明顯z≤x+y：

從上圖可以看出，這個時候整個路徑構(gòu)成了一個閉環(huán)，即形成了TSP的解。

同樣的道理，如果參與旅行的旅行商數(shù)量更多，那么最終經(jīng)過的路徑也會越大，這就是MTSP得到的解總會變得和TSP一樣的原因。

那么，多旅行商問題存在的意義是什么呢？

答案是可以加入限制條件！

比如我們這里可以加入一個或者多個這樣的限定條件：

（1）每個旅行商訪問的城市數(shù)量有一個限制范圍，例如不超過10個城市，不少于5個城市；

（2）每個旅行商總的旅行距離有一個限制范圍；

（3）需要訪問的城市上存在著時間上的約束，例如派遣專家去各地調(diào)研，A地接待時間是7月10日至15日，B地接待時間是7月13日至19日，C地……

事實上在上個推送中我們提過，在運籌學(xué)中有一個很著名的問題：車輛路徑問題（Vehicle Routing Problem,VRP），這個問題有很多種不同的變形（引入了不同的限定條件），也是運籌學(xué)界目前研究的熱點問題之一，我們介紹的多旅行商問題就是車輛路徑問題的一種，因此VRP這才是正統(tǒng)問題！大家在看完本節(jié)的推送后，可以自己搜索VRP中里面相對較為簡單的CVRP和VRPTW，如果能解決這兩個問題的話，解決其他更難的問題也會有很好的思路了。

那么，怎么用模擬退火解決這種帶有約束條件的問題呢？

這里給大家一點思路，我們可以在模擬退火的目標(biāo)函數(shù)中動手腳，只需要在目標(biāo)函數(shù)中加入違背約束的懲罰項即可！

這里我舉一個簡單的例子，假如現(xiàn)在有101個城市，其中0號城市是起始城市，有5個旅行商可以供你調(diào)遣，且按照計劃每個旅行商最多能訪問m個城市。假設(shè)每個旅行商每單位行程你需要支付的差旅成本為10元，每派遣一個旅行商的固定成本為10000元，如果某個旅行商訪問的城市數(shù)超過了m個，則需要給予一定的補償費，每多出一個城市給予的補償費為x元，那么怎樣安排旅行商的分配方案可以使得總的成本最低？那么在模擬退火算法中，你的目標(biāo)函數(shù)應(yīng)該是怎樣的呢？

10*總行程長度+10000*派遣的旅行商個數(shù)+補償費

這里的補償費實際上就是我們對違背了最大訪問城市約束的一個懲罰，如果這里的x取得特別特別大的話，那么公司在安排任務(wù)時絕對不會選擇讓某個旅行商去超過最大訪問城市數(shù)的方案；如果x取得較小的話，公司可能會權(quán)衡這個補償費用和其他兩項花費的大小，而這不就是很多企業(yè)選擇讓員工加班的理由嗎？

因此，在有約束的MTSP編程進行求解中，我們需要做的就是改變這里的目標(biāo)函數(shù)的計算，而以上的分析過程就是我們整體建模的思路！

希望大家在這兩篇推送中能有所收獲，如果覺得講的不錯的話，請在本文下方點贊支持哦！