结合门槛接受法与费洛蒙记忆於求解车辆路线问题

1、結合門檻接受法與費洛蒙記憶於求解車輛路線問題卓裕仁1 鄭佳琳21運輸科技與物流管理學系中華大學助理教授300新竹市五福路二段707號.tw2運輸科技與物流管理學系中華大學300新竹市五福路二段707號摘要：門檻接受法(Threshold Accepting, TA)是一種確定性接受劣解的巨集啟發式方法，可深化區域搜尋的強度並跳脫局部最佳解的束縛。螞蟻演算法(Ant Colony Optimization, ACO)則是將隨機搜尋過程中獲得解的資訊，以費洛蒙(Pheromone)的方式記憶在節線中，屬於一種廣度搜尋的巨集啟發式方法。本研究嘗試將ACO的費洛蒙記憶機制導入到

2、TA法的解題架構中，以期提升TA法的解題績效。本文應用32個車輛路線問題(Vehicle Routing Problem, VRP)的標竿例題進行解題測試，結果發現：TA結合費洛蒙記憶的執行架構確實有助於提升求解VRP問題的績效，其平均誤差百分比可達2.87%，且有一題與文獻已知最佳解相同。關鍵字：車輛路線問題、門檻接受法、費洛蒙記憶、巨集啟發式解法1. 前言近幾年來，國內物流業紛紛受到看好。物流業對於運輸配送議題頗為重視，認為有效且正確的運輸配送計畫對低物中心之運輸成本有相當大地影響。而運輸配送計畫中，尤以輛線問題(Vehicle Routing Problem, VRP)最為關鍵。VRP是

3、一個著名的NP-Hard問題，在求解大規模問題時，精確解演算法(Exact Procedure)將無法在有限時間內求得最佳解，因此些學者利用較有效率的啟發式方法(Heuristic Algorithms)來求得近似最佳解。但由於傳統啟發式方法會面臨陷入局部最佳解(Local Optimum)的窘境，以至於無法提供精確度更好的近似解。為了克服這項缺點，近十幾年來，有許多學者開始採用巨集啟發式方法(Meta-Heuristics)求解VRP問題。在眾多的巨集啟發式方法當中，門檻接受法(Threshold Accepting, TA)具有執行容易、速度快、參數敏感度低等優點。TA已被廣泛應用於許多最

4、佳化問題，如：生產排程問題(Job-Shop Scheduling)、旅行推銷員問題(Traveling Salesman Problem, TSP)，及一般化資源限制之計畫排程問題等，皆有不錯的績效。另一方面，螞蟻演算法(Ant Colony Optimization, ACO)係根據螞蟻找尋食物的現象而發展出來具有人工智慧的演算法。ACO具有多重起點與隨機的方式來加強搜尋途徑的多樣化，並將求解過程中的重要資訊以費洛蒙(Pheromone)機制累積記憶在節線上，是近年來頗受重視的一種巨集啟發式方法。由於螞蟻演算法需要搭配強而有力的鄰域搜尋法才能發揮其效果，而門檻接受法在鄰域搜尋方面又有相當不

5、錯的表現；因此，本研究之目的乃希望結合門檻接受法之深度搜尋特點與螞蟻演算法之廣度搜尋特點，發展出一套混合式(Hybrid)的巨集啟發式方法求解VRP問題，來提升求解之效率。本文後續章節安排如下：第二節簡要回顧了TA與ACO的方法概念與發展；第三節提出結合TA與費洛蒙記憶機制的解題架構，並說明各模組的細節設計；第四節說明測試例題題庫與實驗設計，並彙整測試結果進行分析；最後，於第五節提出本研究的結論與建議。2. 文獻回顧2.1 門檻型演算法回顧門檻型演算法(Threshold Algorithms)亦可稱為包容性搜尋法(Generic Search Methods)，其觀念乃是在鄰域搜尋陷入局部最

