Authors: Ali K. Kamrani, Ricardo Gonzalez
Addresses: Department of Industrial Engineering, University of Houston, Houston, TX 77204, USA. ' Industrial Engineering and Manufacturing Systems Engineering, The University of Michigan, Dearborn, MI 48128-1491, USA
Abstract: 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.
Keywords: data mining; genetic algorithms; GAs; travelling salesman problem; TSP; combinatorial optimisation; metaheuristics; local optimum; branch and bound.
International Journal of Knowledge Management Studies, 2008 Vol.2 No.4, pp.499 - 518
Published online: 29 Jul 2008 *Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article