Enumeration and search procedures for a hub location problem with economies of scale

Within a communications or transportation network, in which a number of locations exchange material or information, hubs can be used as intermediate switching points. In this way, traffic can be consolidated on inter-hub links and, thus, achieve economies of scale in transport costs. Recently, O'Kelly and Brian in 1998 proposed a model (termed the FLOWLOC model) that treats these economies of scale by means of piecewise-linear concave cost functions on the interhub arcs. We show that, for a fixed set of hubs, the FLOWLOC model can be solved using the classic Uncapacitated Facility Location Problem. This observation then motivates an optimal enumeration procedure for the FLOWLOC model, as well as some search heuristics that are based upon tabu search and greedy random adaptive search procedures. These search procedures would be especially applicable for large-sized problems. Some computational experience is described.