考虑容量和成本的最大最小多样性选址问题的强化驱动型禁忌搜索算法

打开文本图片集

中图分类号：TP181 文献标志码：A 文章编号：1001-3695（2026）04-022-1154-10

doi： 10.19734/j. issn.1001-3695.2025.07.0252

Intensification-driven tabu search algorithm generalized dispersion problem

， （BusinessSchool， ，Shanghai ，China）

Abstract：Generalized dispersion problem （GDP）is to select a subsetof nodes fromanundirected complete graph such that the minimumdistancebetweenanytwo nodes inthesubsetis maximizedwhilethelowercapacitylimitanduppercostlimit are satisfied.GDPisanNP-hardproblemwithimportantapplicationsinundesirablefacilitylocation，socialnetworkanalysis， ecologicalenvironmentprotection，etc.Although existing studieshaveproposedsolution methods solving GDP，theyare limited especiallywhenapliedtolarge-scaleGDP.Thisworkproposedthefirst intensification-driventabusearch（IDTS）algorithm tackling GDP.Specifically，IDTSemployed afast greedyalgorithm toconstructan initial feasible solution，ajoint neighborhoodexplorationstrategythat integratedadd，drop，andconstrainedswapneighborhoods toexplorethesearch space， andafastincrementalcalculationstrategytoqucklyevaluate theobjectivefunctionvalue.ItwasimportantthatIDTSexplored thesearch spaceusing anintensification-driven mechanismtoincrease theprobabilityoffindingahigh-qualitysolution.Extensiveexperimentsonthreesetsof120 GDPbenchmark instancesfromtheliteratureshowthat IDTS competesveryfavorably with state-of-the-art algorithms，especially large-scale GDP.

Keywords：generalized dispersionproblem（GDP）；facility location；heuristic algorithm；tabu search；intensificationmechanism

0引言

多样性问题（dispersion/diversityproblem，DP）（也称为分散度问题）是定义在一个无向完全图 G=（V，E） 上的组合优化问题，其中节点集 V 由 n 个节点构成，各节点以整数1至 n 标记；边集 E 为图中全部边的集合，每条边 {i，j}∈E 关联一个距离度量 dij 。（剩余20022字）