Transportation-location problem with unknown number of facilities

The traditional transportation-location problem seeks to determine the location of m new capacitated facilities in continuous space and the level of interaction between these new facilities and existing facilities to minimize the total fixed and variable costs. This paper studies a variant of the transportation-location problem where the number of new facilities is also a decision variable. The problem has practical applications for designing large distribution networks. Several non-linear mixed integer formulations are presented in order to understand the intrinsic complexity of the problem. Given that the problem is NP-hard, a decomposition heuristic (DH) and a simulated annealing-based heuristic (SA) are developed based on the mathematical structure of the problem and compared via experimentation. It is found that both heuristics find the same solution for 40 internally generated problems. Three new benchmark problems are presented and an upper bound is provided.