6、佳解時，採取較鬆的接受法則，亦即接受劣於現解之鄰解，以便脫離局部最佳解的束縛而繼續搜尋下去。屬於這類的方法有：模擬鍛鍊法(Simulated Annealing, SA)、門檻接受法(Threshold Accepting, TA)、大洪水法(Great Deluge Algorithm, GDA)與記錄更新法(Record-to-Record Travel, RRT)等。TA的觀念源自SA，但是其採用確定性的接受法則，只要鄰解與現解的差在門檻值以下就接受，其執行方式更為簡單。1990年Dueck and Scheuer發表TA法時，以一個442節點的TSP例題來驗證其可行性，結果顯示TA可以

7、在很短的時間內找到相當不錯的解。1993年Dueck根據TA的觀念衍生出兩個新的方法：GDA與RRT。SA、TA、GDA與RRT，在接受法則上面有所不同，SA的接受法則為不確定性接受法則，而TA、GDA以及RRT均採確定性接受法則。TA法之控制參數包括：起始門檻比率（T0）及門檻值數列長度（K）。此外，為避免TA發生無法收斂的情形，門檻值數列通常為遞減型態；圖1顯示三種門檻數列遞減型態。圖1、三種門檻數列遞減型態以直線遞減為例，利用控制參數T0與K來產生門檻數列之數值，其公式如式(1)，X0為起始解，而C(X0)則為其目標函數值： (1)以起始門檻值設定來看，Dueck & Scheu

8、er (1990)在提出TA 時所採用的起始門檻值為最佳成本的0.25%、門檻數列長度為30、門檻值遞減型態為梯形遞減。Toussaint (1994)則建議起始門檻值為起始成本的1%、2%及2.5%，門檻值遞減型態為直線遞減或等比遞減。門檻數列長度與起始門檻的設定和數列遞減形態的設定有關，數列長度的設定則會影響計算時間和求解之精確度。一般而言，起始門檻設定比率越高，也會設定較長等門檻數列，使其計算時能逐漸降低成本。楊智凱(民84)根據實證研究之經驗，建議起始門檻值為起始成本的0.2%至1.0%，門檻數列則是採用線性遞減。韓復華與卓裕仁(民89)運用改良式的門檻公式，如式(2)，當中N為節點數

9、。在經過大規模參數測試後結果顯示：解題績效對T0之敏感度較大，T0值不宜過大或過小，以0.2% 1.5%之範圍為佳；K值對解題績效之敏感度較低；K過大解題時間明顯增加但精度改進有限，建議K值不宜超過60。 (2)2.2 螞蟻演算法回顧螞蟻演算法(Ant Colony Optimization, ACO)係根據螞蟻找尋食物的現象而發展出來具有人工智慧的演算法。其基本概念為自然界螞蟻一開始會隨機行走於巢穴與食物之間各個路線，當螞蟻在移動過程中，會分泌一種化學物質：費洛蒙(Pheromone)，藉由費洛蒙的濃度來判斷該行進的路徑，費洛蒙濃度越高，該路徑被螞蟻選擇的機率也越大。因此，基本上費洛蒙是螞蟻

10、間的溝通管道。經一段時間後，螞蟻行經比較短的路徑會較快回巢穴，所以在相同時間內較短的路徑被螞蟻行經次數較多，故費洛蒙濃度高，最後大多數的螞蟻即會依此路線來回於巢穴與食物之間。到目前為止已有許多學者提出了數種不同的螞蟻演算法架構，以下介紹兩種主要的螞蟻演算法。1. 螞蟻系統(Ant System, AS)1996年Dorigo et al.提出的螞蟻系統(AS)為ACO中最早期的版本，運用於求解TSP。AS基本概念為狀態轉換及費洛蒙更新，分別說明如下：(1) 狀態轉換(State Transition)螞蟻藉由選擇城市拜訪，直到所有城市都已被拜訪為止。對於選擇一個城市做為拜訪對象的機率，需要考慮

