×

zbMATH — the first resource for mathematics

Comparison of genetic algorithms, random restart and two-opt switching for solving large location-allocation problems. (English) Zbl 0847.90091
Summary: This paper examines the application of a genetic algorithm used in conjunction with a local improvement procedure for solving the location-allocation problem, a traditional multifacility location problem. This problem is difficult to solve using traditional optimization techniques because of its multimodal, nonconvex nature. The alternate location-allocation (ALA) method has been shown to be an effective local improvement procedure for the location-allocation problem. Using the ALA method, an empirical analysis was done to determine the number and size of the local minima of the location-allocation problem to demonstrate the reduction of the size of the search space that can be achieved through the use of the ALA method as an evaluator. A genetic algorithm that evaluates a series of ALA solutions was developed and compared to two 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 quality of the solutions provided by the three procedures for several problems of varying size demonstrated that the genetic algorithm provides the best solutions. An examination of the number of ALA evaluations performed by each procedure showed that the genetic algorithm also found solutions to the larger size problems much quicker than either the random restart or the H4 procedures.

MSC:
90B85 Continuous location
68T05 Learning and adaptive systems in artificial intelligence
90C06 Large-scale problems in mathematical programming
Software:
Genocop
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cooper, L., The transportation-location problems, Ops res., 20, 94-108, (1972) · Zbl 0237.90036
[2] Love, R.F.; Juel, H., Properties and solution methods for large location-allocation problems, J. ops res. soc., 33, 443-452, (1982) · Zbl 0478.90017
[3] Love, R.F.; Morris, J.G., A computational procedure for the exact solution of location-allocation problems with rectangular distances, Naval res. logist. Q., 22, 441-453, (1975) · Zbl 0338.90057
[4] Daskin, M.S.; Jones, P.C., A new approach to solving applied location/allocation problems, Microcomputers civil engng, 8, 409-421, (1993)
[5] Cooper, L., Location-allocation problems, Ops res., 11, 331-343, (1963) · Zbl 0113.14201
[6] Love, R.F.; Morris, J.G.; Wesolowshy, G.O., Facilities location: models & methods, (1988), North-Holland New York · Zbl 0685.90036
[7] Davis, L., Genetic algorithms and simulated annealing, (1987), Pitman London · Zbl 0684.68013
[8] Michalewicz, Z., Genetic algorithms + data structures = evolution programs, (1992), Springer New York · Zbl 0763.68054
[9] Francis, R.L.; McGinnis, L.F.; White, J.A., Facility layout and location: an analytical approach, (1992), Prentice-Hall Englewood Cliffs, NJ
[10] Eilon, S.; Watson-Gandy, C.D.T.; Christotides, N., Distribution management: mathematical modeling and practical analysis, (1971), Nafner New York
[11] Davis, L., ()
[12] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley Reading, PA · Zbl 0721.68056
[13] Holland, J.H., Adaptation in natural and artificial systems, (1975), The University of Michigan Press Ann Arbor
[14] Joines, J.A.; Houck, C.R., On the use of non-stationary penalty functions to solve constrained optimization problems with genetic algorithms, (), 579-584, Orlando
[15] Law, A.M.; Kelton, W.D., Simulation modeling and analysis, (1991), McGraw Hill New York
[16] Welch, B.L., The generalization of Student’s problem when several different population variances are involved, Biometrika, 34, 28-35, (1947) · Zbl 0029.40802
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.