Highlights We tackle the uncapacitated multiple allocation hub location problem with economies of scale and congestion. An efficient Benders decomposition algorithm is proposed to solve the resulting MIP. The proposed algorithm outperforms CPLEX and is able to solve much larger instances. Computational experiments are presented analyzing the differences between the congested and uncongested problem. Results show that switching from single allocation to multiple allocation yields large cost reductions.
Abstract This paper is the first to consider a novel and more realistic variant of the uncapacitated hub location problem where both flow-dependent economies of scale and congestion considerations are incorporated into the multiple-allocation version of the problem. Given an undirected graph with edge per-unit costs and flow requirements for a given set of source-destination pairs of nodes, the goal is to decide where to locate hub nodes and then to route flow through these hubs in a way that minimizes total cost. Transportation costs are influenced by two conflicting effects: consolidation discounts on hub-to-hub flow due to economies of scale, and congestion penalties due to excessive demand through hubs. The problem is formulated as a mixed-integer linear program by piecewise-linearizing non-linear cost elements. Since the resulting model is found to be difficult to solve directly using commercial solvers, a specialized Benders decomposition approach is devised to solve the problem. The proposed method is tested on two standard testbeds (the Civil Aeronautics Board and Australian Post datasets). While the commercial solver is unable to obtain any feasible solution for networks larger than 25 nodes, the proposed algorithm is shown to be able to obtain optimal solutions for networks as large as 70 nodes, and is able to obtain small-gap feasible solutions for networks with up to 100 nodes. Whenever both algorithms are able to solve instances to optimality, the Benders algorithm is able to do so in a fraction of the time needed by the commercial solver. The incorporation of congestion costs into the multiple-allocation topology as opposed to the single-allocation one is also found to lead to significant cost savings.
Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion
Transportation Research Part B: Methodological ; 133 ; 62-84
2019-12-09
23 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Benders Decomposition for Hub Location Problems with Economies of Scale
Online Contents | 2009
|Benders Decomposition for Hub Location Problems with Economies of Scale
British Library Online Contents | 2009
|