Randomized gravitational emulation search algorithm for symmetric traveling salesman problem

This paper presents a new heuristic method called randomized gravitational emulation search (RGES) algorithm for solving symmetric traveling salesman problems (STSP). This algorithm is found upon introducing randomization concept along with the two of the four primary parameters 'velocity' and 'gravity' in physics through swapping in terms of groups by using random numbers in the existing local search algorithm GELS in order to avoid local minima and thus can yield global minimum for STSP. To validate the proposed method numerous simulations were conducted to compare the quality of solutions with other existing algorithms like genetic algorithm (GA), simulated annealing (SA), hill climbing (HC), etc., using a range of STSP benchmark problems. According to the results of the simulations, the performance of RGES is found significantly enhanced and provided optimal solutions in almost all test problems of sizes up to 76. Also a comparative computational study of 11 chosen benchmark problems from TSPLIB library shows that this RGES algorithm is an efficient tool of solving STSP and this heuristic is competitive with other heuristics too. (C) 2007 Elsevier Inc. All rights reserved.