An improved MIP heuristic for the intermodal hub location problem
An improved MIP heuristic for the intermodal hub location problem
复制标题
DOI：
10.1016/j.omega.2015.04.016
复制
发表时间：
2015-12
影响因子：
6.9
通讯作者：
Yan He;Tao Wu;Canrong Zhang;Zhe Liang
中科院分区：
文献类型：
--
作者：
Yan He;Tao Wu;Canrong Zhang;Zhe Liang
由于多式联运枢纽选址问题具有广泛的实际应用价值，因此，优化方法得到了普遍的发展。这些方法包括精确方法（限于解决大规模问题）和算法（不保证解决方案的质量）。为了避免他们的弱点，但利用他们的优势，我们开发了一个改进的MIP启发式结合分支定界，拉格朗日松弛，线性规划松弛。在启发式算法中，我们使用分支定界和拉格朗日松弛方法生成初始可行解的种群，并使用线性规划松弛方法创建线性松弛解。我们结合联合收割机这些可行的线性松弛的解决方案，以固定的枢纽位置变量的一部分，从而创建一个限制枢纽位置子问题。然后，我们结合联合收割机的分支定界方法来解决这些限制的子问题，迭代提高解决方案的质量。我们详细讨论了应用该方法的联运枢纽选址问题。讨论之后进行了广泛的统计分析和计算测试，其中分析显示的启发式搜索和与其他方法的比较的解决方案的统计意义表明，所提出的方法是计算上听话，能够获得有竞争力的结果。
Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.