计算机应用研究

作者：贺杰栋,陆芷,

单位：上海理工大学管理学院,上海200093；

关键词：多样性选址问题,选址,启发式算法,禁忌搜索,强化机制,

基金：国家自然科学基金资助青年项目(72101149)；上海市浦江人才计划资助项目(22PJC080)；；

考虑容量和成本的最大最小多样性选址问题 （GDP） 是从一个无向完全图中选出一个子集，在满足容量和成本基础上使得子集中任意两个节点之间最小距离最大化。GDP是NP难问题，在不良设施选址、社交网络分析和生态环境保护等领域具有重要应用。现有研究已提出一些求解算法，但在大规模GDP求解方面仍存在局限性。基于此，设计强化驱动型禁忌搜索算法 （IDTS） 求解GDP。具体来说，该算法提出基于节点价值评估的贪心算法构造初始可行解，设计多邻域联合搜索机制探索解空间，采用快速增量计算策略降低复杂度，基于强化驱动机制增强搜索高质量邻近解的能力。实验部分在120个大规模GDP算例集上对比IDTS与现有几种算法，结果表明IDTS在求解大规模GDP时性能更优。

来源：2026年第4期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2026年第4期