分布式并行遺傳算法求解多車型車輛路徑問題

王超 袁杰紅

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

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

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

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

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

2.1算法介紹

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

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

2.2算法步驟

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

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

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

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

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

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

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

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

2.3算法流程圖

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

3算例分析

3.1算例介紹

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

3.2算例求解

將車輛按限載量由小到大的順序依次編號為1-5。分別采用基本遺傳算法和分布式并行遺傳算法求解，并行算法子種群數(shù)目設(shè)置為3，各子種群的規(guī)模均為10，交叉概率0.8，變異概率0.1，遷移周期為5，遷移規(guī)模為3，算法終止準則設(shè)置為迭代次數(shù)達到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)能力增強，體現(xiàn)了MDPGA算法的優(yōu)越性。

4結(jié)論

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