11、路徑上費洛蒙數量和能見度(Visibility)這兩種因素。根據Random Proportional Rule來選擇拜訪下一個城市，其選擇機率如下： (3)若=0，則螞蟻選擇路徑距離最近的鄰近城市做為下一個拜訪城市；若=0，則螞蟻選擇下一個拜訪城市時，完全不考慮其間路徑距離長短。(2) 費洛蒙更新當所有螞蟻都已產生路線(解)時，會依據式(4)進行費洛蒙更新。 (4)其中，t為疊代次數，m為螞蟻個數，為費洛蒙消散係數，其值介於0與1之間，為路徑費洛蒙總共增加的數量，為螞蟻在路徑上所增加的費洛蒙數量。與的計算公式如下： (5)AS法係重複上述兩個步驟，直到達到停止條件為止。2. 螞蟻群落系統(A

12、nt Colony System, ACS)Dorigo and Gambardella於1997年為了加強求解績效，將AS做了一些修改與改良，並取名為螞蟻群落系統(ACS)，首先運用在TSP。ACS之解題架構如下：(1) 狀態轉換ACS導入一個新的控制參數，其值介於0到1之間，做為確定性移動與隨機性移動之間的門檻值。若隨機亂數值小於或等於則根據式(5)採用確定性移動，即選取費洛蒙數量與能見度相乘積為最大的城市；反之，若小於採用隨機性移動，與AS選擇方式相同。 (6)(2) 全域費洛蒙更新法則在AS係利用全部螞蟻所帶來的貢獻進行更新費洛蒙，但ACS只有在最佳螞蟻產生的路線更新費洛蒙，其更新法則

13、如下： (7) (8)其中，t為疊代次數，為費洛蒙消散係數，介於0與1之間，是從實驗開始後至目前為止最佳解之路線距離長度。(3) 局部費洛蒙更新法則在ACS每隻螞蟻只要選擇完一個城市，即針對所有路徑進行費洛蒙更新，其更新方式為式(9)： (9)其中，有三種設定方式：第一種是令，是一個參數；第二種是令，為起始的費洛蒙濃度；第三種是令。3. 混合型巨集啟發式解題架構設計本研究針對傳統車輛路線問題(VRP)，結合門檻接受法(Threshold Accepting, TA)與螞蟻演算法(Ant Colony Optimization, ACO)之費洛蒙記憶機制，以建構一混合型巨集啟發式演算法，並將其命

14、名為TAANT_VRP。3.1 TAANT_VRP解題架構整套TAANT_VRP的解題架構可分為三個模組，第一個為起始解構建模組，第二個為鄰域搜尋模組，第三個為巨集策略模組。其整個TAANT_VRP之解題架構如圖2所示。TAANT_VRP首先使用最遠起點之最省插入法(Farthest-start Cheapest Insertion, FCI)構建起始解，接著利用路線內節線交換(Intra-route arc exchange)與路線間節點交換(Inter-route node exchange)來改善起始解，最後以門檻接受法(Threshold Accepting, TA)為主要執行架構，然

15、後以螞蟻演算法(Ant Colony Optimization, ACO)之費洛蒙記憶機制記載搜尋過程中各個局部最佳解的目標函數值，並以此費洛蒙值來擾動節線成本，以便跳脫局部最佳解而找到全域最佳解。圖2、TAANT_VRP之求解方法架構圖3.2 起始解構建模組設計根據文獻回顧得知插入法不僅簡單且易執行，然而插入法之插入方式眾多，本研究僅針對最省插入法進行修改，設計出最遠起點之最省插入法來構建起始解。最遠起點之最省插入法可分為以下三步驟：步驟1：考慮未在路線中的顧客點，找出距離場站最遠的顧客點做為路線的第一點。步驟2：開始進行插入顧客點的動作，計算未在路線中的顧客點之插入路線每段的插入成本，然後

16、選擇插入成本最小之顧客點並將該點插入至該路線。步驟3：依此準則循序(Sequential)產生其餘路線，過程中應符合容量限制，直到所有的顧客點都已經接受服務為止。3.3 鄰域搜尋模組設計鄰域搜尋模組可分為路線內改善及路線間改善，在路線內改善採用2-opt、Or-opt(p=1)及Or-opt(p=2)；在路線間改善採用1-0、1-1及1-2。本研究執行順序的設計採用路線內與路線間交叉使用，以NS表示。執行順序如圖3所示。圖3、本研究鄰域搜尋法執行順序圖在Osman(1993)的文獻中指出，執行鄰域搜尋時，尋找可交換的鄰解，決定選擇那一個鄰解進行交換的策略稱為選擇策略(Selection Str

17、ategy)。而一般來說有兩種：(1)最佳改善(Best Improve)策略，即從所有搜尋的鄰解中，選擇一個改善最多的解進行交換；(2)首先改善(First Improve)策略，則是在搜尋過程中，只要能改善就進行交換，在之後又有學者提到第三種選擇策略(3)半最佳改善(Semi-best Improve)，即對特定一點，從所有搜尋的鄰解中，選擇一個改善最多的解進行交換。本研究均採用半最佳改善策略。3.4 巨集策略模組設計本研究在巨集策略模組方面，共設計了三種執行架構，分別為門檻接受(TA)、費洛蒙擾動節線成本(ANT)及門檻接受加上費洛蒙擾動節線成本(TAANT)。前述之執行架構均以鄰域搜尋

