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

王超 袁杰紅

摘要：傳統遺傳算法在求解HVRP問題時尋優效率不高，在搜索過程中易陷入局部最優，發生早熟。為解決上述問題，文章在傳統遺傳算法的基礎上，采用多個子算法并行分布、同時迭代的方式調整算法結構，并引入遷移算子實現迭代過程中各子算法間的信息共事，以提升尋優效率。

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

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

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

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

2.1算法介紹

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

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

2.2算法步驟

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

Step1：隨機產生指定個體數目的3個初始種群作為并行算法的子種群;

Step2：若滿足停止準則，輸出結果;否則，轉Step3;

step3：并行計算各子種群中個體的適應度;

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

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

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

Step7：若滿足遷移條件，執行遷移算子，轉Step2，否則，轉Step2。

2.3算法流程圖

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

3算例分析

3.1算例介紹

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

3.2算例求解

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

路線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型車。

最優路徑如圖2所示：

3.3算法對比分析

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

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

4結論

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