Random-Keys Golden Ball Algorithm for Solving Traveling Salesman Problem
Fatima Sayoti, Mohammed Essaid Riffi · International Review on Modelling and Simulations (IREMOS) · 2015
This paper presents a new metaheuristic approach called RKGB algorithm for solving the combinatorial optimization problems. RKGB is based on soccer concepts; it uses the random keys representation to encode solutions. We propose an efficient adaptation of two algorithms for solving the traveling salesman problem (TSP): GB and RKGB; the booth algorithms have been never tested with TSP. To validate the proposed approach, numerous simulations were conducted on 36 instances of TSPLIB. The RKGB algorithm is compared with GB algorithm and other existing metaheuristics. According to the obtained results, the RKGB algorithm yields optimal solutions in less time. Some tests are conducted on TSPLIB instances for an efficient configuration of RKGB’s parameters. In this work we can deduce that our proposed approach is effective in solving NP-hard optimization problems.