18、模組為核心工具。3.4.1 TA執行流程與控制參數TA執行流程如圖4所示，TA的核心搜尋與接受法則如圖5所示。當要執行TA時必須先設定起始門檻值與門檻數列長度，接著按照TA的接受法則決定是否更新現有解。當執行鄰域搜尋有找到新的可行解，必須判斷此可行解與現有解之差值是否在門檻值之下，若是在門檻值之下則接受交換並更新暫優解，若此暫優解優於搜尋過程中目前之最佳解，則更新最佳解。當執行鄰域搜尋法時，依序執行所設定之鄰域搜尋法，而鄰域搜尋法皆執行完後，進行更新門檻值，繼續執行核心搜尋，重新考慮交換情況，直到停止法則成立。執行完後將列出過程中之最佳解。TA在門檻數列收斂型態控制參數方面，根據Althofe

19、r and Koschnick(1991)證明指出，無法明確決定何謂最佳的門檻數列收斂型態，因此本研究只採用等差遞減門檻數列。在起始門檻值(T0)、執行回合數(K)、每次遞減值(Th)控制參數方面，其更新公式如下所示： (10) (11)其中，式(10)為等差遞減每次所減少的值，式(11)為等差遞減的收斂公式。3.4.2 ANT執行流程與控制參數ANT執行流程如圖6所示，ANT的費洛蒙擾動與更新費洛蒙如圖7所示。當要執行ANT時必須先設定執行回合數，接著按照鄰域搜尋法的接受法則決定是否更新現有解。當執行鄰域搜尋，會利用費洛蒙函數記載搜尋過程中各個局部最佳解的成本目標函數值，並以此費洛蒙值來擾動

20、節線成本，然後經由擾動後所找到新的可行解，必須判斷此可行解是否優於現有解，若是則接受交換並更新暫優解，並在此時會更新費洛蒙，而暫優解若優於搜尋過程中目前之最佳解，則更新最佳解。當執行鄰域搜尋法時，依序執行所設定之鄰域搜尋法，而鄰域搜尋法皆執行完後，會判斷有無達到停止法則，若無，則重新考慮交換情況；反之，將列出過程中之最佳解。本研究之ANT費洛蒙更新係以式(6)為基礎，修改成如式(10)，其中為節線上新的費洛蒙值，為節線費洛蒙值之累積量，為費洛蒙濃度消散係數。費洛蒙值()控制參數方面，設定為當搜尋過程中產生解時，會判斷此解的路線是否包含節線，若有則為其成本目標函數值的倒數；若無則為0。 圖4、T

21、A執行流程圖5、TA核心搜尋與接受法則 (12)(13)3.4.3 TAANT執行流程與控制參數TAANT執行流程如圖8所示，TAANT的費洛蒙擾動與更新費洛蒙如圖9所示。當要執行TAANT時必須先設定起始門檻值與門檻數列長度，接著按照TA的接受法則決定是否更新現有解。當執行鄰域搜尋，會利用費洛蒙函數記載搜尋過程中各個局部最佳解的成本目標函數值，並以此費洛蒙值來擾動節線成本，然後經由擾動後所找到新的可行解，必須判斷此可行解與現有解之差值是否在門檻值之下，若是在門檻值之下則接受交換並更新暫優解，並在此時會更新費洛蒙，而暫優解若優於搜尋過程中目前之最佳解，則更新最佳解。當執行鄰域搜尋法時，依序執行

22、所設定之鄰域搜尋法，而鄰域搜尋法皆執行完後，進行更新門檻值，繼續執行核心搜尋，重新考慮交換情況，直到停止法則成立。執行完後將列出過程中之最佳解。圖6、ANT執行流程 圖7、ANT費洛蒙擾動與更新費洛蒙 圖9、TAANT費洛蒙擾動與更新費洛蒙TAANT在起始門檻值(T0)、執行回合數(K)、每次遞減值(Th)及門檻數列收斂型態控制參數方面，其更新公式如同TA方式；而費洛蒙更新公式如同ANT方式。上述所提及這三種執行架構可單獨使用，亦可組合使用於巨集策略模組中，例如先TA再TAANT、先TAANT再TA等。圖8、TAANT執行流程4. 實驗設計與例題測試結果4.1 題庫建立本研究自VRP國際標竿例

23、題題庫中選取32個VRP例題進行績效測試實驗(http:/neo.lcc.uma.es /radi-aeb/WebVRP/)，所有的例題都僅有車輛容量限制，而無最大路線長度限制。首先挑出7題(Christofides等學者所建立)來進行起始解模組、鄰域搜尋模組及大規模參數測試，此為第一階段測試例題實驗測試，希望藉由這7題找出本方法求解最佳解之較佳的參數組合，後續會利用這幾組參數進行第一、二階段VRP測試例題(32個例題)進行驗證測試。兩個階段VRP測試例題之相關設定與已知最佳解如表1和表2所示。表1、第一階段VRP測試例題隨機分佈型態問題（Random Problems）題號例題編號節點數車容

24、量服務時間總服務時間已知最佳解C1vrpnc1501600524.61C2vrpnc2751400835.26C3vrpnc31002000826.14C4vrpnc415020001028.42C5vrpnc519920001291.29集群分佈型態問題（Clustered Problems）C6vrpnc1112020001042.11C7vrpnc121002000819.56註：此符號*表示最佳解來自http:/neo.lcc.uma.es/radi-aeb/WebVRP/表2、第二階段VRP測試例題隨機分佈型態問題（Random Problems）題號例題編號節點數車容量車輛數已知最

25、佳解C8A-n32-k5321005784C9A-n39-k5391005822C10A-n48-k74810071073C11A-n53-k75310071010C12A-n63-k96310091401C13A-n80-k1080100101763C14E-n33-k43380004835C15Kelly09255100014587.09C16A-n45-k6451006944C17A-n55-k95510091073C18A-n63-k1063100101314C19A-n65-k96510091174C20A-n69-k96910091159C21E-n51-k5511605521C2

26、2E-n76-k1476100141021C23E-n101-k81012008815C24E-n101-k14101112141067C25Kelly01240550105646.46C26Kelly0520090056702.73C27Kelly13252100027881.04C28Kelly1724020022666.84集群分佈型態問題（Clustered Problems）C29F-n45-k44520104724C30F-n135-k7135221071162C31F-n72-k472300004237C32B-n68-k96810091272註：此符號*表示最佳解來自http:

27、/neo.lcc.uma.es/radi-aeb/WebVRP/4.2 實驗設計本研究針對方法與所使用模組之組合方式，並設定其執行機制與控制參數的範圍，進行績效測試之實驗設計。整個測試過程可分為以下三個實驗。實驗：針對第一階段測試例題，將TA、ANT及TAANT這三種執行架構進行參數解題績效測試並比較。其目的想找出較佳之參數組合和了解這三種執行架構是否在解題績效上有所差異。其中，在起始門檻值(T0)測試範圍設定為鄰域搜模組內所得的最佳解之0.05至0.25之間，並撘配執行回合數(K)、消散係數()設定不同的數值進行測試。而這些控制參數有許多可能組合，本研究根據前面相關文獻為基礎，選擇各參數項目

