Optimization Online


Single Allocation Hub Location with Heterogeneous Economies of Scale

Borzou Rostami(brostami***at***wlu.ca)
Masoud Chitsaz(masoud.chitsaz***at***hec.ca)
Okan Arslan(okan.arslan***at***hec.ca)
Gilbert Laporte(gilbert.laporte***at***cirrelt.ca)
Andrea Lodi(andrea.lodi***at***polymtl.ca)

Abstract: 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 non-linear program, which we then reformulate as a mixed integer linear program (MILP) and also 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 dataset. The results confirm the efficacy of our solution methods in solving large-scale instances.

Keywords: Single allocation, hub location, economies of scale, quadratic program, Benders decomposition, Lagrangian relaxation

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 10/17/2019
Entry Accepted: 10/17/2019
Entry Last Modified: 10/17/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society