The Traveling Salesman and the Quadratic Assignment Problems: Integration, Modeling and Genetic Algorithm

摘要

The traveling salesman problem and the quadratic assignment problem are the two of the most commonly studied optimization problems in Operations Research because of their wide applicability. Due to their NP-hard nature, the individual problems are already complex and difficult to solve. In this paper, the two hard problems are integrated together first, that is called the integrated problem of which the complexity is absolutely much higher than that of the individual ones. Not only a complete mathematical model which integrates both the traveling salesman and the quadratic assignment problems together is built, but also a genetic algorithm hybridized with several improved heuristics is developed to tackle the problem.