28、的測試範圍，TA、ANT及TAANT測試資料及各參數設定範圍如表3所示。實驗二：將實驗所得到較佳之參數組合，挑出10組參數組合，做為巨集策略模組中之組合型執行架構之參數組合，並由於ANT執行架構解題績效不理想，所以不考慮進行組合，而本實驗設計兩種執行順序，種是先TA後TAANT，以TA_TAANT表示；另種是先TAANT後TA，以TAANT_TA表示，然後針對第一階段和第二階段測試例題進行驗證測試與比較。實驗三：在巨集策略模組中之組合型執行架構中，加入如3.3節所述之六種鄰域搜尋方法作為收尾，以期求得更好的解題績效。表3、TA、ANT及TAANT測試資料及參數設定範圍起始解模組鄰域搜尋模組題號

29、T0KTA參數設定範圍FCINS第一階段測試例題(C1C7)0.05、0.1、0.15、0.2、0.2550、100、150ANT參數設定範圍0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.950、100、150TAANT參數設定範圍0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.90.05、0.1、0.15、0.2、0.2550、100、1504.3 結果彙整4.3.1 TA、ANT及TAANT參數解題績效測試與比較1. TA：從表4可發現T0值較小，平均績效較好；而且當K值為150和100時，平均績效均優於K值為50。為了能求得更好的績效並且欲了解回

30、合數(K)值為150和100何者求解績效較好，因此進一歩分析，所以選擇平均績效為9.65%和9.75%的參數組合為基礎，進行測試不同起始門檻值(T0)所得到的求解績效，而設定範圍為0.01至0.09。表4、TA不同起始門檻值與不同執行回合數之平均績效比較TA 回合數(K)起始門檻(T0)15010050總平均誤差(%)平均誤差(%)0.2514.9516.2717.6 16.270.214.1414.8516.315.10.1513.2813.0515.5713.970.113.8313.2415.2514.110.059.759.6515.5611.65從表5得知，當K值為100且T0值為0

31、.01時，平均績效為最好，平均誤差百分比為6.97%。整體而言，當K值等於150時，其求解績效較優於K值等於100。表5、TA之不同起始門檻值在回合數為150和100之平均績效比較TA 回合數(K)起始門檻(T0)100150平均誤差(%)0.0915.710.440.0810.949.10.0715.3810.350.0612.111.990.059.659.750.0410.119.050.039.529.820.029.858.340.016.978.05總平均誤差(%)11.149.652. ANT：由表6得知，不同的消散係數與不同執行回合數之平均績效均為相同，且平均績效並不理想，其平

32、均誤差百分比高達16.82%。表6、ANT不同消散係數與不同執行回合數之平均績效比較消散係數()總平均 誤差(%)回合數(K)50、100、150平均誤差(%)16.8216.823. TAANT：綜合表7、表8和表9可發現當起始門檻值小和回合數大時，能求得較好的績效，因此為了能求得更好的績效，將進一步分析。而由於回合數增加，將增加計算時間，因此為了能節省計算時間，仍保持固定回合數為150，進行測試不同的消散係數與不同起始門檻值，而起始門檻值範圍設定為0.01至0.09。表7、TAANT不同起始門檻值與不同消散係數之平均績效比較(回合數K=

33、150) 消散係數() 起始門檻(T0)平均誤差(%)0.2515.0915.0915.0415.0415.0415.3715.7415.4115.860.214.2915.5414.6415.5415.4313.7513.9814.7114.490.1512.0111.8411.8411.8413.212.5212.2912.6712.770.1121212.1715.7814.7113.3213.7212.911.690.0510.810.5810.269.6211.159.7810.7311.7210.38總平均誤差(%)12.841

34、3.0112.7913.5613.9112.9513.2913.4813.04表8、TAANT不同起始門檻值與不同消散係數之平均績效比較(回合數K=100) 消散係數() 起始門檻(T0)平均誤差(%)0.2516.6116.3416.3416.3416.3414.6115.3615.7516.910.217.1417.3315.916.4717.4916.3216.8715.9115.490.1514.0612.7612.7612.7614.5714.7314.5814.7311.740.113.9813.9813.1113.113.27

35、12.1611.1312.5112.20.0511.3610.659.819.899.9410.749.3810.6610.69總平均誤差(%)14.6314.2113.5813.7114.3213.7113.4613.9113.41表9、TAANT不同起始門檻值與不同消散係數之平均績效比較(回合數K=50) 消散係數() 起始門檻(T0)平均誤差(%)0.2516.7116.7116.7116.7116.7117.7118.4718.4718.470.216.7116.7116.7116.7116.7116.8716.8716.8715.

