A lagrange relaxation method for the network design problem considering facility location

The network design problem, which attempts to simultaneously take into account facility location and network topology, has a number of applications in transportation network design, distribution systems, telecommunication network planning, and other areas. In this paper, we investigate a new model that simultaneously optimizes facility locations for distribution centers and concentrators, network topology for line-haul trucks and fiber-optic communication lines, and routes of commodity flow for freight and communication data. Our model consists of uncapacitated facility location, uncapaci-tated arc design, general network design, an unlimited number of freight transshipment at facilities, and multi-commodity flow routing that has a large number of origin-destination pairs. It has been noted that this model is not suitable for solving problems that exist in the real world with current OR software on the market. We present a new formulation of this problem that minimizes the sum of flow costs, arc design costs, and facility location costs, and a new Lagrange relaxation problem with relaxed flow conservation constraints and some forcing constraints. We present an exact solution method for this Lagrange relaxation problem, and a subgradient method for Lagrange multipliers. In addition, we present an approximate solution method for obtaining good upper bound using solutions of a Lagrange relaxation problem, which is called Lagrange heuristics. Numerical examples up to 100 nodes are given to show the effectiveness of our formulation and solution methods for lower and upper bound.