Lower bounds for the hub location problem
Lower bounds for the hub location problem
复制标题
DOI：
10.1287/mnsc.41.4.713
复制
发表时间：
1995-04
影响因子：
5.4
通讯作者：
M. O’Kelly;D. Skorin-Kapov;J. Skorin-Kapov
中科院分区：
文献类型：
--
作者：
M. O’Kelly;D. Skorin-Kapov;J. Skorin-Kapov
我们给出了中心选址问题HLP的一个新的下界，其中距离满足三角不等式。我们的下界是基于问题的线性化及其修改，通过结合已知启发式解的知识而获得。为文献中的一些标准数据集计算了下限，范围在10到25个节点之间，具有2个、3个和4个中枢，并计算了参数α的不同值，该参数表示中枢之间的流量折扣。在所有情况下，使用已知的启发式解来导出下界的新方法减小了上界和下界之间的差异。这一差异以高于最佳下限的百分比来衡量最知名的启发式解决方案的质量。作为这项研究的结果，对于较小的问题，具有10个和15个节点的所有实例的平均差异降低到3.3%。对于较大的集合20和25个节点，平均差异减小到5.9%。
We present a new lower bound for the Hub Location Problem HLP where distances satisfy the triangle inequality. Our lower bound is based on a linearization of the problem and its modification obtained by incorporating the knowledge of a known heuristic solution. A lower bound was computed for some standard data sets from the literature ranging between 10 and 25 nodes, with 2, 3, and 4 hubs, and for different values for the parameter α, representing the discount for the flow between hubs. The novel approach of using a known heuristic solution to derive a lower bound in all cases reduced the difference between the upper and lower bound. This difference measures the quality of the best known heuristic solution in percentages above the best lower bound. As a result of this research, for smaller problems all instances with 10 and 15 nodes the average difference is reduced to 3.3%. For larger sets 20 and 25 nodes the average difference is reduced to 5.9%.