A dual based heuristic for the hub location and network design problem with single assignment constraint

In this paper, we address a network design problem including the decision of hub facility locations which is typically found in communication and transportation network design studies. Due to the administrative and the geographical restrictions, it is common to assume that each user should be assigned to only one hub facility. To construct such a network, three types of network costs should be considered: the fixed costs of establishing the hubs and the arcs in the network, and the variable costs associated with transversing the network. The complex problem is formulated as a mixed IP model embedding a multicommodity flow problem. Exploiting its special structure, a dual-based heuristic is then developed, which yields near-optimal design plans. The test results indicate that the heuristic is an effective way to solve this computationally complex problem.