Hits:

Indexed by:期刊论文

Date of Publication:2014-01-01

Journal:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Included Journals:EI、Scopus

Volume:8794

Page Number:44-52

ISSN No.:03029743

Abstract: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.