Single allocation hub location problems with congestion: Mixed-integer second-order cone programming and Benders decomposition

Qing-Mi Hu and Shaolong Hu

Transportation Research Part E: Logistics and Transportation Review, 2025, vol. 201, issue C

Abstract: This paper presents a capacitated single allocation hub location problem with consideration of congestion, in which a mixed-integer nonlinear programming model is established due to the nonlinearity of the congestion cost. A novel Mixed-Integer Linear Programming (MILP) reformulation method utilizing the binary representation of non-negative integers and a strong Mixed-Integer Second-Order Cone Programming (MISOCP) reformulation method resting on the perspective cut are developed to deal with the resulting nonlinear model. Moreover, to further solve larger problems, an accelerated Benders Decomposition (BD) algorithm employing multi-cuts generation and Pareto-optimal cut strategies is devised, in which the master problem is formulated as a relaxed MISOCP so as to effectively utilize the strength of the perspective cut. Meanwhile, an efficient optimization algorithm is developed to generate Pareto-optimal cuts, which significantly saves the time consumption in solving the related dual sub-problems. Through extensive numerical analysis using Civil Aeronautics Board (CAB) and Australian Post (AP) data, it is demonstrated that the computational performance of the developed MILP and MISOCP reformulation methods is far superior to that of the existing classical reformulation methods such as a MILP reformulation method utilizing the McCormick envelop and a MISOCP reformulation method utilizing the feature of binary variables. The proposed BD algorithm can yield the optimal solution for instances with up to 75 nodes within the acceptable computational time. Unexpectedly, under the setting of loose hub capacities, a low congestion level can be also achieved by locating fewer hubs, rather than more hubs.

Keywords: Hub location; Congestion; Mixed-integer nonlinear programming; Linearization; Second-order cone programming; Benders decomposition (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554525003266
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:201:y:2025:i:c:s1366554525003266

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2025.104285

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().