改進蜂群算法求解大規模著色瓶頸旅行商問題

董文永，董學士，王豫峰

（武漢大學計算機學院，湖北 武漢 430072）

1 引言

著色旅行商問題(CTSP，colored traveling salesman problem)[1-4]可應用于具有部分重合工作區的多機器工程系統(MES，multi-machine engineering system)的規劃問題。瓶頸旅行商問題(BTSP，bottleneck traveling salesman problem)[5-9]是 TSP 問題的一種變化模型，其目標是最小化旅行回路的最大邊，可應用于工作流的規劃等領域。雖然 CTSP與BTSP可處理一些實際問題，但不能用于建模有部分重合區域的易于人員與車輛調配的路線優化問題，因此，本文探討一種分析模型CBTSP，可建模具有合作與單獨任務的人員與車輛調配的路線規劃問題，該問題的目標函數是最小化所有旅行路線的最大邊[10]。在智能交通、多任務協作等領域，一些實際問題都可用 CBTSP來建模，所構建問題模型的尺度往往趨向于大規模，即對應城市數量在幾千或以上，因此，研究大規模的 CBTSP問題及其求解算法有一定的實際意義。此外，CBTSP在一定條件下，可轉化為CTSP、BTSP和TSP等組合優化問題，因此探索可行的 CBTSP求解算法可對其他相關優化問題的研究有借鑒意義。相關文獻的研究已證實，蜂群算法求解TSP等組合優化問題表現出較好的性能，基于此，本文將一種改進的蜂群算法應用于求解大規模CBTSP問題。

CTSP是近年剛被提出的問題，目前在這方面的研究文獻較少。東南大學李俊等[1-2]將遺傳算法(GA)貪心遺傳算法(GAG)、爬山法遺傳算法(HCGA)與模擬退火遺傳算法(SAGA)應用在求解小規模的CTSP問題，即該問題的城市數量小于或等于101。之后，文獻[3]應用一種可變的臨近搜索算法求解CTSP，進一步提高了已有算法求解該問題的性能；文獻[4]給出了一種基于多任務學習的蟻群算法求解CTSP，并將問題所對應的城市數目拓展到1 002。BTSP問題的部分研究工作包括：相鄰信息序列的排序可以映射成為 BTSP，文獻[5]采用一種近似算法求解該問題；文獻[6]對不對稱BTSP問題的算法、復雜性和經驗分析進行了研究；Ahmed應用混合遺傳算法優化BTSP問題，并通過實驗證實該算法的有效性[7]；此外，文獻[8-9]也對 BTSP進行了相關的研究。文獻[10]給出了著色瓶頸旅行商問題，并提出了一種混合算法求解該問題，其中 CBTSP問題的規模（即對應的城市數量）小于或等于2 361。近年來，大規模優化的部分相關工作包括：Cheng等給出了一種可用于大規模優化的競爭種群優化器，引入一種成對的競爭機制，求解過程中失去競爭力的粒子將進行更新[11]；針對大規模市內路網的信號劃分優化，Ye等設計了一種分層模型預測控制方法[12]；求解大規模黑箱優化問題，Omidvar等設計了一種快速和多精確差分分組方法[13]；Zhang等提出了一種決策變量聚類的演化算法求解大規模許多目標優化問題[14]；Hu等針對大規模優化，給出了一種快速相依性識別的協同演化算法求解該問題[15]。

本文探討了一種問題模型CBTSP，該模型可建模含有協作與單獨任務的人員與車輛調配的路線規劃和優化問題，并將改進蜂群算法應用在求解大規模CBTSP問題，該算法首先利用m-tour編碼方法生成問題的可行解，然后運用產生鄰近解的方法對蜂群算法求解該問題做進一步的優化，從而得到問題的最優解。通過實驗表明，IABC算法求解大規模CBTSP是有效的，該算法的求解質量優于對比算法。

2 著色瓶頸旅行商問題

2.1 CBTSP問題

CBTSP問題[10]含有m個旅行者和n個城市，其中m,n∈Z={1,2,3,…},m＜n。CBTSP可被定義為一個完全圖G(V,E)，V={0,1,2,…,n-1}表示城市集，每個邊edge (i,j)∈E,i≠j。城市集V被分成m+1個非空集，包括m個獨享城市集Vi，?i∈Zm={1,2,3,…,m}表示只有旅行者i能訪問，以及一個共享城市集U，可被所有的旅行者訪問。定點di表示站點，是旅行者i的起始點。在CBTSP中，變量xijk(i≠j,i,j∈V,k∈Zm)表示第k個旅行者是否經過城市i到j。

CBTSP的目標函數表達式為

式(1)表示最小化整個旅行回路的最大邊。

CBTSP問題的限制條件為[10]

