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 Cities TM initiative.

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

VL - 133

SP - 62

EP - 84

JO - Transportation Research, Series B: Methodological

JF - Transportation Research, Series B: Methodological

SN - 0191-2615

ER -