開放式車輛路線問題的改進(jìn)混合遺傳算法
任春玉
（黑龍江大學(xué)信息科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150080）
摘 要：針對傳統(tǒng)的遺傳算法存在收斂速度慢，局部搜索能力差，易早熟的缺點(diǎn)，采用混合遺傳算法進(jìn)行優(yōu)化求解開放式車輛路線問題。即采用二重結(jié)構(gòu)編碼，可以使問題變得更簡潔，提高遺傳法的搜索效率．用個體數(shù)量控制選擇策略，以保證群體的多樣性，周改進(jìn)的順序交叉算子避免優(yōu)良基因片斷在順序交叉時被破壞，保證算法能夠收斂到全局****。最后，結(jié)合具體實(shí)例，通過買驗(yàn)計(jì)算證明了該改進(jìn)算法的艮好性能。
關(guān)鍵詞：開放式車輛路線問題；二重結(jié)構(gòu)編碼；個體數(shù)量控制；順序交叉；混合遺傳算法
中圖分類號：tp 29 文獻(xiàn)標(biāo)識碼：a
1引言
開放式車輛路線問題(，ovrp)是經(jīng)典車輛路線問題(vrp)的拓展問題。
ovrp問題研究方法主要包括精確算法、啟發(fā)式算法和智能優(yōu)化方法；在求解大規(guī)模、
復(fù)雜問題時，智能優(yōu)化算法應(yīng)用更廣泛，其中，遺傳算法具有簡單通用、魯棒性好、隱并行性和求解組合優(yōu)化問題的良好特性。肖天國通過應(yīng)用交叉、變異概率的自適應(yīng)機(jī)制和交叉算子等技術(shù)，構(gòu)造了一個求解帶軟時間窗的開放式車輛路徑問題的遺傳算法。鄧猛針對開放的車輛路線安排問題，建立以車流為基礎(chǔ)的數(shù)學(xué)模型，利用罰函數(shù)法來化簡約束條件，并設(shè)計(jì)了基于自然數(shù)編碼的遺傳算法．
但由于ovrp的特殊性，借助于標(biāo)準(zhǔn)遺傳算法存在收斂速度慢，局部搜索能力差，易早熟的缺點(diǎn)。因此，針對這些缺點(diǎn)，本文設(shè)計(jì)了一種混合遺傳算法進(jìn)行優(yōu)化求解。最后，通過算例，對模型和算法的性能進(jìn)行了驗(yàn)證。
2數(shù)學(xué)模型
ovrp和vrp最顯著的區(qū)別在于，車輛在服務(wù)完最后一個顧客點(diǎn)后，不要求其回到出發(fā)車場，若需要回到車場，則必須沿原路返回，如圖l所示。
約束條件
式中，m為配送中心擁有車輛數(shù)；wk為車輛載重量；n為客戶需求點(diǎn)數(shù)；ri為需求點(diǎn)需貨量；lk為每輛車日****運(yùn)行距離；dij為配送中心到各需求點(diǎn)距離及需求點(diǎn)之間距離。
約束條件式(2)表示每輛車輛所運(yùn)送量不超出其載重量；約束條件式(3)表示每個需求點(diǎn)由一輛車送貨；約束條件式(4)表示若客戶點(diǎn)j由車輛k送貨，則車輛必從某點(diǎn)。到達(dá)點(diǎn)j；約束條件式(5)表示若客戶點(diǎn)i由車輛k送貨，則車輛k送完該點(diǎn)貨后必到達(dá)另一個點(diǎn)j；約束條件式(6)表示每條線路距離不大于車輛****運(yùn)行距離為lk。
3 混合遺傳算法應(yīng)用描述
針對傳統(tǒng)遺傳算法不足，本文設(shè)計(jì)了一種混合遺傳算法，即采用二重結(jié)構(gòu)編碼，提高遺傳法的搜索效率；采用個體數(shù)量控制選擇策略以保證群體的多樣性；采用改進(jìn)的順序交叉算子避免優(yōu)良基因片斷在順序變叉時被破壞，保證算法能夠收斂到全局****。
1)遺傳編碼個體染色體表示的二重結(jié)構(gòu)由變量碼和附加碼兩行組成。上行s(i)為變量x(j)的附加碼s(i)=j，下行為變量xsi，對應(yīng)于附加碼s(i)的值。
解碼算法的步驟如下：
step 1 s=o，sum =o。
step 2 若xs（i）=o，則ps（i） =0，執(zhí)行step 4，否則，執(zhí)行step 3。
step 3 如果ei≤sum+as(i)≤li則ps(i)=l，sum= sum+as(i)，否則，ps(i) =0。
step 4 i=i+1，如果i≤n，返回step 3，否則終止。
2)初始解的形成設(shè)表示編碼的…維數(shù)組為p[n]，先令p[n]={0，l，2，…，n-l}，再利用偽隨機(jī)數(shù)發(fā)生器，產(chǎn)生2個隨機(jī)整數(shù)j1，j2其中，j1，j2屬于[1，n,2]。交換數(shù)組中p[j1]和p[j2]2個元素，形成一個隨機(jī)的初始解。重復(fù)該過程，直至達(dá)到所需的群體規(guī)模為止。
3)適應(yīng)度函數(shù)采用輪盤賭選擇法，要求適應(yīng)度函數(shù)為非負(fù)，通過下面的變化將目標(biāo)函轉(zhuǎn)化為適應(yīng)度函數(shù)。
| 
