Construction and improvement algorithms for dispersion problems
Construction and improvement algorithms for dispersion problems
复制标题
DOI：
10.1016/j.ejor.2014.09.058
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
R. Aringhieri;R. Cordone;A. Grosso
中科院分区：
文献类型：
--
作者：
R. Aringhieri;R. Cordone;A. Grosso
给定一个集合n，一个两两距离函数和一个整数，色散问题（DPs）需要从na子集合m的基数中提取，以优化m中元素之间距离的合适函数。不同的函数会产生一系列的组合优化问题。其中，最大和dpp和最大最小dpp在文献中受到了极大的关注。最近提出了其他问题（例如，最大最小差分和最小差分），目的是对公平要求的优化建模，而不是对更经典的效率要求建模。本文基于一些最先进的主题和数据挖掘方法的主要思想，针对这些新问题提出了一些建设性的步骤和禁忌搜索算法。特别是，我们研究了初始化、权属管理和多样化机制等关键特征在新背景下的扩展。计算实验表明，应用这些思想的算法在公开可用的基准测试上表现有效，但也存在一些关于文献中更多研究的dp的有趣差异。我们还提供了最优的结果和边界，为进一步的研究提供了有用的参考。
Given a setN, a pairwise distance functiondand an integer numberm, theDispersion Problems(DPs) require to extract fromNa subsetMof cardinalitym, so as to optimize a suitable function of the distances between the elements inM. Different functions give rise to a whole family of combinatorial optimization problems. In particular, themax-sum DPand themax-min DPhave received strong attention in the literature. Other problems (e.g., themax-minsum DPand themin-diffsum DP) have been recently proposed with the aim to model the optimization of equity requirements, as opposed to that of more classical efficiency requirements. Building on the main ideas which underly some state-of-the-art methods for themax-sum DPand themax-min DP, this work proposes some constructive procedures and a Tabu Search algorithm for the new problems. In particular, we investigate the extension to the new context of key features such as initialization, tenure management and diversification mechanisms. The computational experiments show that the algorithms applying these ideas perform effectively on the publicly available benchmarks, but also that there are some interesting differences with respect to theDPs more studied in the literature. As a result of this investigation, we also provide optimal results and bounds as a useful reference for further studies.