This article presents a mixed-integer model to optimize the location of facilities and the underlying transportation network at the same time to minimize the total transportation and operating costs. In this problem, it is assumed that for connecting two nodes, there are several types of links in which their capacity, transportation and construction costs are different. The developed model has various applications in telecommunication, emergency, regional planning, pipeline network, energy management, distribution, to just name a few. To solve the model effectively, this paper also proposes a fix-and-optimize heuristic based on the evolutionary fire-fly algorithm. Finally, to validate the model and evaluate the algorithm’s performance, a series of test instances with up to 100 nodes and 600 candidate links with three different levels of quality are reported
