Column generation and local search for the profit-oriented hub-line location problem with elastic demands
针对盈利导向的枢纽线路选址问题，提出了列生成与局部搜索结合的数学启发式方法，在经典数据集和蒙特利尔真实数据上验证了其高效求解能力，并进行了敏感性分析。
Population growth and city sprawl have been driving increasing amounts of traffic congestion in multiple major cities worldwide. In this scenario, developing efficient public transportation networks becomes critical to ensure adequate mobility. Hub network location models address the problems of designing public transit networks to model — and to optimize — passenger mobility. More specifically, hub-line location problems (HLLP) play an essential role in the design of rapid transit corridors and subway lines. In this work we address the profit-oriented hub-line location problem (ED-HLLP) for which we introduce a column generation method to solve the linear relaxation of a mixed-integer model and matheuristic that combines column generation and local search. The proposed methodologies lead to the calculation of primal and dual bounds. We assess the performance of the proposed methods on some classic datasets from the HLLP literature. Furthermore, we conduct a study based on real-world data representing the metropolitan area of Montreal, Canada. Finally, we conduct a sensitivity analysis to assess the major attributes driving our results, both from an algorithmic point of view as well as from a planning perspective. The numerical results show that the proposed methods produce high-quality solutions, reduce computational times, and address the model’s combinatorial complexity more effectively than a commercial off-the-shelf solver, allowing for the solution of larger problems otherwise untractable for the latter. • We introduce a column generation (CG) method for the ED-HLLP. • CG allows for the computation of strong dual bounds in moderate computing times. • Introduce a hybrid matheuristic that combines CG with local search (CG+LS). • CG+LS is capable of producing strong primal bounds in short computing times. • We perform a sensitivity analysis and derive managerial insights.