Improving Iterated Local Search Solution for the Linear Ordering Problem with Cumulative Costs (LOPCC)
Improving Iterated Local Search Solution for the Linear Ordering Problem with Cumulative Costs (LOPCC)
复制标题
改进具有累积成本的线性排序问题的迭代局部搜索解决方案 (LOPCC)
DOI：
10.1007/978-3-642-15390-7_19
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Héctor José Puga Soberanes
中科院分区：
文献类型：
--
作者：
David Terán Villanueva;H. J. F. Huacuja;A. Duarte;Rodolfo Pazos;Juan Martín Carpio Valadez;Héctor José Puga Soberanes
本文研究了带累积费用的线性订货问题。最著名的算法解决这个问题是禁忌搜索Duarte提出的。在这项工作中，进行了实验研究，以评估这些阶段之间的集约化和多样化的平衡。结果表明，启发式构造阶段对禁忌搜索算法的性能有很大的影响，这往往会减少与大的实例。然后，评估的启发式结构的多样性潜力，两个迭代局部搜索算法的发展。实验结果表明，启发式结构的分布提出的多样化机制是更适合解决大型实例。启发式构造方法的多样化潜力得到了证实，因为使用这种方法，我们找到了26个最佳已知解，而不是禁忌搜索算法找到的。
In this paper the linear ordering problem with cumulative costs is approached. The best known algorithm solution for the problem is the tabu search proposed by Duarte. In this work an experimental study was performed to evaluate the intensification and diversification balance between these phases. The results show that the heuristic construction phase has a major impact on the tabu search algorithm performance, which tends to diminish with large instances. Then to evaluate the diversification potential of the heuristic construction, two iterated local search algorithms were developed. Experimental evidence shows that the distribution of the heuristic construction proposed as diversification mechanism is more adequate for solving large instances. The diversification potential of the heuristic construction method was confirmed, because with this approach we found 26 best known solutions, not found by the tabu search algorithm.