| Summary |
Yu-Jie Liao,2007.06
Department of Transportation Technology and Management National Chiao Tung University
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. |
