Facility location-network design problems seek to simultaneously determine the locations of fa- cilities and the design of the network connecting the facilities so as to best serve a set of clients accessing the facilities via the network. Here we study a dynamic (multi-period) version of the problem, subject to a budget constraint limiting the investment in new facilities and network links in each period. We consider an uncapacitated setting, in which the objective is to minimize the combined travel cost for clients and operating costs of facilities and network links. We present a mixed-integer linear programming (MIP) model generalizing related models in the literature, derive some useful properties of solutions, and show how the model can be strengthened. Three heuristics based on sequential solution of MIPs, and an efficient hybrid heuristic based on variable neighbor- hood search (VNS), are presented. The models and algorithms are compared computationally on randomly generated instances.
Citation
Report C-OPT 2012/02, The University of Newcastle, Callaghan, NSW, 2308, Australia, 2012