Decomposition strategies for large-scale continuous location–allocation problems

The continuous location–allocation problem requires finding sites for m new facilities in the plane in order to serve n users such that the total transportation costs are minimized. Several heuristics have been developed to solve this well-studied global optimization problem. However, little work has been done using decomposition techniques. In this paper, we examine a few new ways to decompose the location–allocation problem. These strategies are then embedded in a variable neighbourhood decomposition search heuristic and tested on large instances of this problem.