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