Optimization Online


Hub Network Design Problem with Capacity, Congestion and Stochastic Demand Considerations

Vedat Bayram(vedat.bayram***at***tedu.edu.tr)
Barış Yıldız(byildiz***at***ku.edu.tr)
M. Saleh Farham(Saleh.Farham***at***cirrelt.ca)

Abstract: We introduce the hub network design problem with congestion, capacity, and stochastic demand considerations (HNDC), which generalizes the classical hub location problem in several directions. In particular, we extend state-of-the-art by integrating capacity acquisition decision and congestion cost effect into the problem and allowing dynamic routing for origin-destination pairs. Connecting strategic and operational level decisions, HNDC jointly decides hub locations and capacity acquisitions by taking the expected routing and congestion costs into account. A path-based mixed-integer second-order cone programming (SOCP) formulation of the HNDC is proposed. We exploit SOCP duality results and propose an exact algorithm based on Benders decomposition and column generation to solve this challenging problem. We use a specific characterization of the capacity-feasible solutions to speed up the solution procedure and develop an efficient branch-and-cut algorithm to solve the master problem. We conduct extensive computational experiments to test the performance of the proposed approach and to derive managerial insights based on realistic problem instances adapted from the literature. In particular, we found that including hub congestion costs, accounting for the uncertainty in demand, and whether the underlying network is complete or incomplete have a significant impact on hub network design and the resulting performance of the system.

Keywords: hub location problem; hub congestion; capacity building; multiple allocation; second order cone programming; Benders decomposition; column generation; branch-and-cut

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/19/2021
Entry Accepted: 12/20/2021
Entry Last Modified: 12/19/2021

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