旅行商式配送問題新的簡便解法

□ 陳金莎,王家榮,齊字捧,賈春玉

(寧波工程學院,浙江 寧波 315211)

TSP問題(Traveling Salesman Problem，旅行商問題)，有若干個城市，任何兩個城市之間的距離都是確定的，現要求一旅行商從某城市出發必須經過每一個城市且只在一個城市逗留一次，最后回到出發的城市，問如何事先確定一條最短的線路并保證其旅行的費用最少。該問題是復雜組合優化NP難問題，這類問題相關研究雖然可追朔到圖論中“七橋”問題，但密切相關研究主要從上世紀60年代開始[1、2]，此后，許多學者作了大量研究[3-14],研究成果很多，解法也很多，主要解法有分支限界算法[3]、規劃解法[4-6]、遺傳算法等一些人工智算法[9、10]。每種方法各有利弊，分支限界算法、規劃解法規模小時比較有效，規模大時不一定有效，影響應用推廣；人工智算法繁瑣、求解時間長，有些方法易陷入局部最優，容易陷入早熟、停滯的缺點，不如規劃求解優化程度高；雖然有人用匈牙利法求解[7]，但沒有深入考慮無可行解時情況。因此，有必要給出易于掌握的簡便解、有效解。

1 旅行商配送問題的描述及其數學模型

1.1 旅行商配送問題的描述

設有n-1個需要配送地(共n個節點)，配送中心為節點1，第i個配送地(節點)到第j個配送地(節點)的距離(或行走時間、或運費)Cij，是否行走(相連)變量為Xij第(0，1變量，0代表該2點不行走、不相連，1代表該2點行走、相連)，從配送中心節點1出發，到各需要配送節點各去一次配送貨物，最后回到配送中心節點1。

1.2 旅行商配送問題的數學模型

旅行商配送問題的數學與指派問題數學模型具有3點類似，一是目標函數是總的行走距離(時間或運費)最小；二是變量均為二進制變量(0或1)；三是每行和每列變量之和均為1；不同有2點是，一是當i=j時，Xij為0；二是從第一點出發經過各點一次，最后回到第一點。旅行商配送問題的數學模型[9]如下：

(1)

(2)

(3)

Xij=0/(i=j)

(4)

Xij+Xji≤1i≠j

(5)

Xij+Xjk+Xki≤2i≠j≠k

(6)

?

Xij+Xjk+Xkl+Xls+…+Xpi≤n-2i≠j≠k…≠p共n-1項

(7)

Xij=0or1

(8)

2 新的簡便解法原理

2.1 原有規劃解法的弊端及解決措施

規劃解法規模小時比較有效，規模大時不一定有效，影響應用推廣，為了克服這一問題，我們簡化數學模型，減少約束條件，使之在規模大時求解也有效；由于減少約束條件，多數情況求解結果不是可行解，只少有15%-25%的比例直接獲得最優可行解，為了解決這一矛盾，從分析不是最優可行解的特點入手，加以解決、克服這一弊端。不是可行解，就是沒有滿足從配送中心節點1出發，各需要配送點只去一次，最后再回到節點1。就是至少出現2段聯通線路，沒經過各配送點，提前回到配送中心節點1。解決措施是有2種，方法一，干預行走路徑，不讓它提前回到節點1，使之盡可能經過各配送點，最后回到節點1；方法二，使聯通線路只有1個，使之盡可能經過各配送點，最后回到節點1。這里只采用第一種方法，不讓行走某種路徑方法是強行讓對應變量為0，具有多種可采取的辦法，如最后一步不讓提前回到節點1、換一個分支求解等。選擇幾種干預方法，規劃求解后在可行解中擇優，作為最終近似最優解。

2.2 新的簡便解法具體措施及求解過程

2.2.1 相關假設與描述

①路經類別界定。

第一大類路徑：在沒加干預情況下運用Excel自動規劃求解，給出第一大類路徑，即1、K、H…S、W、1。首端(開始階段)為1、K、H，尾端(結束階段)最后3個節點為S、W和1。

第一大類第一分支路徑：以1、K、H為首端(開頭)順序為第一大類第一分支路徑。

第二大類路徑：在第一大類基礎上，令1到K對應變量為0，再規劃求解，得1、D、E…Q、R、1；則這個為第二大類路徑。

第三大類路徑：在第二大路徑基礎上1、D、E…Q、R、1；令1到D對應變量為0，再規劃求解，得1、M、N…X、Y、1；則這個為第三大類路徑。以此類推，獲得第四、第五大路徑，通常，前三大路徑基本夠用，可獲得滿意可行解。

2.2.2 新解法具體措施及求解過程

措施1：為了提高求解效率和直接獲得最優可行解的概率，只省去數學模型中的約束條件(6)和(7)，其余均保留。

措施2：采用路徑首端干預方法，預顧名思義，就是在首端(開始階段)干預，以第一大類為例：不走第一大類第一個分支K到H，令對應變量為0，求解。可行，停止運算，否則，可繼續干預(第二步)，通常進行二步干預即可停止，換另一個分支求解(因為步驟越多，優化程度越低)。

