Recently, integrated models of facility location and network design (FLND) problems have attracted many research attentions. This class of NP-hard problems, as the name suggests, simultaneously optimizes facility locations and the design of the underlying network. They have been a central and useful planning tool in many contexts, e.g., regional planning, distribution, energy management, etc. However, FLND problems are extremely hard to solve and computational difficulties has limited their way into the practice. In this paper, we propose three variants of a simple and efficient meta-heuristic based on variable neighborhood search method to solve the capacitated FLND problem effectively. We particularly improve the neighborhood exploration mechanism by taking advantage of exact methods within the solution framework. Computational experiments on a wide-range of test instances with up to 100 nodes and 600 links show that our approaches consistently return high quality solutions in short CPU times in comparison with the state-of-the-art of commercial solvers.