式(2)為旅行者開始和終止于站點。

式(3)表示獨享城市只能被指定的旅行者訪問，其他旅行者無權訪問。

式(4)為旅行者l(≠k)不是開始和結束于第k個城市集。

式(5)表示除站點外其他城市只能被訪問一次。

式(6)為所有旅行者同時訪問和退出U。

2.2 CBTSP相關理論

CBTSP是非確定性多項式（NP, non-deterministic polynomial）難問題[1]：根據已知文獻，CTSP是NP難問題，而CBTSP通過改變目標函數，可以轉化為 CTSP，改變目標函數不會引起其復雜度的變化，因此CBTSP也是NP難問題。此外，CBTSP可以在一定條件下，即共享數據集為空集時，轉化為多個單一的BTSP問題，因為BTSP屬于NP難問題，而該形變操作不會引起模型時間復雜度變化，所以CBTSP屬于NP難問題。

2.3 CBTSP與CTSP及其BTSP

CBTSP與CTSP的異同點如下。它們都有共享城市集和獨享城市集，具有相同的限制條件和訪問規則，每個城市只能被訪問一次。但是它們有不同的目標函數，CBTSP的目標函數是使得所有哈密爾頓回路的最大的邊最小化，CTSP的目標函數是使所有旅行回路的總的旅行長度最小。

CBTSP與BTSP的異同點如下。它們具有相同的目標函數，都是 TSP問題的變化模型。但是CBTSP有多個旅行者，可建模含多個旅行者多任務的優化問題，而BTSP只能建模單個旅行者單個任務的問題，它們有不同的限制條件和訪問規則。

3 改進蜂群算法求解CBTSP問題

3.1 人工蜂群算法

人工蜂群算法（ABC，artificial bee colony）[16-19]是一種較新的群體智能算法，該算法模擬蜂群覓食的機制，蜂群可分為3類: 采蜜蜂、觀察蜂和偵察蜂。優化問題的一個解由一個食物源的位置來表示，每個食物源的花蜜量表示對應解的適應度值，種群的大小為采蜜蜂和觀察蜂的數量。

蜂群算法求解問題的具體步驟如下。

首先，隨機產生一個初始的種群P，內含Np個解D維的決策變量Xi={xi,1,xi,2,…,xi,D}，Xi由下界Xmin與上界Xmax定義。

其中，i=1,2,…,Np,j=1,2,…,D。

蜂群算法中，一個采蜜蜂使用式(8)從前一個候選解Xi產生一個候選解Vi。

其中，k∈{1,2,…,Np}和j∈{1,2,…,D}是隨機選擇指數，k≠i，φij表示在[-1, 1]的隨機數。

與采蜜蜂不同，觀察蜂使用如式(9)的概率值pi選擇一個位置訪問來求解問題。

其中，fiti表示第i個解的適應度值。在該過程中，采蜜蜂與觀察蜂可交換信息。

在觀察蜂選擇一個解之后，觀察蜂運用式(8)產生一個新解，貪心選擇應用于新的解和以前的解，采蜜蜂也是如此。當解在預先設定的循環不能被改進和優化時，此解將被舍棄，然后，對應的采蜜蜂變成偵察蜂，偵察蜂再通過式(7)產生一個新解[16]。

3.2 改進蜂群算法

改進蜂群算法是一種蜂群算法與局部優化相結合的算法，通過優化方法使蜂群算法獲得的解得到進一步提升，求解CBTSP的具體介紹如下。

3.2.1 編碼方案

本文采用的m-tour編碼[20]方案用一組m個旅行者來表示 CBTSP問題的一個解。例如，如圖 1所示，有一個11個城市3個旅行者的CBTSP問題，城市1和城市2屬于旅行者1的獨享城市，城市3和城市4是旅行者城市2的獨享城市，城市5和城市6屬于旅行者3的獨享城市，城市7～城市11為3個旅行者的共享城市。用 m-tour編碼方法表示CBTSP問題的一個解（不包括起始點）：旅行者 1的訪問順序為(1, 2, 9, 10)，旅行者2的訪問序列為(3, 4, 11)，旅行者3的訪問順序為(5, 6, 7, 8)。

圖1 表示CBTSP的m-tour編碼方法

3.2.2 觀察蜂選擇蜜源的概率

采用二重錦標賽選擇方法[20](binary tournament selection method)來選擇觀察蜂的一個蜜源。Pcopy位于預先定義的初始值Pmincopy和預先定義的最終值Pmaxcopy之間。Pcopy定義為

如果在一個設定的次數limitnoimp之后，采蜜蜂的解仍然沒有得到改善，采蜜蜂及其蜜源將被放棄，采蜜蜂變成偵察蜂。通過隨機產生一個解與偵察蜂相聯系，偵察蜂可以再次變成采蜜蜂，偵察蜂的解通過相同的方式產生并設為初始解。

