資源描述：
《多車場多車型車輛路徑問題的改進(jìn)遺傳算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、計(jì)算機(jī)與現(xiàn)代化2008年第9期JISUANJIYUXIANDAIHUA總第157期文章編號(hào)：1006—2475(2008)09-00104)4多車場多車型車輛路徑問題的改進(jìn)遺傳算法楊元峰(蘇州市職業(yè)大學(xué)計(jì)算機(jī)工程系，江蘇蘇州215104)摘要：在給出有時(shí)間窗約束的多車場多車型車輛路徑問題的基于直觀描述的數(shù)學(xué)模型基礎(chǔ)上，引入一種新的編碼方式，并將Rc交叉算子進(jìn)行修正，構(gòu)造出一種解決該問題的模擬退火遺傳算法，實(shí)驗(yàn)證明能夠有效地解決優(yōu)化問題。關(guān)鍵詞：車輛路徑問題；多車場；多車型；遺傳算法；模擬退火算法中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)識(shí)碼：A
2、AnImprovedGeneticAlgorithmforMultiple-·depotandHeterogeneous-vehicleVehicleRoutingProblemYANGYuan—feng(DepartmentofComputerEngineering，S~houVocationalUniversity，Suzhou215104，China)Abstract：Thispaperstatesamodelofmultiple-·depotandheterogeneous·-vehiclevehicleroutingprob
3、lemwithtimewindowsbasedonnaturaldescription．AnimprovedgeneticalgorithmisproposedbasedOilanewcodingmethodandamendedRCcrossover叩·erator．TheexperimentalresultsshowthatthisgeneticalgorithmCansuitforsolvingmultiple-depotandheterogeneous—vehicleve—hicleroutingproblem．Keywords
4、：vehicleroutingproblem；multi—depot；heterogeneous—vehicle；geneticalgorithm；simulatedannealingalgorithm0引言’1問題的描述和數(shù)學(xué)模型車輛路徑問題(Vehiclemutingproblem，VRP)由有時(shí)間窗約束的多車場多車型車輛調(diào)度問題描Dantzing和Ramser于1959年首次提出，它是指對一述為：有M個(gè)車場，各自擁有L種類型的車輛構(gòu)成的系列發(fā)貨點(diǎn)(或收貨點(diǎn))，組織適當(dāng)?shù)男熊嚶肪€，滿足混合車隊(duì)，每種類型車的載重量為Q。(1∈L)，
5、且此類客戶的需求，并在一定的約束條件下，達(dá)到一定的目型車輛數(shù)為K。(m∈M，l∈L)。負(fù)責(zé)對N個(gè)用戶進(jìn)標(biāo)(諸如路程最短、成本最小、耗費(fèi)時(shí)間盡量少等)，行貨物運(yùn)輸工作，用戶i的貨物需求為gi(i=1，2，?屬于NP難度問題。，N)，且必須在時(shí)間窗口[ET；，LT；]完成，若車輛在遺傳算法有較強(qiáng)的全局搜索性能，但它的爬山能ET；之前到達(dá)用戶i處，則在此等待；如果車輛到達(dá)時(shí)力弱，在實(shí)際應(yīng)用中容易產(chǎn)生早熟收斂的問題，且在間晚于LT；，用戶i的需求將被延遲進(jìn)行。要求一個(gè)進(jìn)化后期搜索效率較低。而模擬退火算法卻具有擺合適的車輛調(diào)度方案，使各車場的車
6、輛能滿足所有用脫局部最優(yōu)點(diǎn)的能力，能抑制遺傳算法的早熟現(xiàn)象。戶的需求，并使車輛總的運(yùn)輸成本最低。本文提出的模擬退火遺傳算法即模擬退火算法和遺在文獻(xiàn)中，多車場問題常轉(zhuǎn)化為單車場問題來處傳算法相結(jié)合的進(jìn)化算法?，主要是利用模擬退火理，其關(guān)鍵是首先對每個(gè)車場確定它所服務(wù)的客算法的Boltzmann機(jī)制來控制遺傳算法的交叉、變異戶[2-3]。但是由于這種解決思路首先將客戶分配給各操作中子代染色體的選擇，在父代與子代染色體中引車場，再求解單個(gè)車場的優(yōu)化解，這樣即使每個(gè)車場入競爭。模擬退火算法能使解的收斂從局部最優(yōu)跳的路徑優(yōu)化都得到了最優(yōu)解，但從
7、整個(gè)調(diào)度問題來出，最終達(dá)到全局收斂?？?，很難得到全局最優(yōu)解。基于中國配送調(diào)度的實(shí)際情況、特點(diǎn)，本文吸收前人的研究成果訓(xùn)和對實(shí)收稿日期：2007-06—11．作者簡介：楊元峰(1973一)，男，江蘇鹽城人，蘇州市職業(yè)大學(xué)計(jì)算機(jī)工程系講師，碩士，研究方向：智能信息處理及網(wǎng)絡(luò)應(yīng)用。2008年第9期楊元峰：多車場多車型車輛路徑問題的改進(jìn)遺傳算法l1際應(yīng)用中的車輛調(diào)度問題進(jìn)行分析，將多車場車輛調(diào)由此獲得的解僅表示每輛車訪問了哪些用戶，并度問題本身看作一個(gè)復(fù)雜的組合優(yōu)化問題進(jìn)行研究，沒有給出訪問的順序。但問題就轉(zhuǎn)變?yōu)榇_定每輛車在原有的研究基礎(chǔ)上考
8、慮多車場、多車型、有時(shí)間窗訪問用戶的順序，即n個(gè)小規(guī)模的TSP問題。本文用等情況，并初步考慮了交通對配送的影響和車輛行駛文獻(xiàn)[8]中改進(jìn)的節(jié)約算法來求解這些TSP問題。成本，建立下文的數(shù)學(xué)模型。并對用戶的時(shí)間窗得不由于規(guī)
