混合遺傳算法在帶時(shí)間窗車輛路徑問題中的研究與實(shí)現(xiàn).pdf

1、車輛路徑問題(Vehicle Routing Problem，VRP)是對(duì)一系列給定的顧客，確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使其從車場(chǎng)中心出發(fā)，按一定順序通過它們，最后返回車場(chǎng)，并在滿足一定的約束條件下(如車輛載重量、顧客需求量、時(shí)間窗限制等)，使總運(yùn)輸成本最小。車輛路徑問題是物流系統(tǒng)實(shí)物運(yùn)輸調(diào)度中的關(guān)鍵環(huán)節(jié)。合理安排車輛，對(duì)車輛路徑進(jìn)行優(yōu)化，不但可以降低物流成本，還可以提高顧客滿意度，這對(duì)于整個(gè)物流系統(tǒng)具有重要的理論和現(xiàn)實(shí)意義。

2、 VRP是帶約束條件的組合優(yōu)化問題，屬于NP完全問題，采用傳統(tǒng)精確優(yōu)化方法難以得到令人滿意的結(jié)果。智能優(yōu)化算法能在多項(xiàng)式時(shí)間內(nèi)獲得該問題的近似解，因此成為該問題的研究熱點(diǎn)。遺傳算法(Genetic Algorithm，GA)、模擬退火算法(Simulated Annealing，SA)和禁忌算法(Tabu Search，TS)是智能優(yōu)化算法中的典型啟發(fā)式算法?；谶@三種算法，本文對(duì)帶軟時(shí)間窗車輛路徑問題(Vehicle Routing

3、Problem with Soft Time Window，VRPSTM)進(jìn)行分析，建立相應(yīng)的數(shù)學(xué)模型，提出一種混合遺傳算法求解VRPSTW。為了提高初始種群的質(zhì)量，算法提出改進(jìn)的Sweep算法啟發(fā)式地構(gòu)造初始種群；設(shè)計(jì)了一種啟發(fā)式最大插入交叉算子，以提高算法的收斂速度和防止遺傳操作產(chǎn)生不可行染色體；采用SA及TS作為優(yōu)化算子，以增強(qiáng)遺傳算法的局部搜索能力。最后用Solomon's instances集合中的實(shí)例對(duì)該算法進(jìn)行實(shí)驗(yàn)。與其他