[發明專利]遺傳算法與MapReduce相結合的車輛調度方法

有效

• 申請號: 201310387759.5
• 申請日: 2013-08-31
• 公開（公告）號: CN103440522A
• 公開（公告）日: 2013-12-11
• 發明（設計）人: 鄭湘涵;陳國龍;陳李瑩
• 申請（專利權）人: 福州大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/06
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

技術領域

本發明涉及物流車輛調度技術領域，特別是一種遺傳算法與MapReduce相結合的車輛調度方法。

背景技術

車輛路徑問題（Vehicle?Routing?Problems，VRP）是交通運輸、物流配送的核心問題，目的在于設計一套車輛行駛的路線，實現以最小的成本滿足各個客戶的配送要求。帶載重約束的車輛路徑問題（Capacitated?Vehicle?Routing?Problems，CVRP）是指從配送中心用多輛車向多個需求點(用戶)送貨，每個需求點的位置和需求量一定，每輛車的載重量一定，要求合理安排車輛路線，達到一定的目標（如路程最短、費用最少、時間盡量少、使用車輛數盡量少等），并滿足以下條件：每條配送路徑上需求點的需求量之和不超過車輛載重量；每條路徑的長度不超過車輛一次配送的最大行駛距離；每個需求點必須且只能由一輛車送貨。

綜合過去的求解算法，可以分為精確算法與啟發式算法。精確算法在解決較大規模的車輛路徑問題時相對費力且難以實現。啟發式算法是求解問題的主要方法，可以分為簡單啟發式算法、兩階段啟發式算法、人工智能方法。遺傳算法和蟻群算法都屬于人工智能方法，且相比其他人工智能方法，二者只需要極少的初始化信息。但是，當問題規模較大時，采用傳統的遺傳算法或蟻群算法求解問題的速度會呈指數下降。

發明內容

本發明的目的在于克服現有技術的不足，提供一種遺傳算法與MapReduce相結合的車輛調度方法，該方法運行速度快，易于實現，使用效果好。

為實現上述目的，本發明的技術方案是：一種遺傳算法與MapReduce相結合的車輛調度方法，對于采用m輛車配送n個客戶點的問題，基于云計算中的MapReduce模型和遺傳算法，按如下步驟進行車輛調度：

（1）初始化種群：采用自然數{1,2,…,n}對n個客戶點進行對應編碼，并隨機編成一條長度為n、自然數{1,2,…,n}前后順序隨機排列的染色體個體，然后根據載重約束在染色體個體中插入分隔符，所述載重約束為分隔符之間的所有編碼對應的客戶點的配送量之和不大于車輛載重量；設種群規模為P，則通過上述方法隨機產生P個染色體個體，即形成規模為P的初始種群；

（2）計算個體適應度：利用根據適應度函數構造的多個Map函數，并行計算P個染色體個體的個體適應度，并將結果輸出給Reduce函數；

（3）進行選擇、雜交、變異操作：利用根據選擇、雜交、變異算法構造的Reduce函數，將Map函數的輸出作為Reduce函數的輸入，利用Reduce函數將父代染色體中適應度較高的個體選擇出來產生子代染色體，然后以一雜交概率隨機選擇子代染色體中一部分進行雜交操作并將雜交后染色體個體添加到新種群中，以一變異概率隨機選擇子代染色體中另一部分進行變異操作并將變異后染色體個體添加到新種群中，子代染色體中的剩余部分直接復制到新種群中，從而形成新種群并輸出；

（4）判斷算法是否達到設定的最大遺傳代數，是則選出適應度最高的染色體個體所對應的路徑集合作為問題的最優解，否則返回步驟（2）。

步驟（3）中，Reduce函數采用輪盤賭算法進行選擇操作：計算P個染色體個體的相對適應度，以之作為概率，并按概率大小將[0,1]空間劃分成P份，然后再生成一個[0,1]范圍內的隨機數，落在哪個區域則選擇對應的染色體個體；按上述方法重復P次，產生P個染色體個體，得到子代染色體。

步驟（3）中，Reduce函數按如下方法進行雜交操作：隨機在一對染色體個體A、B中選擇一個交配區域，將個體B的交配區域加到個體A的前面，個體A的交配區域加到個體B的前面，然后分別刪除原個體中與交配區域相同的自然數并根據載重約束重新在染色體個體中插入分隔符，得到一對雜交后染色體個體C、D。

步驟（3）中，Reduce函數按如下方法進行變異操作：隨機在染色體產生兩個基因位，將所述兩個基因位上的自然數進行互換，然后根據載重約束重新在染色體個體中插入分隔符，得到變異后染色體個體。

相較于現有技術，本發明的有益效果是在物流車輛調度問題中引入了基于云計算中的MapReduce模型和遺傳算法，將算法并行化，不僅運行速度快，而且MapReduce模型不同于MPI并行計算，MapReduce中如何分布處理對用戶是透明的，因此無需底層知識，易于實現，且提供了良好的節點失效時備份處理容錯機制，具有很強的實用性和廣闊的應用前景。

附圖說明

圖1是本發明實施例的實現流程圖。

具體實施方式