3.2.3 產生鄰近解的優化方法

ABC可以使用局部優化進一步改善問題的解，在求解過程中，本文通過產生鄰近解（GNS，generate neighboring solution）[20]進行優化，并在該過程中引入二個限制和優化條件。

GNS是對CBTSP解的訪問序列進行部分刪除和重插入操作，并在重插入時進行優化。例如，CBTSP的解S路徑為 1—2—9—10—3—4—11—5—6—7—8，通過概率Pcopy將部分城市刪除，并產生一個臨近解S′，假設刪除的城市為10、3、4、11，再將這些刪除的城市重新插入到S′訪問序列中。重新插入時有2個限制和優化條件，一個是獨享城市只能插入到指定的旅行商的訪問序列；共享城市可以插入到任意的序列，另一個是插入的城市位置使整個旅行回路的最大的邊最小。重新插入之后，新解S′的訪問序列可能為 1—2—9—11—4—3—10—5—6—7—8，如果S′優于S，就用S′替換S。

在算法1中，5)～11)表示將S訪問序列的部分城市刪除，未刪除的城市賦值到S′，刪除的城市賦值到未賦值的城市集。13) 將未賦值的城市集的城市c重插入S′中，該處有2個限制和優化條件：第一，獨享城市只能插入到特定的旅行商訪問序列；第二，重新插入城市的位置使整個旅行回路的最大的邊最小。

3.2.4 改進蜂群算法求解CBTSP步驟

蜂群算法通過使用算法1對問題的解優化。算法2表示改進蜂群算法求解CBTSP的步驟[20]。

算法 2 中，6)～11)為采蜜蜂階段，12)～18)為觀察蜂階段，19)～22)為偵察蜂階段。IABC分別在采蜜蜂和觀察蜂兩個階段調用算法 1（產生鄰近解）對求解問題的解進行優化。

4 實驗與分析

實驗計算機的運行環境為 AMD AthlonTMII X4 3.01 GHz處理器和3.25 GB RAM。實驗是用Java平臺進行設計與開發。表1為CBTSP的實驗數據，其中，1～14為小規模，15～27為中規模，28～49為大規模。

表1 CBTSP的實驗數據

表1中有3種不同規模的CBTSP數據。n表示城市數量，其取值范圍從21到9 849；m表示旅行者數，其取值范圍從2到60；s表示共享城市的數量；e表示獨有城市的數量。小規模和中規模的部分數據，即n的取值為21到101的數據，來自文獻[1]，大規模的數據由原始TSP數據制作而成，該TSPLIB 對稱性TSP數據已在網上公開。

GA、GAG、HCGA與SAGA算法來自文獻[1]，根據相關實驗該文獻的算法參數設置可使算法獲得較好的求解結果，參數設置具體如下：種群大小為30，交叉概率為0.7，變異概率為0.1。SAGA其他的參數設置如下：初始溫度為 100，總的冷卻時間為60，每個溫度的步長為30，模擬系數0.9。蜂群算法和改進蜂群算法的參數為：limitnoimp設置為100，Pmincopy為0.2，Pmaxcopy為 0.9。圖2～圖6、表 2和表3中所有算法的最大未更新迭代次數均相同。

圖 2(a)～圖 2(d)分別為當n=31與m=4時，GAG、HCGA、SAGA與IABC求解CBTSP問題的運行界面。

圖3(a)～圖3(d)分別為當n=51和m=5時， HCGA、SAGA、ABC、IABC求解CBTSP。

圖 4(a)～圖 4(d)分別為當n=101與m=7時，GAG、HCGA、SAGA與IABC求解CBTSP問題。

圖5(a)～圖5(d)分別為n=431與m=40時，HCGA、SAGA、ABC與IABC求解該問題。實驗詳細情況如下：HCGA平均解是17 106.4，時間為0.2；SAGA平均解為16 873.4，時間為0.3；ABC平均解為14 477.3，時間為0.03；IABC平均解為10 318.6，時間為0.6。

圖 6(a)～圖 6(d)分別為當n=655與m=33時，GAG、HCGA、SAGA與IABC求解CBTSP問題。求解詳細情況如下：GAG平均解為14 610.9，時間為0.3；HCGA平均解為14 231.0，時間為0.3；SAGA平均解為13 626.8，時間為0.6；IABC平均解 13 248.7，時間為0.9。從該實例數據可看出，IABC平均求解質量最優。

表2和表3為6種算法求解CBTSP實驗。

