GRASP with path-relinking for the quadratic assignment problem

Abstract. This paper describes a GRASP with path-relinking heuristic for the quadratic assignment problem. GRASP is a multi-start procedure, where different points in the search space are probed with local search for high-quality solutions. Each iteration

GRASPwithpath-relinkingfortheQuadraticAssignmentProblem

CarlosA.S.Oliveira1,PanosM.Pardalos1,andMauricioG.C.Resende2

Dept.ofIndustrialandSystemsEngineering,UniversityofFlorida303WeilHall,

Gainesville,FL32611,USA({oliveira,pardalos}@ufl.edu)

AlgorithmsandOptimizationResearchDept.,AT&TLabsResearchRoomC241,180Park

Avenue,FlorhamPark,NJ07932,USA(mgcr@http://www.wendangwang.com)

1

2

Abstract.ThispaperdescribesaGRASPwithpath-relinkingheuristicforthequadraticassignmentproblem.GRASPisamulti-startprocedure,wherediffer-entpointsinthesearchspaceareprobedwithlocalsearchforhigh-qualityso-lutions.EachiterationofGRASPconsistsoftheconstructionofarandomizedgreedysolution,followedbylocalsearch,startingfromtheconstructedsolution.Path-relinkingisanapproachtointegrateintensi cationanddiversi cationinsearch.Itconsistsinexploringtrajectoriesthatconnecthigh-qualitysolutions.Thetrajectoryisgeneratedbyintroducingintheinitialsolution,attributesoftheguidingsolution.ExperimentalresultsillustratetheeffectivenessofGRASPwithpath-relinkingoverpureGRASPonthequadraticassignmentproblem.

1Introduction

Thequadraticassignmentproblem(QAP)was rstproposedbyKoopmansandBeck-man[10]inthecontextoftheplantlocationproblem.Givennfacilities,representedbythesetF={f1,...,fn},andnlocationsrepresentedbythesetL={l1,...,ln},onemustdeterminetowhichlocationeachfacilitymustbeassigned.LetAn×n=(ai,j)beamatrixwhereai,j∈R+representsthe owbetweenfacilitiesfiandfj.LetBn×n=(bi,j)beamatrixwhereentrybi,j∈R+representsthedistancebetweenlocationsliandlj.Letp:{1...n}→{1...n}beanassignmentandde nethecostofthisassignmenttobe

c(p)=∑

ni=1j=1

∑ai,jbp(i),p(j).

n

IntheQAP,wewantto ndapermutationvectorp∈Πnthatminimizestheassign-mentcost,i.e.minc(p),subjecttop∈Πn,whereΠnisthesetofallpermutationsof{1,...,n}.TheQAPiswellknowntobestronglyNP-hard[18].

GRASP,orgreedyrandomizedadaptivesearchprocedures[5,6,8,17],havebeenpreviouslyappliedtotheQAP[12,14,15].Inthispaper,wepresentanewGRASPfortheQAP,whichmakesuseofpath-relinkingasanintensi cationmechanism.InSection2,webrie yreviewGRASPandpath-relinking,andgiveadescriptionofhowbotharecombinedto ndapproximatesolutionstotheQAP.ExperimentalresultswithbenchmarkinstancesarepresentedinSection3.Finally,inSection4wedrawsomeconcludingremarks.

GRASP with path relinking for the quadratic assignment problem相关文档

最新文档

返回顶部