資源描述：
《帶時間窗車輛路徑問題及其算法設(shè)計》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、ClassifiedIndex:O224
U.D.C.:519.863DissertationfortheMasterDegreeinScienceTHEOPTIMIZATIONANDALGORITHMDESINNOFVEHICLEROUTINGPROBLEMSWITHTIMEWINDOWSCandidate:SuLihongSupervisor:Prof.ShangShoutingAcademicDegreeAppliedfor:MasterofScienceSpecialty:FoundationalMathe
2、maticalAffiliation:HeilongjiangCollegeofConstructionDateofOralExamination:June,2010University:HarbinInstituteofTechnology哈爾濱工業(yè)大學(xué)理學(xué)碩士學(xué)位論文摘要物流是一個新興學(xué)科，配送是現(xiàn)代物流的一個重要內(nèi)容，合理安排車輛配送路線可以降低運輸成本，提高經(jīng)濟效益。車輛路徑問題是一類在物流配送調(diào)度中具有廣泛應(yīng)用的組合優(yōu)化問題，屬于強NP難題。有時間窗車輛路徑問題比具有簡單約束的車輛路徑問題更加難以求解。本
3、文對標(biāo)準(zhǔn)遺傳算法的發(fā)展概況、基本概念、基本原理、理論基礎(chǔ)、收斂性、特點及其應(yīng)用等方面作了簡明扼要的介紹，并對遺傳算法的實現(xiàn)技術(shù)作了較詳細(xì)的總結(jié)。為研究有時間窗裝卸問題的遺傳算法作了充分準(zhǔn)備。本文在VRP研究工作的基礎(chǔ)上，考慮現(xiàn)有的VRPTW模型，通過設(shè)定懲罰函數(shù)，更加全面的把握客戶對服務(wù)時間的約束、車輛運輸費用和時間效應(yīng)成本等因素，切合實際建立了有懲罰函數(shù)的VRPTW優(yōu)化模型。并針對該模型設(shè)計了基于客戶分組的兩階段求解思路：第一階段，從影響客戶滿意因素的角度出發(fā)，先應(yīng)用k-means算法對配送網(wǎng)點進行配送區(qū)域劃分，
4、將大規(guī)模的VRP簡化成小規(guī)模的VRP，降低計算量，提高求解速度；第二階段，針對每個客戶組組內(nèi)構(gòu)造最優(yōu)路徑，采用具有全局空間搜索和隱含并行性優(yōu)點的遺傳算法對優(yōu)化模型進行求解，并運用Matlab的遺傳算法工具箱加以實現(xiàn)，進而形成一種系統(tǒng)的考慮客戶全面需求屬性和減少計算工作量的求解方法。并通過具體實例，將運算結(jié)果與其他優(yōu)化算法進行比較，證明了本文提出的改進遺傳算法在處理路徑優(yōu)化問題上具有明顯的優(yōu)勢，在所用配送車數(shù)量最小的前提下，可得到一個相對最短的行駛路線，實現(xiàn)總運輸成本最低的目的。關(guān)鍵詞：車輛路徑問題；客戶分組；時間窗
5、；k-means算法；遺傳算法-I-哈爾濱工業(yè)大學(xué)理學(xué)碩士學(xué)位論文AbstractLogisticsisanemergingdisciplineanddistributionisanimportantelementofmodernlogistics．Wellarrangementforvehicleroutesdistributioncancutdowntransportcostandimproveefficiency．VehicleRoutingProblem(VRP)isacombinationoptimiza
6、tionproblemintransportationlogistics，whichhasbeenappliedinmanyfields．ItisastrongNPproblem．ThevehicleroutingproblemwithtimewindowsVRPTWismoredifficulttosolvethanVRPwithsimpleconditions．Inthispaper,brieflyintroducethestandardgeneticalgorithminthegeneralsituation
7、ofthedevelopment，basicconcept，basicprinciple，rationale，convergence，characteranditsapplication.TheseresearchesmadefullpreparationforustostudyVRPTW．BasedontheVRP,thispaperconsiderstimewindowsconstraintsofcustomerservice，transportationcostsandtimeeffectcostsmorec
8、omprehensivly,soastosetthepenaltyfunctionandestablishthemodelofthevehicleroutingproblemwithtimewindows．Then，thetwo-stageapproachhasbeendesigned：thefirststage，theconsiderationofcust