36、970.1517.8317.8317.8317.8317.6716.1816.3516.3515.720.116.2518.4816.2516.2516.2516.2516.2116.2514.850.0514.1918.4814.9814.9814.9814.6412.4912.5713.77總平均誤差(%)16.3417.6416.5016.5016.4616.3316.0816.1015.76從表10得知，平均誤差百分比介於5.45%與14.13%之間。T0值為0.02且值為0.8時，平均績效是所有參數組合下最好的，其平均誤差百分比為5.45%。表10、TAANT起始門檻值(0.010.

37、09)與消散係數(0.10.9)平均績效比較 消散係數() 起始門檻(T0)平均誤差(%)0.0910.8310.9310.9310.2410.2411.5212.5212.8214.130.0811.249.8510.0610.0611.8410.7710.9911.4710.530.0710.4910.4910.4911.2910.9910.9511.4111.1210.780.069.069.169.049.23610.0510.30.0510.810.5810.269.6211.159.7810.7311.721

38、0.380.0411.169.9610.479.5210.1810.7910.558.548.50.0310.228.297.287.287.186.380.028.075.458.260.018.848.368.367.699.957.648.5810.248.68總平均誤差(%)10.079.649.459.059.869.359.799.8410.054. 將TA、ANT及TAANT所有測試情形下，各自以最佳參數組合下所得的結果，進行績效比較。各自參數組合資料如表11所示。本實驗利用誤差之成對樣本平均數差T檢定，令=0

39、.05，然後進行兩兩相比的檢定方式，以得知這三種執行架構是否有顯著差異。檢定結果顯示：三種執行架構解題績效沒有明顯差異。整體而言，ANT與TA、TAANT有顯著差異；TA與TAANT沒有顯著差異。表11、各自最佳參數組合資料執行架構最佳參數組合TAT0=0.01,K=100,ANTK=150,=0.1(均相同結果，僅列出一組)TAANTT0=0.02,K=150,= 巨集策略模組中之組合型執行架構驗證測試與比較將實驗所得到較佳之參數組合，挑出10組參數組合，如表12所示。做為巨集策略模組中之組合型執行架構之參數組合。表12、較佳參數組合資料編號TATAANT編號TATAANT1

40、K=100T0=0.01(=0.5,K=150,T0=0.01)6K=100T0=0.01(=0.8,K=150,T0=0.02)2(=0.7,K=150,T0=0.01)7(=0.8,K=150,T0=0.03)3(=0.4,K=150,T0=0.02)8(=0.8,K=150,T0=0.06)4(=0.6,K=150,T0=0.02)9(=0.5,K=150,T0=0.02)5(=0.7,K=150,T0=0.02)10(=0.4,K=150,T0=0.01)從表13得知，TAANT_TA之平均誤差百分比為3.3%；而TA_TAANT平均誤差百分比為3.74%，所以TAANT_TA之解題績

41、效略優於TA_TAANT之解題績效。表13、TA_TAANT與TAANT_TA之32題測試例題所得之最佳解例題型態題號已知最佳路線成本TA_TAANTTAANT_TA運算時間a路線成本誤差(%)運算時間a路線成本誤差(%)RPC1524.617.91547.054.28%18.22524.930.06%C2835.2619.14877.555.06%36.91854.562.31%C3826.14129.33842.642%42.56840.251.71%C41028.4297.941063.613.42%220.561073.24.35%C51291.29215.171485.7915.06

42、%251.611463.213.31%CPC61042.11177.721052.470.99%219.281078.413.48%C7819.5670.7819.560%125.63819.560%RPC87845.57870.38%14.557870.38%C982210.068392.07%11.78442.68%C10107310.0211325.5%7.0211486.99%C11101013.4810352.48%10.2410301.98%C12140138.7414332.28%13.814191.28%C13176326.8818213.29%37.6418122.78%C1

