点击次数：

论文类型：期刊论文

发表时间：2014-01-01

发表刊物：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录刊物：EI、Scopus

卷号：8794

页面范围：44-52

ISSN号：03029743

摘要：As a well-known NP-hard problem, the Three-Index Assignment Problem (AP3) has attracted lots of research efforts for developing heuristics.However, existing heuristics either obtain less competitive solutions or consumetoo much time. In this paper, a new heuristic named Approximate Muscleguided Beam Search (AMBS) is developed to achieve a good trade-off betweensolution quality and running time. By combining the approximate muscle withbeam search, the solution space size can be significantly decreased, thus thetime for searching the solution can be sharply reduced. Extensive experimentalresults on the benchmark indicate that the new algorithm is able to obtain solutionswith competitive quality and it can be employed on instances with largescale.Work of this paper not only proposes a new efficient heuristic, but alsoprovides a promising method to improve the efficiency of beam search. ? Springer International Publishing Switzerland 2014.