措施3：采用路徑尾端(結束階段)干預方法，該類方法采取二種方式進行。以第一大類為例，方式1：第一大類分支路徑，最后3個節點為S、W和1。強行不讓走最后倒數第二個路徑S倒W，令對應變量為0，然后再規劃求解，若可行，停止運算，可繼續干預，進行二步即可停止，換另一個分支求解。方式2：第一大類分支路徑，最后3個節點為S、W和1。強行不讓走最后一個路徑W倒1，令對應變量為0，然后再規劃求解，若可行，停止運算，可繼續干預，進行二步即可停止，換另一個分支求解。

措施4：求解第二大類路徑和第三大類路徑，若第二大類路徑獲得可行解，停止運算，否則，采取上述方法繼續干預求解。類似的，若第三大類路徑獲得可行解，停止運算，否則，繼續干預求解。

2.3 新的簡便解法優化程度

最優解下限，在沒有干預情況下獲得規劃其解結果(不一定是可行解)即為最優解下限，可行方案化程度計算公式如下：

優化程度≥[1-(可行解目標函數值-最優解下限)/最優解下限]×100%

3 計算實例

某配送中心給7個客戶配送貨物，配送中心編號為1，其余7各客戶編號分別為1至8，出發點用Ai表述，到達點用Bj表述，相關資料參見表1。是給出優化后的配送方案及總的行走距離。

表1 原始數據sheet1

解:首先進行無干預情況下規劃解,目標函數值為162,既為最優解下限，具有2條聯通線路,一是1、4、2、5、1;二是3、6、8、7、3。方案不可行，變量求解結果參見表2。

其次采用不同干預方法、干預再求解，干預手段是強行令某些變量為0。下面只介紹出現可行解的干預方法：

采用路徑首端干預方法，第一大路經是1、4、2、5、1;強行不讓4到2，令對應變量等于0(編輯Excel軟件計算公式，自動完成)，然后再規劃求解。求解結果為：可行解路徑：1、8、6、3、7、4、2、5、1(編輯Excel計算公式，自動給出路徑)；總距離176，優化程度至少91.4%，變量求解結果參見表3。

采用路徑尾端干預方法，第一大路經是1、4、2、5、1;強行不讓2到5，令對應變量等于0(編輯Excel軟件計算公式，自動完成)，然后再規劃求解。求解結果為：可行解路徑：可行解路徑：1，4，2，8，6，3，7，5，1；總距離167，優化程度至少96.9%，變量求解結果參見表4。

第二大路徑：1、8、6、3、7、4、5、1，總距離176，優化程度至少91.4%；

第三大路徑：1、3、7、4、2、8、6、5、1，總距離180，優化程度至少88.9%；

為了節省篇幅，其它干預方法結果從略，Excel規劃求解參數設計及相關Excel表格因篇幅大從略。10種方法最好的是：

最終選取可行解路徑：1，4，2，8，6，3，7，5，1；總距離167，優化程度至少96.9%。

表2 無干預規劃求解結果(Sheet1)

表3 首端干預方法、分支2規劃求解可行解(Sheet2)

表4 路徑結尾階段干預方法、分支1下規劃求解可行解Sheet3

4 10種解法比較分析

表5 10種方法比較表

隨即選取60個樣本,配送點從4到13不等,各點之間距離多數隨機選取，少量為隨機對稱數據,結果顯示,平均優化程度97.6%以上，第一大類直接獲得最優可行解數為22，占36.7%,。其中小于等于9個配送點(定義為點數少的情況)，次數為14，樣本為32個，占43.7%；大于9個配送點為8次，樣本為28個，占28.6%；可見，配送點越少，直接獲得最優可行解概率越大。其余為干預后獲得可行解，只有一次無可行解(在給定10種方法求解中無可行解,進一步干預獲得可行解)。從第一大類看，尾端干預明顯好于首端干預，第二大類，正好相反。第一大類好結果，明顯高于第二和第三大類，類別數越高，好結果數越少，優化程度也就越低。

5 結論

旅行商配送問題是復雜組合優化問題，雖然可用智能搜索等方法求解，但方法復雜、求解效率不高、優化程度不夠理想。規劃解法雖然優化程度高,但問題規模大時不一定有效，影響其運用及推廣。新解法兼顧優化程度高和求解有效，通過減少約束條件，使之在規模大時求解也有效；通過若干種方法、干預不讓配送提前回到始點，可有效獲得可行近似最優解。模擬試驗證明，只少有15%-35%的比例直接獲得最優可行解，95%以上經過有限10種干預方法可獲得理想的可行近似最優解,特殊情況需要連續多步驟干預獲得可行解。尾端干預明顯好于首端干預。新方法相對簡單、易于掌握、優化程度高，平均優化程度至少在96.7%以上，優化程度理想。