43、48357.368633.35%10.028441.08%C15587.0938.74622.736.07%843.69630.37.36%C169449.9210228.26%6.8810228.26%C17107311.6710881.4%13.2810901.58%C18131441.5613381.83%13.713270.99%C19117418.4711911.45%15.8311931.62%C20115917.711912.76%13.2211801.81%C215217.665474.99%17.955240.58%C22102141.2710391.76%17.491059

44、3.72%C2381536.478423.31%38.028403.07%C24106736.0211245.34%32.311184.78%C255646.46396.235832.593.3%602.145760.422.02%C266702.73848.197026.194.83%294.756788.331.28%C27881.04464.39900.842.25%1839.528971.81%C28666.84411.84737.6710.62%890.86741.0311.13%CPC2972410.947321.1%8.227321.1%C301162416.3411973.01

45、%235.4212073.87%C3123743.72495.06%34.282526.33%C32127216.5912982.04%29.5512982.04%平均誤差(%)3.74%3.3% a：單位(sec)。4.3.3 加入六種鄰域搜尋方法作為收尾之解題績效測試由於實驗二測試之32題測試例題，其解題績效似乎不盡理想，故為了能獲得更好的績效，本實驗三將在巨集策略模組中之組合型執行架構之後，再加入六種鄰域搜尋法做最後收尾，以期能獲得更佳的解題績效。測試結果顯示：TA_TAANT加入收尾後，32題平均誤差改善為0.13%；TAANT_TA加入收尾後，32題平均誤差改善為0.01%。4.3.

46、4 加入六種鄰域搜尋方法作為收尾之解題績效測試本研究所有測試情形下，有題與已知最佳解相同，為C7，其他最佳解詳細之參數設定如表14所示。各例題的最佳解平均為2.87%。表14、本研究32題測試例題所得之最佳解例題型態題號執行架構參數組合運算時間(sec)路線成本已知最佳路線成本誤差(%)RPC1*TAANT_TA818.22524.93524.610.06%C2*TAANT_TA436.91854.56835.262.31%C3*TAANT_TA342.56840.25826.141.71%C4TA_TAANT197.941063.611028.423.42%C5TAANT_TA3251.61

47、1463.21291.2913.31%CPC6TA_TAANT2177.721052.471042.110.99%C7*TA_TAANT270.7819.56819.560%RPC8*TA_TAANT75.57877840.38%C9TA_TAANT810.068398222.07%C10TA_TAANT310.02113210735.5%C11TAANT_TA610.24103010101.98%C12TAANT_TA313.8141914011.28%C13TAANT_TA+收尾636.95180717632.5%C14TAANT_TA710.028448351.08%C15TA_TAAN

48、T138.74622.73587.096.07%C16*TAANT_TA76.8810229448.26%C17TA_TAANT311.67108810731.4%C18*TAANT_TA313.7132713140.99%C19TA_TAANT218.47119111741.45%C20*TA_TAANT+收尾314.8117211591.12%C21TAANT_TA817.955245210.58%C22TA_TAANT741.27103910211.76%C23*TAANT_TA338.028408153.07%C24TAANT_TA1032.3111810674.78%C25TAANT

49、_TA+收尾2593.065741.975646.461.69%C26TAANT_TA9294.756788.336702.731.28%C27TAANT_TA81839.52897881.041.81%C28TA_TAANT10411.84737.67666.8410.62%CPC29*TAANT_TA18.227327241.1%C30TA_TAANT+收尾7256.06118611622.07%C31TA_TAANT343.72492375.06%C32*TA_TAANT916.59129812722.04%平均誤差(%)2.87%*有多組參數能達到同樣結果，僅列出組數據作代表。5. 結論與建議5.1 結論本研究嘗試將門檻接受法結合螞蟻演算法之費洛蒙記憶機制應用於求解VRP之問題，乃屬於一種創新的設計。根據本研究混合型巨集啟發式求解VRP之結果，有下列幾點結論：1. 放棄ACO之機遇性特性，僅使用費洛蒙記憶機制，記載過程中各個局部最佳解的目標函數值，並以此費洛蒙值擾動節線成本，其解題績效不甚理想，可能原因為費洛蒙值擾動節線成本過小，因而跳脫不出局部最佳解。2. 針對第一階段測試例題，TAANT與TA其解題績效沒有明顯的差異，但TA