表 2表示 GA、GAG與 HCGA求解大規模CBTSP問題的實驗數據，表中n表示城市數量，m表示旅行者數目，最優解、最差解與平均解均為算法的求解質量，分別表示算法求解CBTSP運行10次的最優解、最差解和平均解，時間為運行 10次的平均求解時間。從表可以看出，HCGA和 GAG求解該問題的求解質量要好于GA。

圖2 當n = 31和m = 4時GAG、HCGA、SAGA與IABC求解CBTSP最優路線

圖3 當n = 51和 m = 5 時HCGA、SAGA、ABC與IABC求解CBTSP最優路線

圖4 當 n = 101與m = 7時 GAG、HCGA、SAGA與IABC求解CBTSP最優路線

圖5 當 n = 431與m = 40時HCGA、SAGA、ABC與IABC求解CBTSP最優路線

圖6 當 n = 655與m = 33時 GAG、HCGA、SAGA與IABC求解CBTSP最優路線

表2 GA、GAG與HCGA求解大規模CBTSP的實驗數據

表3 SAGA、ABC與IABC求解大規模CBTSP的實驗數據

表3的最優解、最差解與平均解均表示算法的求解質量，分別為算法求解CBTSP運行10次的最優解、最差解和平均解，時間為運行 10次的平均求解時間。從表3可以看出，IABC求解CBTSP問題的求解質量要好于SAGA和ABC。圖7和圖8分別為IABC與HCGA等6種不同算法在相同終止條件下，求解CBTSP的平均求解質量。

圖7 算法求解CBTSP的平均求解質量對比

圖8 算法求解CBTSP的平均求解質量對比

圖7中，橫軸表示實例的序號，每個序號對應著一個實例數據，縱軸表示算法的平均求解質量，單位為千米（km）。從圖7可看出，IABC求解CBTSP的平均求解質量要好于 ABC、GA、GAG、HCGA和SAGA，表明改進蜂群算法求解該問題的有效性。IABC使用產生鄰近解的方法來優化問題的解，求解該問題可產生更好的解，從圖7可以看出，IABC的求解質量總體上要好于其他對比算法。

圖8的橫軸表示各個實例的序號，縱軸表示算法求解該問題的平均求解質量，單位為km。從圖8可以看出，GA的求解質量最差，其他幾種算法的平均求解質量相差不大，而且在使用不同的實例數據時每種算法的求解質量存在差異，在6種算法求解該問題中，IABC的平均求解質量表現較好。

表4和表5為相同的迭代時間為終止（停機）條件的5種算法求解大規模CBTSP問題的求解質量，從表4、表5的數據對比可看出，IABC的求解質量要好于GA、GAG、HCGA和SAGA。

表4 GA、GAG與HCGA求解大規模CBTSP的求解質量

表5 SAGA與IABC求解大規模CBTSP的求解質量

為充分驗證算法求解問題的有效性，用文獻[21]實驗的最優解的百分偏差PDbest和平均解的百分偏差PDav，對算法求解CBTSP問題進行顯著性分析，結果如表6所示。

表6中PDbest計算方法為算法當前最優解減去已知最優解，然后除以已知最優解，再乘以 100；PDav計算方法是算法當前平均最優解減去已知平均最優解，然后除以已知平均最優解，再乘以100[21]。

表6為GA、GAG、HCGA、SAGA、ABC和IABC求解CBTSP的百分偏差數據，表中給出了最優解偏差PDbest和平均解偏差PDav，最后給出6種算法求解該問題的百分偏差數據的總均值。從該實驗數據可看出，IABC的PDbest與PDav值在6種算法中最小，表示IABC求解質量在6種對比算法中最優。

IABC是先進的群體智能算法，在求解旅行商等組合優化問題可表現出較好的性能，從以上圖表分析可看出，該算法求解大規模的CBTSP的求解質量要優于其他幾個對比算法。IABC不僅使用ABC算法的優化機理，而且還運用產生鄰近解的優化方法來進一步提升蜂群算法的求解質量，所以有更好的求解性能，因此求解大規模CBTSP問題的求解質量要好于ABC、GA、GAG、HCGA和SAGA算法。

5 結束語

針對現存實際問題，在CTSP與BTSP基礎之上，本文探討了一種 CBTSP路線規劃分析模型，可以應用于含合作和獨有任務并有部分重合工作區域的人員與車輛的路線優化問題，并將改進蜂群算法應用在求解 CBTSP之中。廣泛的實驗與分析表明，該算法對大規模 CBTSP問題的求解質量要優于相關的對比算法。

進一步的工作包括：1) 繼續研究CBTSP問題及其相關的應用領域，使其在多任務協作、智能交通等領域有更加廣泛的應用；2) 可以將本文的算法應用于求解其他大規模優化問題。

表6 算法求解大規模CBTSP問題的實驗百分偏差數據