基于混合遺傳算法對應急條件下蔬菜配送問題的研究

高 特，李 莉，鐘 蓮，紅德孜·再努拉（新疆農業大學 機械交通學院，新疆 烏魯木齊 830052）

我國每年的蔬菜產量很高，并且呈逐年遞增的趨勢。同時也是一個蔬菜需求量巨大的國家，隨著居民生活水平的提高，人們對蔬菜的要求已經從曾經的數量型轉變為質量型。但在追求蔬菜質量的同時，物價的飛漲也增加了百姓的生活壓力。為此，相關部門也加快步伐，通過采取各種措施來抑制蔬菜價格的上漲。以烏魯木齊市為例，政府通過搭建社區蔬菜副食品直銷店（簡稱：社區菜店）的方式來管控蔬菜的質量和價格，以此來解決老百姓買菜難、買菜貴的問題。

在對社區菜店規劃配送路線時，一般會抽象成車輛路徑問題來考慮。在解決車輛路徑問題時，選用合理有效的算法是非常關鍵的。林國璽（2006）[1]采用混合智能算法來解決現實中的CVRPTW的問題，提出將模擬退火算法中的Metropolis接受準則引入到遺傳算法的群體更新策略中，并將其應用于物流管理中的帶容量約束和時間窗的車輛路徑問題（CVRPTW）。郎茂才等（2009）[2]在配送車輛優化調度模型與算法中討論了多車場多目標的配送問題。張靜等（2013）[3]在對物流配送路徑優化問題中使用遺傳算法進行研究。

1 問題描述與算法設計

以烏市社區菜店為例，指定某家配送中心負責周邊區域的65家社區菜店的蔬菜配送工作，該配送中心擁有載重量為2t的貨車10輛，1t的貨車4輛。每家社區菜店都有配送時間的要求，時間窗限制閥值最小為2小時，需要配送車輛進行非滿載蔬菜配送運輸。在某些情況（如：訂單遺漏某些菜品、訂單打印時出現錯誤、工作人員在清點菜品時出現失誤、突發狀況導致暫存蔬菜損壞無法出售等）發生的時候，為了維持每日居民對蔬菜的需求量，就需要實施應急蔬菜的配送工作。在這里提出應急配送指數（α代表該種菜品的需求指數，c1代表該種菜品的單位利潤，m代表該種菜品的需求量，s代表運輸菜品所走的路程長度，c2代表單位運輸成本，c3代表單位距離車輛磨損費）來判斷是否需要實施配送服務，同時還要考慮配送中心是否有額外的車輛可以安排配送。對于n家菜店都需要應急配送的情況下，用sn=s/n來代替應急配送指數公式中的s；若sn＞s則不必替換，實施點對點運輸。

表1 蔬菜應急配送分析表

2 RSG-遺傳算法設計

RSG-遺傳算法是一種結合改進掃描法思想的混合遺傳算法。算法的整體設計分為RSG（Radar Scan Grouping）掃描部分和遺傳尋優兩個部分。對于RSG掃描的設計，其基本思想是由中心點（配送中心）開始向任意方向劃一條射線（掃描線），沿順時針或逆時針的方向旋轉該掃描線與任意貨物需求點相交。如果需要在某分組里增加該需求點，則反饋該點，并累計貨運量，計算是否會超過安排車輛的運載能力，若無則繼續旋轉掃描線，直到與下一個貨物需求點相交；再次累計貨運量，計算安排運輸車輛的已裝載程度。如果超過車輛的運輸能力，便不考慮最后的貨物需求點，或按照其他設定的終止條件，直到達到車輛最大運載能力為止，該分組確定。隨后沿著掃描線的方向，從不包含在上一組的貨物需求點開始，繼續旋轉掃描線以尋找新的貨物需求點，繼續該過程直到所有的貨物需求點都被合理的劃分成組。

RSG流程圖如下圖1所示：

圖1 RSG流程圖

對遺傳尋優部分的設計采用RSG的結果來劃定遺傳種群。然后通過隨機生成的方法產生初始種群、使用輪賭盤復制法保留染色體并進行復制和最優保留順序交叉算子進行染色體交叉的基礎上，采用反轉變異算子進行變異操作，加速有效收斂，然后根據終止條件——染色體連續最佳保持到β代得到問題的最優解。

步驟如下：

（1）初始數據輸入。根據改進掃描法的分組結果，將初始數據例如起點坐標、終點坐標、配送車輛載重量、社區菜店坐標、各家菜店的需求量、需求時間和遺傳控制參數輸入程序中；

（2）初始化運輸距離數組，并初始化染色體；

（3）進行選擇、交叉、變異操作；

（4）根據終止條件判斷是否停止計算，如滿足條件，停止計算，輸出最優解，否則轉（3）。

3 優化結果分析

在表2中，采用RSG-遺傳算法得到了優化后的配送線路。A代表配送中心，數字編號表示各家菜店。根據車輛需要行駛的路線長度和平均行駛速度（50km/h），可知每組運輸車輛都可以在1.5h內完成蔬菜的配送工作，并返回配送中心，滿足時間窗的最小閥值。同時，優化算法中使用的載重量為2t的汽車10輛，1t的汽車2輛，沒有超出配送中心的實際配送能力。因此，程序運行的實驗結果合理有效。

從圖2可以看出，采用RSG-遺傳算法在收斂速度上有顯著的提升，在較短時間內收斂到最優值，減少了遺傳算法的計算時間。

4 結 論

通過實例驗證RSG-遺傳算法可以有效地控制種群規模，提取出優質的遺傳種群，有效降低了發生局部最優解的概率，相比傳統的遺傳算法更加高效。雖然應急配送出現的概率很小，但是從理論研究的角度把它提出來，期望對其他相關問題的研究有一定的參考價值。

[1]林國璽，宣慧玉.混合智能算法在CVRPTW中的應用[J].工業工程，2006(1):107-111.

表2 采用RSG-遺傳算法得到的優化配送路線表

圖2 采用RSG-遺傳算法與傳統遺傳算法的收斂過程對比

[2]郎茂祥.基于遺傳算法的物流配送路徑優化問題研究[J].中國公路學報，2002(3):76-79.

[3]張靜，衛文學，劉倩.基于遺傳算法的物流配送路徑優化算法[J].中國科技信息，2013(1):98-99.