Single Allocation Hub Location with Heterogeneous Economies of Scale

• 成果类型: Article
• 署名作者: Rostami, Borzou; Chitsaz, Masoud; Arslan, Okan; Laporte, Gilbert; Lodi, Andrea
• 署名单位: Wilfrid Laurier University; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Universite de Montreal; HEC Montreal; University of Bath; Cornell University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2185
• 发表日期: 2022
• 页码: 766-785
• 关键词: Benders decomposition; Network design; spoke network; models; algorithms

摘要

We study the single allocation hub location problem with heterogeneous economies of scale (SAHLP-h). The SAHLP-h is a generalization of the classical single allocation hub location problem (SAHLP), in which the hub-hub connection costs are piecewise linear functions of the amounts of flow. We model the problem as an integer nonlinear program, which we then reformulate as a mixed integer linear program (MILP) and as a mixed integer quadratically constrained program (MIQCP). We exploit the special structures of these models to develop Benders-type decomposition methods with integer subproblems. We use an integer L-shaped decomposition to solve the MILP formulation. For the MIQCP, we dualize a set of complicating constraints to generate a Lagrangian function, which offers us a subproblem decomposition and a tight lower bound. We develop linear dual functions to underestimate the integer subproblem, which helps us obtain optimality cuts with a convergence guarantee by solving a linear program. Moreover, we develop a specialized polynomial-time algorithm to generate enhanced cuts. To evaluate the efficiency of our models and solution approaches, we perform extensive computational experiments on both uncapacitated and capacitated SAHLP-h instances derived from the classical Australian Post data set. The results confirm the efficacy of our solution methods in solving large-scale instances.