Linkage in warehouse location problems: The numbering effect and its influence on evolutionary algorithms
Jörn Grahl, Tobias Weiblen, Stefan Minner · Alexandria (UniSG) (University of St.Gallen) · 2007
We solve the uncapacitated warehouse location problem with a simple genetic algorithm and find a significant influence of the numbering of warehouses on the performance of the genetic algorithm. The effect is explained by linking a decom- position result for the problem to genetic algorithm theory, and its relevance is un- derlined by means of an empirical study based on over 600 widely used benchmark test instances. We propose to solve warehouse location problems with estimation of distribution algorithms. Estimation of distribution algorithms perform indepen- dent of the numbering of warehouses and are more effective. The number of fitness evaluations required to solve warehouse location problems is found to grow with a low-order polynomial depending on the number of warehouses. The results are rel- evant to optimization practitioners who design evolutionary algorithms for location problems.