African Buffalo Optimization and the Randomized Insertion Algorithm for the Asymmetric Travelling Salesman’s Problems - Odili, Julius Beneoluchi; M. N. M., Kahar; Noraziah, Ahmad; Odili, Esther Abiodun (JATIT, 2016)
This paper presents a comparative study of the African Buffalo Optimization algorithm and the Randomized Insertion Algorithm to solving the asymmetric Travelling Salesman’s Problem with the overall objective of determining a better method to solving the asymmetric Travelling Salesman’s Problem instances. Our interest in the asymmetric Travelling Salesman’s Problem (ATSP) is borne out of the fact that most practical daily-life problems are asymmetric rather than symmetric. The choice of the Random Insertion Algorithm as a comparative algorithm was informed by our desire to investigate the general belief among the scientific community that Heuristics being mostly problem-dependent algorithms are more efficient that metaheuristics that are usually general-purpose algorithms. Moreover, both the metaheuristic, the African Buffalo Optimization and the Heuristic, Randomized Insertion Algorithms hold some of the best results in literature in solving the ATSP. Similarly, both methods employ different search techniques in attempting solutions to the ATSP: while the African Buffalo Optimization uses the modified Karp-Steele technique, the Randomized Insertion employs random insertion mechanism. After investigating all the 19 benchmark ATSP datasets available in TSPLIB, it was discovered that the Randomized Insertion Algorithm achieves slightly better result to the problems but the African Buffalo Optimization is much faster