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