Genetic algorithms‐based solution approach to combinatorial optimisation problems

This paper presents various methods and algorithms used in the solution of combinatorial optimisation problems. A definition of a combinatorial optimisation problem is first given. The definition is followed by a discussion on the depth first branch‐and‐bound algorithm and the local search algorithm; two approaches used for solving these kinds of problems. An introduction to Genetic Algorithms (GAs) coupled with an explanation of their role in solving combinatorial optimisation problems such as the travelling salesman problem is then presented. The discussion on genetic algorithms focuses on the advantages and disadvantages of using this technique as a tool or solving combinatorial optimisation problems. A sample instance of the Travelling Salesman Problem (TSP) is then solved using a GA. Finally, some conclusions are presented to emphasise the implications, benefits and drawbacks of using genetic algorithms in the solution of various combinatorial optimisation problems.