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

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

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

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

1 旅行商配送問題的描述及其數(shù)學(xué)模型

1.1 旅行商配送問題的描述

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

1.2 旅行商配送問題的數(shù)學(xué)模型

旅行商配送問題的數(shù)學(xué)與指派問題數(shù)學(xué)模型具有3點類似，一是目標(biāo)函數(shù)是總的行走距離(時間或運費)最小；二是變量均為二進制變量(0或1)；三是每行和每列變量之和均為1；不同有2點是，一是當(dāng)i=j時，Xij為0；二是從第一點出發(fā)經(jīng)過各點一次，最后回到第一點。旅行商配送問題的數(shù)學(xué)模型[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 原有規(guī)劃解法的弊端及解決措施

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

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

2.2.1 相關(guān)假設(shè)與描述

①路經(jīng)類別界定。

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

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

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

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

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

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

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

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

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

2.3 新的簡便解法優(yōu)化程度

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

優(yōu)化程度≥[1-(可行解目標(biāo)函數(shù)值-最優(yōu)解下限)/最優(yōu)解下限]×100%

3 計算實例

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

表1 原始數(shù)據(jù)sheet1

解:首先進行無干預(yù)情況下規(guī)劃解,目標(biāo)函數(shù)值為162,既為最優(yōu)解下限，具有2條聯(lián)通線路,一是1、4、2、5、1;二是3、6、8、7、3。方案不可行，變量求解結(jié)果參見表2。

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

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

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

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

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

為了節(jié)省篇幅，其它干預(yù)方法結(jié)果從略，Excel規(guī)劃求解參數(shù)設(shè)計及相關(guān)Excel表格因篇幅大從略。10種方法最好的是：

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

表2 無干預(yù)規(guī)劃求解結(jié)果(Sheet1)

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

表4 路徑結(jié)尾階段干預(yù)方法、分支1下規(guī)劃求解可行解Sheet3

4 10種解法比較分析

表5 10種方法比較表

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

5 結(jié)論

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