基于混合遺傳算法對(duì)應(yīng)急條件下蔬菜配送問(wèn)題的研究

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

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

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

1 問(wèn)題描述與算法設(shè)計(jì)

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

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

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

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

RSG流程圖如下圖1所示：

圖1 RSG流程圖

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

步驟如下：

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

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

（3）進(jìn)行選擇、交叉、變異操作；

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

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

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

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

4 結(jié) 論

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

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

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

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

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

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