TY - JOUR
T1 - Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion
AU - Najy, Waleed
AU - Diabat, Ali
N1 - Funding Information:
This work was partially supported by the NYUAD Center for Interacting Urban Networks (CITIES), funded by Tamkeen under the NYUAD Research Institute Award CG001 and by the Swiss Re Institute under the Quantum CitiesTM initiative.
Funding Information:
This work was partially supported by the NYUAD Center for Interacting Urban Networks (CITIES), funded by Tamkeen under the NYUAD Research Institute Award CG001 and by the Swiss Re Institute under the Quantum Cities TM initiative.
Publisher Copyright:
© 2019 Elsevier Ltd
PY - 2020/3
Y1 - 2020/3
N2 - 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.
AB - 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.
KW - Benders decomposition
KW - Flow-dependent economies of scale
KW - Hub location
KW - Multiple allocation
KW - Network congestion
KW - Piecewise-linear modeling
UR - http://www.scopus.com/inward/record.url?scp=85077470082&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077470082&partnerID=8YFLogxK
U2 - 10.1016/j.trb.2019.12.003
DO - 10.1016/j.trb.2019.12.003
M3 - Article
AN - SCOPUS:85077470082
SN - 0191-2615
VL - 133
SP - 62
EP - 84
JO - Transportation Research, Series B: Methodological
JF - Transportation Research, Series B: Methodological
ER -