SOLUTION OF THE TRAVELLING SALESMAN PROBLEM AND THE QUADRATIC ASSIGNMENT PROBLEM USING NOVEL HEURISTICS

Abstract

Combinatorial optimization is a popular sub-field of optimization. It involves finding the best solution to a problem from a finite and discrete set of choices. These problems are challenging as they aim to address complex real-world problems and improve quality of life. This thesis focuses on solving combinatorial optimization problems, namely the Travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). These problems are among the extensively studied and well-known optimization problems in the field of operations research. Also, these problems are challenging from the theoretical point of view but play an important role in industrial issues. They possess many applications in logistics, scheduling, transportation, and facility location planning. TSP is one of the most appealed and extensively studied problem, which generate a great social, scientific and industrial interest. The TSP seeks to find the shortest possible route that visits a set of cities and returns to the starting point. It finds application in various domains, including logistics, planning, and manufacturing, among others. The QAP, on the other hand, aims to determine the optimal assignment of facilities to locations, considering the distances between facilities and their interaction costs. QAP and its variants are studied in scheduling, layout design, campus planning problem, typewriters, keyboard design and data allocation. Both problems are known to be NP-hard, therefore, heuristics that can find good quality solutions in reasonable computational time are highly desirable. The Symmetric Travelling Salesman Problem (STSP), Asymmetric Travelling Salesman Problem (ATSP) and Quadratic Assignment Problem (QAP) are addressed in this thesis, and to solve them, new heuristics are proposed. Two discrete variants of the grey wolf optimizer and one discrete version of the salp swarm algorithm have been developed to solve STSP. To develop these variants, transformation operators and the 2-opt algorithm are used. The performance of the proposed variants is evaluated across a comprehensive set of STSP instances, and the results are compared with existing state-of-the-art algorithms. The proposed variants have shown competitive performance for STSP instances. Also, discrete variants of particle swarm optimization, grey wolf optimizer, whale optimization algorithm, sine cosine algorithm, and artificial humming bird algorithm have been developed for the ATSP. Among these algorithms, the artificial humming bird algorithm has demonstrated superior performance when applied to ATSP instances, outperforming the other algorithms. To address the Quadratic Assignment Problem (QAP), a hybrid discrete variant of the grey wolf optimizer (GWO) is developed by incorporating the tabu search algorithm. In this proposed variant, the continuous values generated by the classical GWO are transformed into discrete values using the largest real value mapping technique. Subsequently, the tabu search algorithm is applied to enhance the solution further. The performance of the proposed variant is evaluated through computational experiments over standard QAP benchmark instances and compared with other well-known algorithms from the literature. The analysis of obtained numerical results demonstrated that the proposed hybrid discrete variant has merit in solving QAP. Overall, the experimental results of the proposed heuristics demonstrate their highly effective nature in finding high-quality solutions for TSP and QAP problems. These results demonstrate the potential of heuristics as a powerful tool for solving combinatorial optimization problems, especially when exact algorithms become intractable for large instances. These approaches have the potential to be extended and applied to address a range of other combinatorial optimization problems. For instance, they can be used to solve problems like vehicle routing problem, facility location problem, and flowshop scheduling. In summary, this thesis makes a significant contribution to the field of combinatorial optimization by proposing efficient heuristics for solving two challenging problems, the TSP and QAP. The proposed algorithms are highly effective and can be applied to a wide range of practical problems in various industries.