應用可回溯式門檻接受法結合GENIUS求解VRP問題之研究

Abstract

可回溯式門檻接受法(Backtracking Adaptive Threshold Accepting, BATA)是由Tarantilis et al. [38]於2001年提出，它是從門檻接受法演變而來的新型巨集啟發式解法。其主要差異在於門檻值變化並非單調遞減；當找不到可接受的交換時，可允許放鬆門檻值再重新搜尋。本研究以此方法作為基本架構，並與一般化插入/解繫法(GENIUS)和其他傳統鄰域搜尋法相結合，來求解VRP問題，以探討其求解績效。本研究之求解架構包含起始解模組、鄰域搜尋模組和可回溯式門檻接受模組三個部份。並以Christofides et al. [8]的14題國際標竿題庫作為績效評估的測試例題。 本研究首先以循序式的一般化插入法(GENI)產生起始解，再以鄰域搜尋模組改進，其方法共包括解繫法(US)、1-1、2-Opt和Or-Opt等數種。並且以巨網結構的方式建構路線，使其能同時考慮「路線內」與「路線間」的交換。同時，本研究設計了一個能夠擴大解繫法鄰域搜尋範圍機制(Expanded US)，以提高解繫法的搜尋績效。而本研究以C#語言撰寫程式，並在Pentium(R) 4，CPU為3.00GHz的個人電腦測試可回溯式門檻接受模組。結果顯示，傳統上BATA的設定，即門檻回溯比值b<1時，在起始門檻比率0.01、門檻下降比率0.9，以及門檻數列長度180的情況下，14題標竿題目的平均誤差可為1.2%。另外，本研究亦發現，若突破傳統BATA限制，而設定門檻回溯比值b>1時，在起始門檻比率0.02附近的範圍，門檻下降比率0.9以上附近的範圍，以及門檻數列長度180的情況下，可找到更佳的結果，其中最低的14題標竿題目平均誤差更降低至0.87%。表示此種更為放鬆的設計可能可以找到較佳的解。 最後，再與近年來國際期刊之文獻進行比較。本研究14題中共有7題可找到已知最佳解，而各題最佳結果之平均誤差僅為0.26%，且相比之下求解時間亦頗快速，顯示可回溯式門檻接受法可成為相當不錯的求解架構。

Backtracking Adaptive Threshold Accepting (BATA) was first introduced by Tarantilis et al. in 2001 for the distribution of perishable goods. This algorithm is similar to Threshold Accepting (TA) but the values of threshold are lowered or raised, depending on if an acceptable solution can be found in a fixed number of iterations. This research used a BATA structure embedded with GENIUS and other traditional exchange methods for solving the Vehicle Routing Problem (VRP). And the 14 classic instances described by Christofides et al. were selected for the evaluation of our method. The first phase of our proposed metaheuristic is the following. A feasible initial solution was generated by a sequential GENI, and then improved by neighborhood search methods such as US, 1-1, 2-Opt, Or-Opt. Since we presented the solution as a giant tour, both the inter-route and intra-route improvements were considered simultaneously. We also proposed a mechanism named “Expanded US” to enhance the performance of US. In the second phase, we applied BATA to further improve the giant-tour solution. We coded our metaheuristic method in C# and implemented all experiments on a Pentium 4, 3.00GHz personal computer. Results showed that the average deviation of 14 benchmark instances can be 1.2% using traditional BATA parameter b<1. We also tested the case of the threshold backtracking factor b>1 and found that this change could lead to even better results. The average of deviation of the 14 benchmark instances can be reduced to 0.87%. Overall, compared with the recent literatures, among the 14 instances, we found 7 best-known solutions and the average deviation is merely 0.26%. The average computer time is about 50 seconds which demonstrated the efficiency and potential applicability of our proposed method.