An empirical comparison of tabu search, simulated annealing, and genetic algorithms for facilities location problems.

摘要

Operations managers are typically faced with the need to find good solutions to difficult problems. Such problems include job scheduling, assembly line balancing, process layout, project scheduling, and facilities locations. Although optimal solutions are preferable, the combinatorial nature of these problems means that in many cases problems found in practical applications cannot be solved to optimality within reasonable resources. Recently, much interest has been devoted to the development and application of three general heuristic algorithms for these problems: tabu search, simulated annealing, and genetic algorithms.;In this research study we conduct an empirical comparison of these three heuristic algorithms using three variants of the facilities location problem: capacitated (CFLP), multiple-periods (MP-FLP), and multiple-commodities (MC-FLP). The selection of three different problem structures allowed us to explore the behavior of the heuristics under different circumstances and constraints.;This research consisted of several stages including the proper selection of problem solutions representations, parameter searches, and benchmarking. The final stage was a statistical study to compare the performance of each heuristic along two dimensions: same computation time allowed and same amount of information allowed (i.e., number of solutions evaluated). We also compared the performance without any such restrictions.;When all heuristics are limited to the same amount of computation time, tabu search performs consistently well for all three problem types. However, for MP-FLP, the performance of simulated annealing shows no statistically significant difference from tabu search; and, for MC-FLP, the performance of the genetic algorithm shows no statistically significant difference form tabu search. When all heuristics are limited to the same number of solutions they may evaluate, each heuristic performs best for one type of problem. When no restrictions are place on the heuristics, tabu search performs best for CFLP and MC-FLP and simulated annealing performs best for MP-FLP.;Overall, tabu search tends to give the most robust results closely followed by simulated annealing. Genetic algorithms do not generally perform well for these types of problems, except when very few candidate solutions may be evaluated because of large computing requirements.