To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
The Maximum Scatter Travelling Salesman Problem: A Hybrid Genetic Algorithm |
|
Author |
Zakir Hussain Ahmed, Asaad Shakir Hameed, Modhi Lafta Mutar, Mohammed F. Alrifaie, Mundher Mohammed Taresh |
| Citation |
Vol. 23 No. 6 pp. 193-201 |
|
Abstract |
In this paper, we consider the maximum scatter traveling salesman problem (MSTSP), a travelling salesman problem (TSP) variant. The problem aims to maximize the minimum length edge in a salesman’s tour that travels each city only once in a network. It is a very complicated NP-hard problem, and hence, exact solutions can be found for small sized problems only. For large-sized problems, heuristic algorithms must be applied, and genetic algorithms (GAs) are found to be very successfully to deal with such problems. So, this paper develops a hybrid GA (HGA) for solving the problem. Our proposed HGA uses sequential sampling algorithm along with 2-opt search for initial population generation, sequential constructive crossover, adaptive mutation, randomly selected one of three local search approaches, and the partially mapped crossover along with swap mutation for perturbation procedure to find better quality solution to the MSTSP. Finally, the suggested HGA is compared with a state-of-art algorithm by solving some TSPLIB symmetric instances of many sizes. Our computational experience reveals that the suggested HGA is better. Further, we provide solutions to some asymmetric TSPLIB instances of many sizes. |
|
Keywords |
Hybrid genetic algorithm; maximum scatter traveling salesman problem; sequential constructive crossover; adaptive mutation; local search; perturbation procedure. |
|
URL |
