Capacitated Air/Rail Hub Location Problem With Uncertainty: A Model, Efficient Solution Algorithm, and Case Study

Well-designed multi-modal transportation networks are crucial for our connected world. For instance, the excessive construction of railway tracks in China, at speeds up to 350 km/h, makes it necessary to consider the interaction of rail with air transportation for network design. In this study, we propose a model for an air/rail multi-modal, multiple allocation hub location problem with uncertainty on travel demands. Our model is unique in that it integrates features from the existing literature on multi-modal hub location problem (including hub-level capacities, link capacities, direct links, travel cost and time, transit costs and uncertainty), which have not been considered simultaneously, given its high computational complexity. We formulate this model with O(n⁴) variables and show that the implementation of a Benders decomposition algorithm is inherently hard, because of the cubic number of variables in the master problem. Furthermore, we derive an iterative network design algorithm and additional improvement strategies: MMHUBBI which resolves a restricted problem by the solver CPLEX and MMHUBBI-DIRECT which re-designs the transportation network by a heuristic. Our evaluation on real-world dataset for Chinese domestic transportation shows that MMHUBBI provides a significant speed-up on all instances, compared to using CPLEX, while obtaining near-optimal solutions. MMHUBBI-DIRECT further reduces the runtime/memory usage but provides solutions with worse quality. We believe that our study contributes towards the design of more realistic multi-modal hub location problems.