Solving Single Allocation Hub Location Problems on Euclidean Data.

If shipments have to be transported between many sources and sinks, direct connections from each source to each sink are often too expensive. Instead, a small number of nodes are upgraded to hubs that serve as transshipment points. All sources and sinks are connected to these hubs, so that only a few, strongly consolidated transport relations exist. While hubs and detours lead to additional costs, the savings from bundling shipments—i.e., economies of scale—usually outweigh these costs. Typical applications for hub networks are in cargo, air freight, and postal and parcel transport services. In this paper, we consider three classical and two recent formulations of single allocation hub location problems—i.e., hub location problems in which every source and sink is connected to exactly one hub. Solving larger instances of these problems to optimality is difficult because the inherent quadratic structure of the problem has to be linearized: This leads to a sharp rise in the number of variables. Our new approach relies on the fact that many instances—including the Civil Aeronautics Board and Australian Post data sets—have a Euclidean structure: The distances between the possible hub locations are Euclidean. This enables us to construct a new linearization together with a row generation procedure that solves instances of up to 200 nodes to optimality. For problems like the uncapacitated single allocation p-hub median problem and the uncapacitated single allocation hub location problem, we present the first optimal results for instances of this size. [ABSTRACT FROM AUTHOR]

Copyright of Transportation Science is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)