COMPARISON OF GENETIC ALGORITHMS, RANDOM RESTART AND 2-OPT SWITCHING FOR SOLVING LARGE LOCATION-ALLOCATION PROBLEMS

This paper examines the application of a genetic algorithm used in con junction with a local improvement procedure for solving the location-a llocation problem, a traditional multifacility location problem. This problem is difficult to solve using traditional optimization technique s because of its multimodal, nonconvex nature. The alternate location- allocation (ALA) method has been shown to be an effective local improv ement procedure for the location-allocation problem. Using the ALA met hod, an empirical analysis was done to determine the number and size o f the local minima of the location-allocation problem to demonstrate t he reduction of the size of the search space that can be achieved thro ugh the use of the ALA method as an evaluator. A genetic algorithm tha t evaluates a series of ALA solutions was developed and compared to tw o traditional heuristic procedures for the problem: random restart and H4, a two-opt procedure. Like the genetic algorithm, both procedures evaluate a series of ALA solutions. A statistical analysis of the qual ity of the solutions provided by the three procedures for several prob lems of varying size demonstrated that the genetic algorithm provides the best solutions. An examination of the number of ALA evaluations pe rformed by each procedure showed that the genetic algorithm also found solutions to the larger size problems much quicker than either the ra ndom restart or the H4 procedures. Copyright (C) 1996 Elsevier Science Ltd