This paper presents a genetic algorithm to solve the asymmetric traveling salesman problem. The genetic algorithm proposed in this study extends search space by purposefully generating andinclud ing infeasible solutions in the population. Insteadof trying to maintain feasibility with crossover operations, it searches through both feasible andinfeasible regions for goodquality solutions. It is also shown in the article that the size of the infeasible region de4ned by solutions with subtours dominates that of a feasible region in the asymmetric traveling salesman problem. A comparative computational study using benchmark problems shows that the proposedgenetic algorithm is a viable option for hardasymmetric traveling salesman problems.
['In Chan Choi', 'Seong In Kim', 'Hak Soo Kim']
A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem