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

Weibin Dai, Sebastian Wandelt, Jun Zhang, Xiaoqian Sun*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

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^{4})$ 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.

Original languageEnglish
Pages (from-to)8451-8466
Number of pages16
JournalIEEE Transactions on Intelligent Transportation Systems
Volume23
Issue number7
DOIs
Publication statusPublished - 1 Jul 2022
Externally publishedYes

Keywords

  • Hub location problem
  • air
  • heuristic
  • rail
  • uncertainty

Fingerprint

Dive into the research topics of 'Capacitated Air/Rail Hub Location Problem With Uncertainty: A Model, Efficient Solution Algorithm, and Case Study'. Together they form a unique fingerprint.

Cite this