A new formulation and branch-and-cut method for single-allocation hub location problems. (July 2023)

• Record Type: Journal Article
• Authors: Espejo, Inmaculada; Marín, Alfredo; Muñoz-Ocaña, Juan M.; Rodríguez-Chía, Antonio M.
• Is Part Of: Computers & operations research. Volume 155(2023)
• Publication Date: 2023-07
• Subjects: Hub location -- Single allocation -- Discrete optimization -- Branch-and-cut; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106241
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: A new compact formulation for uncapacitated single-allocation hub location problems with fewer variables than the previous Integer Linear Programming formulations in the literature is introduced. Our formulation works even with costs not based on distances and not satisfying triangle inequality. Moreover, costs can be given in aggregated or disaggregated way. Different families of valid inequalities that strengthen the formulation are developed and a branch-and-cut algorithm based on a relaxed version of the formulation is designed, whose restrictions are inserted in a cut generation procedure together with two sets of valid inequalities. The performance of the proposed methodology is tested on well-known hub location data sets and compared to the most recent and efficient exact algorithms for single-allocation hub location problems. Extensive computational results prove the efficiency of our methodology, that solves large-scale instances in very competitive times. Highlights: A new compact formulation for USAHLP is introduced. Costs do not require to be based on distances or satisfying triangle inequality. Costs can be given in aggregated or disaggregated way. Families of valid inequalities that strengthen the formulation are developed. A branch-and-cut algorithm is designed.