Approximate Muscle Guided Beam Search for Three-Index Assignment Problem
Approximate Muscle Guided Beam Search for Three-Index Assignment Problem
复制标题
DOI：
10.1007/978-3-319-11857-4_6
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
He Jiang;Shuwei Zhang;Zhilei Ren;Xiaochen Lai;Yong Piao
中科院分区：
文献类型：
--
作者：
He Jiang;Shuwei Zhang;Zhilei Ren;Xiaochen Lai;Yong Piao
作为一个著名的 NP 难问题，三索引分配问题（AP3）吸引了大量的研究工作来开发启发式方法。然而，现有的启发式方法要么获得竞争力较差的解决方案，要么消耗太多时间。在本文中，开发了一种名为近似肌肉引导波束搜索（AMBS）的新启发式算法，以实现解决方案质量和运行时间之间的良好权衡。通过将近似肌肉与波束搜索相结合，可以显着减小解空间大小，从而大大减少搜索解的时间。基准上的大量实验结果表明，新算法能够获得具有竞争力的质量解决方案，并且可以在大规模实例上使用。本文的工作不仅提出了一种新的高效启发式方法，而且还提供了一种有前途的提高波束搜索效率的方法。
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 consume too much time. In this paper, a new heuristic named Approximate Muscle guided Beam Search (AMBS) is developed to achieve a good trade-off between solution quality and running time. By combining the approximate muscle with beam search, the solution space size can be significantly decreased, thus the time for searching the solution can be sharply reduced. Extensive experimental results on the benchmark indicate that the new algorithm is able to obtain solutions with competitive quality and it can be employed on instances with large-scale. Work of this paper not only proposes a new efficient heuristic, but also provides a promising method to improve the efficiency of beam search.