摘要
集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小。集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域。对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法。本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法。算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列。用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的。
The set/covering problem is a fundamental combinatorial problem in operations research. It is usually described as the problem of covering the rows of this m-row, n-column, 0-1 matrix （au）rex, by a subset of the columns at minimal cost. This problem has many practice applications such as airline crew scheduling, circuit design, vehicle routing, etc. For solving this problem, many algorithms such as genetic algorithm, simulated annealing, ant colony algorithm and artificial neural network algorithm have been proposed. Based on the greedy algorithm, a heuristic algorithm for set covering problem is proposed according to wisdom and experience of human being in this paper. The main idea of the algorithm is that remove some columns from a solution randomly and add some new columns by greedy strategy. 45 instances provided by Beasley are tested by the produced algorithm, the average gap between the best solution and the optimal solution is 0. 44% and 33 instances of them are achieved optimal solutions. Experimental results demonstrate that the algorithm proposed in this paper is efficient for solving the set covering problem.
出处
《计算机科学》
CSCD
北大核心
2007年第4期133-136,共4页
Computer Science
基金
国家自然科学基金资助项目(10471051和973项目2004CB318000)
关键词
集合覆盖
启发式算法
贪心策略
随机跳坑
Set covering problem, Heuristic algorithm, Greedy strategy, Random off-trap
