A Lagrangian heuristic and GRASP for the hub-and-spoke network system with economies-of-scale and congestion. (May 2019)

• Record Type: Journal Article
• Authors: Alkaabneh, Faisal; Diabat, Ali; Elhedhli, Samir
• Is Part Of: Transportation research. Volume 102(2019)
• Page Start: 249
• Page End: 273
• Publication Date: 2019-05
• Subjects: Hub-and-Spoke design network -- Congestion -- Economies-of-scale -- Mixed Integer Nonlinear programming -- Lagrangian relaxation -- GRASP; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2018.12.011
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: We consider a hub-and-spoke network design problem with inter-hub economies-of-scale and hub congestion. We explicitly model the economies-of-scale as a concave piece-wise linear function and congestion as a convex function. We develop a Lagrangian approach is proposed to obtain tight upper and lower bounds. We develop a Greedy Randomized Adaptive Search Procedure (GRASP) for solving large instances of the problem. Abstract: We consider a hub-and-spoke network design problem with inter-hub economies-of-scale and hub congestion. We explicitly model the economies-of-scale as a concave piece-wise linear function and congestion as a convex function. The problem is modeled as a nonlinear mixed integer program that is difficult to solve directly since the objective function has both convex and concave nonlinear terms and hence finding an optimal solution may not be easy. A Lagrangian approach is proposed to obtain tight upper and lower bounds. The Lagrangian decomposition exploits the structure of the problem and decomposes it to convex and concave subproblems. Furthermore, we add some valid inequalities to accelerate the convergence rate of the Lagrangian heuristic. To tackle large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is developed. Both the Lagrangian heuristic and GRASP provide high-quality solutions within reasonable computational time. The optimal designs of hub-and-spoke networks with nonlinear inter-hub economies-of-scale and congestion at hub locations are analyzed in comparison with other models in the literature to demonstrate the significant impact of modeling nonlinearity in economies-of-scale and congestion simultaneously rather than independently.