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

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

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

1 問題描述與算法設(shè)計

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

表1 蔬菜應(yīng)急配送分析表

2 RSG-遺傳算法設(shè)計

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

RSG流程圖如下圖1所示：

圖1 RSG流程圖

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

步驟如下：

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

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

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

（4）根據(jù)終止條件判斷是否停止計算，如滿足條件，停止計算，輸出最優(yōu)解，否則轉(zhuǎn)（3）。

3 優(yōu)化結(jié)果分析

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

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

4 結(jié) 論

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

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

表2 采用RSG-遺傳算法得到的優(yōu)化配送路線表

圖2 采用RSG-遺傳算法與傳統(tǒng)遺傳算法的收斂過程對比

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

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