搜索
Travelingsalesmanproblem1IntroductionThetravelingsalesmanproblem(TSP)isanNP-hardproblemincombinatorialoptimizationstudiedinoperationsresearchandtheoreticalcomputerscience.Givenalistofcitiesandtheirpairwisedistances,thetaskistofindtheshortestpossibletourthatvisitseachcityexactlyonce.ItisaspecialcaseoftheTravelingpurchaserproblem.Theproblemwasfirstformulatedasamathematicalproblemin1930andisoneofthemostintensivelystudiedproblemsinoptimization.Itisusedasabenchmarkformanyoptimizationmethods.Eventhoughtheproblemiscomputationallydifficult,alargenumberofheuristicsandexactmethodsareknown,sothatsomeinstanceswithtensofthousandsofcitiescanbesolved.TheTSPhasseveralapplicationseveninitspurestformulation,suchasplanning,logistics,andthemanufactureofmicrochips.Slightlymodified,itappearsasasub-probleminmanyareas,suchasDNAsequencing.Intheseapplications,theconceptcityrepresents,forexample,customers,solderingpoints,orDNAfragments,andtheconceptdistancerepresentstravelingtimesorcost,orasimilaritymeasurebetweenDNAfragments.Inmanyapplications,additionalconstraintssuchaslimitedresourcesortimewindowsmaketheproblemconsiderablyharder.Inthetheoryofcomputationalcomplexity,thedecisionversionoftheTSP(where,givenalengthL,thetaskistodecidewhetheranytourisshorterthanL)belongstotheclassofNP-completeproblems.Thus,itislikelythattheworstcaserunningtimeforanyalgorithmfortheTSPincreasesexponentiallywiththenumberofcities.2HistoryTheoriginsofthetravellingsalesmanproblemareunclear.Ahandbookfortravellingsalesmenfrom1832mentionstheproblemandincludesexampletoursthroughGermanyandSwitzerland,butcontainsnomathematicaltreatment.WilliamRowanHamiltonThetravellingsalesmanproblemwasdefinedinthe1800sbytheIrishmathematicianW.R.HamiltonandbytheBritishmathematicianThomasKirkman.Hamilton’sIcosianGamewasarecreationalpuzzlebasedonfindingaHamiltoniancycle.ThegeneralformoftheTSPappearstohavebeenfirststudiedbymathematiciansduringthe1930sinViennaandatHarvard,notablybyKarlMenger,whodefinestheproblem,considerstheobviousbrute-forcealgorithm,andobservesthenon-optimalityof2thenearestneighbourheuristic:Wedenotebymessengerproblem(sinceinpracticethisquestionshouldbesolvedbyeachpostman,anywayalsobymanytravelers)thetasktofind,forfinitelymanypointswhosepairwisedistancesareknown,theshortestrouteconnectingthepoints.Ofcourse,thisproblemissolvablebyfinitelymanytrials.Ruleswhichwouldpushthenumberoftrialsbelowthenumberofpermutationsofthegivenpoints,arenotknown.Therulethatonefirstshouldgofromthestartingpointtotheclosestpoint,thentothepointclosesttothis,etc.,ingeneraldoesnotyieldtheshortestroute.HasslerWhitneyatPrincetonUniversityintroducedthenametravellingsalesmanproblemsoonafter.Inthe1950sand1960s,theproblembecameincreasinglypopularinscientificcirclesinEuropeandtheUSA.NotablecontributionsweremadebyGeorgeDantzig,DelbertRayFulkersonandSelmerM.JohnsonattheRANDCorporationinSantaMonica,whoexpressedtheproblemasanintegerlinearprogramanddevelopedthecuttingplanemethodforitssolution.Withthesenewmethodstheysolvedaninstancewith49citiestooptimalitybyconstructingatourandprovingthatnoothertourcouldbeshorter.Inthefollowingdecades,theproblemwasstudiedbymanyresearchersfrommathematics,computerscience,chemistry,physics,andothersciences.RichardM.Karpshowedin1972thattheHamiltoniancycleproblemwasNP-complete,whichimpliestheNP-hardnessofTSP.Thissuppliedamathematicalexplanationfortheapparentcomputationaldifficultyoffindingoptimaltours.Greatprogresswasmadeinthelate1970sand1980,whenGrötschel,Padberg,Rinaldiandothersmanagedtoexactlysolveinstanceswithupto2392cities,usingcuttingplanesandbranch-and-bound.Inthe1990s,Applegate,Bixby,Chvátal,andCookdevelopedtheprogramConcordethathasbeenusedinmanyrecentrecordsolutions.GerhardReineltpublishedtheTSPLIBin1991,acollectionofbenchmarkinstancesofvaryingdifficulty,whichhasbeenusedbymanyresearchgroupsforcomparingresults.In2005,Cookandotherscomputedanoptimaltourthrougha33,810-cityinstancegivenbyamicrochiplayoutproblem,currentlythelargestsolvedTSPLIBinstance.Formanyotherinstanceswithmillionsofcities,solutionscanbefoundthatareguaranteedtobewithin1%ofanoptimaltour.3Description3.1AsagraphproblemTSPcanbemodeledasanundirectedweightedgraph,suchthatcitiesarethegraph'svertices,pathsarethegraph'sedges,andapath'sdistanceistheedge'slength.Itisaminimizationproblemstartingandfinishingataspecifiedvertex3afterhavingvisitedeachothervertexexactlyonce.AnHamiltoniancycleisaoptimaltourofaTSPwhereeachedgehasadistanceproportionaltothedistance.Often,themodelisacompletegraph(i.e.,anedgeconnectseachpairofvertices).Ifnopathexistsbetweentwocities,addinganarbitrarilylongedgewillcompletethegraphwithoutaffectingtheoptimaltour.SymmetricTSPwithfourcitiesTSPcanbemodeledasanundirectedweightedgraph,suchthatcitiesarethegraph'svertices,pathsarethegraph'sedges,andapath'sdistanceistheedge'slength.Itisaminimizationproblemstartingandfinishingataspecifiedvertexafterhavingvisitedeachothervertexexactlyonce.AnHamiltoniancycleisaoptimaltourofaTSPwhereeachedgehasadistanceproportionaltothedistance.Often,themodelisacompletegraph(i.e.