期刊
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
卷 59, 期 3, 页码 388-398出版社
PALGRAVE MACMILLAN LTD
DOI: 10.1057/palgrave.jors.2602356
关键词
integer programming; combinatorial analysis; VLSN search; partitioning problems; generalized assignment; local search
In this paper, we propose a general paradigm to design very large-scale neighbourhood search algorithms for generic partitioning-type problems. We identify neighbourhoods of exponential size, called matching neighbourhoods, comprised of the union of a class of exponential neighbourhoods. It is shown that these individual components of the matching neighbourhood can be searched in polynomial time, whereas searching the matching neighbourhood is NP-hard. Matching neighbourhood subsumes a well-known class of exponential neighbourhoods called cyclic-exchange neighbourhoods. Our VLSN algorithm is implemented for two special cases of the partitioning problem; the covering assignment problem and the single source transportation problem. Encouraging experimental results are also reported.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据