资源描述：
《HEURISTIC APPROACHES FOR THE NO-DEPOT K-TRAVELING》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、HEURISTICAPPROACHESFORTHENO-DEPOTK-TRAVELINGSALESMENPROBLEMWITHAMINMAXOBJECTIVEAThesisbyBYUNGSOONASubmittedtotheOceofGraduateStudiesofTexasA&MUniversityinpartialful llmentoftherequirementsforthedegreeofMASTEROFSCIENCEMay2006MajorSubject:IndustrialEngineeringHEURISTI
2、CAPPROACHFORTHENO-DEPOTK-TRAVELINGSALESMENPROBLEMWITHAMINMAXOBJECTIVEAThesisbyBYUNGSOONASubmittedtotheOceofGraduateStudiesofTexasA&MUniversityinpartialful llmentoftherequirementsforthedegreeofMASTEROFSCIENCEApprovedby:ChairofCommittee,SergiyButenkoCommitteeMembers,I
3、llyaHicksYunlongZhangHeadofDepartment,BrettA.PetersMay2006MajorSubject:IndustrialEngineeringiiiABSTRACTHeuristicApproachesfortheNo-Depotk-TravelingSalesmenProblemwithaMinmaxObjective.(May2006)ByungsooNa,B.S.,PohangUniversityofScience&TechnologyChairofAdvisoryCommitte
4、e:Dr.SergiyButenkoThisthesisdealswiththeno-depotminmaxMultipleTravelingSalesmenProblem(MTSP),whichcanbeformulatedasfollows.Givenasetofncitiesandksalesmen, ndkdisjointtours(oneforeachsalesmen)suchthateachcitybelongstoexactlyonetourandthelengthofthelongestofktoursismin
5、imized.Theno-depotassumptionmeansthatthesalesmendonotstartfromandreturntoone xeddepot.Theno-depotmodelcanbeappliedindesigningpatrollingroutes,aswellasinbusinesssituations,especiallywheresalesmenworkfromhomeorthecompanyhasnocentraloce.Thismodelcanbealsoappliedtothejo
6、bschedulingproblemwithnjobsandkidenticalmachines.Despiteitspotentialapplicabilitytoanumberofimportantsituations,there-searchliteratureontheno-depotminmaxk-TSPhasbeenlimited,withnoreportsoncomputationalexperiments.ThepreviouslypublishedresultsincludedtheproofofNP-hard
7、nessoftheproblemofinterest,whichmotivatesusingheuristicsforitssolution.Thisthesisproposesseveralconstructionheuristicalgorithms,includinggreedyalgorithms,cluster rstandroutesecondalgorithms,androute rstandclus-tersecondalgorithms.Asalocalsearchmethodforasingletour,2-
8、optsearchandLin-Kernighanwereused,andforalocalsearchmethodbetweenmultipletours,relocationandexchange(edgeheuristics)wereused.Furthe
