Variable neighborhoodsearchforthecostconstrainedminimumlabel spanning treeandlabelconstrainedminimumspanningtreeproblems

Given anundirectedgraphwhoseedgesarelabeledorcolored,edgeweightsindicatingthecostofan edge, andapositivebudget B, thegoalofthecostconstrainedminimumlabelspanningtree(CCMLST) problemistofindaspanningtreethatusestheminimumnumberoflabelswhileensuringitscostdoes not exceed B. Thelabelconstrainedminimumspanningtree(LCMST)problemiscloselyrelatedtothe CCMLSTproblem.Here,wearegivenathreshold K on thenumberoflabels.Thegoalistofinda minimumweightspanningtreethatusesatmost K distinctlabels.Bothoftheseproblemsare motivatedfromthedesignoftelecommunicationnetworksandareknowntobeNP-complete [15]. In thispaper,wepresentavariableneighborhoodsearch(VNS)algorithmfortheCCMLSTproblem. The VNSalgorithmusesneighborhoodsdefinedonthelabels.WealsoadapttheVNSalgorithmtothe LCMST problem.WethentesttheVNSalgorithmonexistingdatasetsaswellasalarge-scaledataset based onTSPLIB [12] instancesranginginsizefrom500to1000nodes.FortheLCMSTproblem,we comparetheVNSproceduretoageneticalgorithm(GA)andtwolocalsearchproceduressuggestedin [15]. FortheCCMLSTproblem,theproceduressuggestedin [15] can beappliedbymeansofabinary search procedure.Consequently,wecomparedourVNSalgorithmtotheGAandtwolocalsearch proceduressuggestedin [15]. TheoverallresultsdemonstratethattheproposedVNSalgorithmisof high qualityandcomputessolutionsrapidly.Onourtestdatasets,itobtainstheoptimalsolutioninall instancesforwhichtheoptimalsolutionisknown.Further,itsignificantlyoutperformstheGAandtwo local searchproceduresdescribedin [15].