A TREE-SEARCH ALGORITHM FOR THE PARA-MEDIAN PROBLEM
A TREE-SEARCH ALGORITHM FOR THE PARA-MEDIAN PROBLEM
复制标题
DOI：
10.1016/0377-2217(82)90160-6
复制
发表时间：
1982-01-01
影响因子：
6.4
通讯作者：
BEASLEY, JE
中科院分区：
文献类型：
--
作者：
CHRISTOFIDES, N;BEASLEY, JE
在本文中，我们给出了p-中值问题的两个下界，即在网络上定位设施(中值)的问题。这些界限是基于问题的0-1公式的两个独立的拉格朗日松弛，并使用次梯度优化来最大化这些界限。基于这些下界和启发式确定的问题上界的惩罚测试被开发出来，并表明导致问题大小的大幅减少。描述了将下界和惩罚检验结合到树搜索过程中的过程，并给出了具有任意数目的中间点和多达200个顶点的问题的计算结果。并与Erlenkotter的基于对偶的算法进行了比较。
In this paper we present two lower bounds for thep-median problem, the problem of locatingpfacilities (medians) on a network. These bounds are based on two separate lagrangean relaxations of a zero-one formulation of the problem with subgradient optimisation being used to maximise these bounds. Penalty tests based on these lower bounds and a heuristically determined upper bound to the problem are developed and shown to result in a large reduction in problem size. The incorporation of the lower bounds and the penalty tests into a tree search procedure is described and computational results are given for problems with an arbitrary number of medians and having up to 200 vertices. A comparison is also made between these algorithms and the dual-based algorithm of Erlenkotter.