RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM
RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM
复制标题
DOI：
--
复制
发表时间：
2007-12
期刊：
影响因子：
--
通讯作者：
S. Umetani;M. Yagiura;柳浦 睦憲
中科院分区：
文献类型：
--
作者：
S. Umetani;M. Yagiura;柳浦 睦憲
集合覆盖问题（SCP）是一类典型的组合优化问题，有着广泛的实际应用。随着数学规划的不断发展，出现了许多启发式算法和精确分枝定界算法，它们可以求解大型SCP问题，如公交车、铁路和航空公司乘务员调度问题。我们调查的启发式算法的SCP侧重于数学规划技术的贡献，以启发式算法，并说明其性能通过实验分析。
The set covering problem (SCP) is one of representative combinatorial optimization problems, which has many practical applications. The continuous development of mathematical programming has derived a number of impressive heuristic algorithms as well as exact branch-and-bound algorithms, which can solve huge SCP instances of bus, railway and airline crew scheduling problems. We survey heuristic algorithms for SCP focusing mainly on contributions of mathematical programming techniques to heuristics, and illustrate their performance through experimental analysis.