基于改進(jìn)遺傳算法的帶軟時(shí)間窗車(chē)輛路徑問(wèn)題的研究.pdf

1、中國(guó)物流與采購(gòu)聯(lián)合會(huì)數(shù)據(jù)顯示2014年我國(guó)社會(huì)物流總成本占GDP的比重約為16.6％，這一數(shù)據(jù)高于全球平均水平約5個(gè)百分點(diǎn)。第三產(chǎn)業(yè)統(tǒng)計(jì)年鑒的數(shù)據(jù)顯示近20年來(lái)運(yùn)輸成本在物流總成本中所占的比重均超過(guò)了50％。上述數(shù)據(jù)表明車(chē)輛路徑問(wèn)題是影響我國(guó)物流總成本偏高的一個(gè)重要因素。在實(shí)際的運(yùn)輸過(guò)程中，由于客戶規(guī)模一般較大，很難做到使每一個(gè)客戶都達(dá)到最滿意的結(jié)果，故軟時(shí)間窗車(chē)輛路徑問(wèn)題(Vehicle Routing Problem with So

2、ft TimeWindow, VRPSTW)更加貼近實(shí)際運(yùn)輸情況。另外VRPSTW會(huì)充分考慮每一個(gè)節(jié)點(diǎn)上的客戶滿意度問(wèn)題。因此研究VRPSTW無(wú)論是在提高顧客滿意度方面還是在縮減物流成本方面都在物流運(yùn)輸中起著最為重要的作用。
　　遺傳算法(Genetic Algorithm，GA)是求解VRPSTW時(shí)應(yīng)用更廣泛、性能表現(xiàn)更為優(yōu)越的。但是該算法也存在早熟問(wèn)題、易收斂到局部最優(yōu)解的問(wèn)題和求解精度有待進(jìn)一步提高的問(wèn)題。為此本文采取了以下

3、措施來(lái)解決這些問(wèn)題:引入最佳種群規(guī)模的計(jì)算方法;采用隨機(jī)生成方式來(lái)產(chǎn)生初始種群;采用自適應(yīng)機(jī)制來(lái)確定交叉概率和變異概率;采取基于排序法的隨機(jī)競(jìng)爭(zhēng)選擇和最佳保留相結(jié)合的選擇策略;引入小生境操作技術(shù)的交叉算子A;采用局部爬山變異算子。為了使整個(gè)算法能更好的解決VRPSTW，本文做了如下工作，首先綜合考慮了顧客的滿意度、物流公司的費(fèi)用支出、顧客的特殊要求等因素后，對(duì)目標(biāo)函數(shù)進(jìn)行了權(quán)重的設(shè)置以及對(duì)約束條件進(jìn)行了罰函數(shù)等方面的處理。其次除了對(duì)遺傳

4、算子的改進(jìn)外，還對(duì)編碼解碼、種群初始化方法、控制參數(shù)的設(shè)置以及終止條件的確定等方面進(jìn)行了適度的調(diào)整工作。最后為測(cè)算改進(jìn)算法的有效性，針對(duì)同一數(shù)據(jù)集進(jìn)行了全方位多角度的對(duì)比分析工作，力求使后續(xù)分析工作更具有說(shuō)服力。
　　針對(duì)GA求解VRPSTW時(shí)所表現(xiàn)出的種種不足，本文做出相應(yīng)改進(jìn)調(diào)整方案后。對(duì)solomon標(biāo)準(zhǔn)庫(kù)中C101數(shù)據(jù)集的100個(gè)節(jié)點(diǎn)進(jìn)行測(cè)試，以驗(yàn)證改進(jìn)方案的合理性。在大量的測(cè)算過(guò)程中，算法并沒(méi)有出現(xiàn)早熟現(xiàn)象和收斂到局部最