王超 袁杰紅

摘要：傳統(tǒng)遺傳算法在求解HVRP問題時(shí)尋優(yōu)效率不高，在搜索過程中易陷入局部最優(yōu)，發(fā)生早熟。為解決上述問題，文章在傳統(tǒng)遺傳算法的基礎(chǔ)上，采用多個(gè)子算法并行分布、同時(shí)迭代的方式調(diào)整算法結(jié)構(gòu)，并引入遷移算子實(shí)現(xiàn)迭代過程中各子算法間的信息共事，以提升尋優(yōu)效率。

關(guān)鍵詞：車輛路徑問題;多車型車輛路徑;遷移算子;并行遺傳

在運(yùn)籌學(xué)中，車輛路徑問題（Vehicle Routing Problem，VRP）是經(jīng)典的組合優(yōu)化問題，已被證明具有NP計(jì)算復(fù)雜性，求解多采用近似算法和啟發(fā)式算法㈣。遺傳算法是模仿生物遺傳過程的一種方法，每迭代一次既表示遺傳一代，按照一定概率執(zhí)行選擇、交叉和變異算子，獲得優(yōu)良種群。傳統(tǒng)遺傳算法在求解VRP問題時(shí)容易陷入局部最優(yōu)，所得近似最優(yōu)解常不甚理想。本文采用分布式并行遺傳算法，旨在提升算法搜索速度和尋優(yōu)效果。

1多車型車輛路徑問題模型建立

在上述模型中，公式（1）表示車輛不可超載，公式（2）表示車輛起止點(diǎn)均為配送中心，公式（3）表示所有客戶均被服務(wù)，且任一客戶僅由一輛車服務(wù)，公式（4）為0-1變量。 2分布式并行遺傳算法設(shè)計(jì)

2.1算法介紹

分布式并行遺傳算法（MDPGA）是在傳統(tǒng)遺傳算法（sGA）的基礎(chǔ)上，依據(jù)分布式并行處理模型，對算法結(jié)構(gòu)進(jìn)行改變，以實(shí)現(xiàn)并行化操作。它將種群分成若干個(gè)子群并分配給各自對應(yīng)的處理器，每個(gè)處理器獨(dú)立的實(shí)現(xiàn)一個(gè)完整的串行遺傳算法，并按遷移算子對子群體間的若干個(gè)體進(jìn)行遷移，在引入優(yōu)良個(gè)體的同時(shí)豐富了種群的多樣性，有效避免了早熟現(xiàn)象的發(fā)生。

除遺傳算子外，分布式并行遺傳算法還引入了遷移算子，來負(fù)責(zé)各個(gè)分處理器之間的個(gè)體交換，以加速較好個(gè)體在各子種群中的傳播。遷移算子主要考慮遷移規(guī)模、遷移拓?fù)浜瓦w移策略三方面的內(nèi)容。本文對遷移規(guī)模的確定主要依據(jù)經(jīng)驗(yàn)，取子種群染色體數(shù)目的18%。遷移拓?fù)涫侵竷?yōu)良個(gè)體在子種群中的傳播方式，本文采用一對多遷移方式。遷移策略主要是指遷移周期的確定，本文選擇固定遷移周期。

2.2算法步驟

采用分布式并行遺傳算法求解HVRP問題，算法步驟如下：

Step1：隨機(jī)產(chǎn)生指定個(gè)體數(shù)目的3個(gè)初始種群作為并行算法的子種群;

Step2：若滿足停止準(zhǔn)則，輸出結(jié)果;否則，轉(zhuǎn)Step3;

step3：并行計(jì)算各子種群中個(gè)體的適應(yīng)度;

Step4：采用輪盤賭方式并行執(zhí)行各子算法的選擇算子;

Step5：按交叉概率并行執(zhí)行各子算法的交叉算子;

Step6：按變異概率并行執(zhí)行各子算法的變異算子;

Step7：若滿足遷移條件，執(zhí)行遷移算子，轉(zhuǎn)Step2，否則，轉(zhuǎn)Step2。

2.3算法流程圖

分布式并行遺傳算法流程如圖1所示：

3算例分析

3.1算例介紹

以16個(gè)客戶的HVRP問題為例，配送中心編號為0，客戶編號為1-16，節(jié)點(diǎn)信息見表1。車輛類型共有2種，其中，A型車2輛，限載量20t;B型車2輛，限載量10t。求車輛配送總里程最小的路徑選擇方案。

3.2算例求解

將車輛按限載量由小到大的順序依次編號為1-5。分別采用基本遺傳算法和分布式并行遺傳算法求解，并行算法子種群數(shù)目設(shè)置為3，各子種群的規(guī)模均為10，交叉概率0.8，變異概率0.1，遷移周期為5，遷移規(guī)模為3，算法終止準(zhǔn)則設(shè)置為迭代次數(shù)達(dá)到1000，所得最優(yōu)路徑結(jié)果如下：

路線1：0-8-6-2-5---0;用A型車;

路線2：0-7-1-4-3-0;用A型車;

路線3：0-9-10-16-14-0;用B型車;

路線4：0-12-11-15-13-0;用B型車。

最優(yōu)路徑如圖2所示：

3.3算法對比分析

傳統(tǒng)遺傳算法與分布式并行遺傳算法求解該HVRP問題的收斂圖3、圖4所示：

圖3與圖4比較后可知，MDPGA算法較SGA算法，收斂速度及魯棒性都得到了很大的提升，有效避免了早熟，尋優(yōu)能力增強(qiáng)，體現(xiàn)了MDPGA算法的優(yōu)越性。

4結(jié)論

對比分析基本遺傳算法（sGA）與分布式并行遺傳算法（MDPGA）的收斂性可知，SGA算法的收斂性明顯較差，在最優(yōu)解搜索過程中，易陷入局部最優(yōu)。MDPGA算法收斂速度較快，遷移算子使得算法全局搜索能力大幅提升。通過實(shí)例論證，分布式并行遺傳算法在求解HVRP問題時(shí)收斂速度更快，具有更好地尋優(yōu)能力，是一種更有效的算法。