任春玉
黑龍江大學信息科學與技術學院，黑龍江哈爾濱

摘　　　要：針對傳統的遺傳算法存在收斂速度慢，局部搜索能力差，易早熟的缺點，采用混合遺傳算法進行優化求解開放式車輛路線問題。即采用二重結構編碼，可以使問題變得更簡潔，提高遺傳法的搜索效率。用個體數量控制選擇策略，以保證群體的多樣性，用改進的順序交叉算子避免優良基因片斷在順序交叉時被破壞，保證算法能夠收斂到全局較優。較后，結合具體實例，通過實驗計算證明了該改進算法的良好性能。

關　鍵　詞：開放式車輛路線問題；二重結構編碼；個體數量控制；順序交叉；混合遺傳算法

１　引　言
開放式車輛路線問題（ＯｐｅｎＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＯＶＲＰ）是經典車輛路線問題（ＶｅｈｉｃｌｅＲｏｕ�玻簦椋睿纾校颍铮猓欤澹恚�ＶＲＰ）的拓展問題。ＯＶＲＰ問題研究方法主要包括精確算法、啟發式算法［１�玻玻莺椭悄軆灮�方法［３�玻矗荨Ｔ谇蠼獯笠幠！�復雜問題時，智能優化算法應用更廣泛，其中，遺傳算法具有簡單通用、魯棒性好、隱并行性和求解組合優化問題的良好特性。肖天國通過應用交叉、變異概率的自適應機制和交叉算子等技術，構造了一個求解帶軟時間窗的開放式車輛路徑問題的遺傳算法［５］。鄧猛針對開放的車輛路線安排問題，建立了以車流為基礎的數學模型，利用罰函數法來化簡約束條件，并設計了基于自然數編碼的遺傳算法［６］。但由于ＯＶＲＰ的特殊性，借助于標準遺傳算法存在收斂速度慢，局部搜索能力差，易早熟的缺點。因此，針對這些缺點，本文設計了一種混合遺傳算法進行優化求解。較后，通過算例，對模型和算法的性能進行了驗證。

登錄網站后可下載文件