A Novel Solution to the ATT48 Benchmark Problem

A solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for

7

002 tcO 2 ]SD.sc[ 1v9350.017:0viXraANovelSolutiontotheATT48Benchmark

Problem

AnthonyA.Ru a

NavalUnderseaWarfareCenterDivision

1176HowellStreetNewport,RI02841

February2,2008

Abstract

AsolutiontothebenchmarkATT48TravelingSalesmanProblem(fromtheTSPLIB95library)resultsfromisolatingthesetofverticesintotenopen-endedzoneswithninelengthwiseboundaries.Ineachzone,aminimum-lengthHamiltonianPath(HP)isfoundforeachcombinationofboundaryvertices,leadingtoanapproximationfortheminimum-lengthHamiltonianCycle(HC).DeterminationoftheoptimalHPsforsubse-quentzoneshasthee ectofautomatically lteringoutnon-optimalHPsfromearlierzones.AlthoughtheoptimalHCforATT48involvesonlytwocrossingedgesbetweenallzones(withoneexception),addinginter-zoneedgescanaccomodatemorecomplexproblems.

1Introduction

Givenasetofvertices,thewell-knownTravelingSalesmanProblem(TSP)in-volves ndingtheminimum-lengthHamiltonianCycle(HC):thepathvisitingeachvertexonceandreturningtothestartingvertex.

ThesymmetricTSPwithNverticeshas(N 1)!/2permutations,precludinganexhaustivesearchexceptforsmallN.Evenarelativelysmallproblem(e.g.,N=20)has1016distinctHCs;N=40leadsto1046distinctHCs.TheEuclideanTSPisclassi edasanNP-hardproblem1,havingnoknownalgorithmforthegeneralcasewhosenumberofoperationsisapolynomialfunctionofN.The(N 1)!/2permutationsassumethatanyvertexcanoccupyanyofNpositions.Isolatingverticesintospatialzoneslockseachintoalimitedrangeofpositions,subjecttoboundaryvertexpermutations.Thisfallsintothegeneralareaofdynamicprogramming2,3,4.

Partitioningtheverticesintosub-problemshasbeendonefortheEuclideanTSP5 10.Inparticular,Arora6obtainedaPolynomialTimeApproximationScheme(PTAS)generatingatourexceedingtheoptimallengthbynomorethan

1

A solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for

afactorof1+εintimeNO(1/ε).Theapproachinvolvedaboundingsquareboxdissectedintosquaresandshiftedrandomly,withrestrictionsonedgecrossings(tospeci edportals).Mitchell7independentlyobtainedasimilarresult.

Theapproachinthispaperdissectstheproblemlengthwiseand ndsoptimalHamiltonianPaths(HPs)—pathsvisitingeachvertexonce—fortheisolatedzonesindependentlyoftheothers.ThenumberofcombinationsofboundaryverticesdeterminesthenumberofoptimalHPsforeachzone.SetsofoptimalHPsforeachzone(withembeddedHPsfrompreviouszones)generateanHCforthesetofvertices.Whennoboundaryverticesareomitted,theoptimalHCwillcontainanoptimalHPfoundfromeachzone.

Thispaperillustratestheprocedureforabenchmarkproblem(i.e.,ATT4811)smallenoughtopermitadetaileddescriptionoftheentiresolutionprocess.Thesuccessoftheapproachdependsonlimitingthenumberofpotentialboundaryverticesandcrossingedges.Inpractice,sometimesasfewastwoedgeswillcrossaboundaryfromonezonetoanother.Thenumberofcrossingedgescanbeincreased,ifnecessary,toimprovethesolution.

2OutlineoftheApproach

Followingpreviousapproaches5 10,theproblemisbrokendownintosubprob-lemsthatdependoneachotherthroughboundaryinteractions.Theboundarieshavealengthwisenature,forming(doubly)open-endedzones.Figure1showstheseparationoftheATT4811verticesintotenzonesbymeansofnineintro-ducedboundaries,eachdissectingtheproblemlengthwise.Table1summarizesthezonesandpotentialboundaryverticesforeach.Eachzoneconnectstoadja-centzonesviaalimitednumberofedges.(Anedgeisastraightlineconnectingtwovertices.)

AsinglelengthwiseboundarycutstheoptimalHCintoanevennumberofHPs,thesumofwhichmusthavetheminimumlengthineachofthetwocreatedspatialzones.Forexample,iftwoHPsarecreated,theHPineachcreatedzone(terminatedatboundaryverticesintheotherzone)musthavetheminimumlength.IfanHPlengthexceedstheminimum,replacingitwithanotherHP(havingthesamevertices)willreducetheoverallHClength.Statedanotherway,itisnotpossibletodissecttheoptimalHCintotwoHPsandreplaceoneofthemwithashorterHPhavingthesamevertices.

TheboundaryverticescontainedbytheoptimalHCassociatedwithapar-ticulardissectionareingeneralnotknown,requiringtheenumerationofallpossibleboundaryverticeslocatedintheadjacentzone.Typically,notallpo-tentialboundaryverticeswillconnectedgestotheadjacentzone.Forexample,asfewastwoedges(n=mightconnecttwozones.Foreachvalueofn, 2)

b

thebinomialcoe cientprovidesthenumberofboundaryvertexcom-n

binations(bisthenumberofpotentialboundaryvertices).Summingoverallvaluesofnleadsto2b 1 1combinations(whenn=0andoddvaluesofnareeliminated).Aminimum-lengthHPisthenfoundforeachparticularboundary

2

A solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for

Figure1:SeparationoftheATT48verticesintotenopen-endedzones

vertexcombination,beginningattheleftendzonein gure1(zone1).

Thesecondboundaryfromtheleftin gure1isolatesbothzones1&2fromtheothervertices.Theapproachthen ndsthesetofminimumlengthHPsforthecombinedverticesinzones1&2inthesameway,exceptthatthepreviouslydeterminedHPsfromzone1becomeembeddedinthenewHPs.

Boundaryverticescancomprisealltheverticesintheadjacentzone,or(morelikely)asmallersubset,usuallythoseclosesttotheboundary.Verticesclosetotheboundaryoftenhavethee ectofeliminatingotherpotentialboundaryverticesbecausethelatteroftenleadtonon-optimalHCs.Table1.ATT48ZonesandBoundaryVerticesZone

4,35,45

2

2,29,42,5,48,39,324

16,22,3,23,11,47

6

38,31,46,44,18,7,368

27,43 …… 此处隐藏：11757字，全部文档内容请下载后查看。喜欢就下载吧 ……