配送中心車輛調(diào)度模型及遺傳算法設(shè)計

摘要：針對物流配送中心車輛調(diào)度問題，采用混合整數(shù)規(guī)劃方法進(jìn)行建模。對實際問題進(jìn)行研究分析后，基于所研究問題的特點，提出基于遺傳算法的求解方法。通過數(shù)值實驗對算法不同參數(shù)組合進(jìn)行分析、比較，獲得最佳參數(shù)組合，建立了有效的求解該問題的遺傳算法。并通過對實際問題的數(shù)值仿真試驗，驗證了算法的有效性。

關(guān)鍵詞：配送中心；車輛調(diào)度；優(yōu)化；遺傳算法

中圖分類號：F224文獻(xiàn)標(biāo)識碼：A

文章編號：1002-3100(2008)05-0079-04

Abstract: This paper considers the vehicle scheduling problem in distribution center， and using the method of mixed integer programming to build the mathematical model. By analyzing the characteristics of the problem， a genetic algorithm is presented. Secondly， computational experiments are given to select the optimal parameters of the algorithm， and then optimal genetic algorithm is determined. Finally， computational tests are further given to show the efficiency of the algorithm.

Key words: distribution center; vehicle scheduling; optimization; genetic algorithm

越庫配送是將貨物在進(jìn)貨口卸下，經(jīng)過簡單分揀等操作后直接裝到等候在出貨口的車輛上運送給零售商，在不增加庫存的同時降低了運輸費用和運輸時間。其優(yōu)勢在于：（1）對較大、較穩(wěn)定的需求，并不需要每次都采取訂購模式來運作，越庫配送可使供應(yīng)鏈各環(huán)節(jié)減少庫存；（2）對穩(wěn)定而小批量的需求，采用越庫技術(shù)來代替零擔(dān)運輸（Less-than-truckload）可大大降低運輸成本；（3）節(jié)省了昂貴的庫存費用；（4）順應(yīng)了商品本身對時間上的要求，例如快遞、保鮮食品等。越庫技術(shù)已成功地應(yīng)用于沃爾瑪（Wal-Mart），Home Depot，Costco，Canadian Tire以及FedEx等著名企業(yè)。

在越庫配送中，為了實現(xiàn)準(zhǔn)時制配送，降低庫存，必須對車輛調(diào)度進(jìn)行深入研究，國內(nèi)外許多學(xué)者均致力于此方面的研究。文獻(xiàn)[1]針對美國郵電局郵件優(yōu)先投遞傳送系統(tǒng)的卡車運輸網(wǎng)絡(luò)進(jìn)行了設(shè)計，利用整數(shù)規(guī)劃松弛法解決大規(guī)模系統(tǒng)的物流配送網(wǎng)絡(luò)，為解決類似模型提供了依據(jù)。陳火根[2]等人針對在已知配送中心位置、客戶點位置及道路情況下，對m輛車n個客戶點，確定車輛分配（每輛車負(fù)責(zé)的客戶點）及每輛車的行車路線，所采用的方法為遺傳算法。林方明[3]等人研究了運輸網(wǎng)絡(luò)優(yōu)化問題在物流配送決策中的作用，并探討了物流企業(yè)應(yīng)如何設(shè)計運輸網(wǎng)絡(luò)，提出運輸網(wǎng)絡(luò)優(yōu)化的方法，以降低供應(yīng)鏈成本，提高客戶響應(yīng)度。本文作者[4]針對越庫作業(yè)調(diào)度問題提出兩階段越庫作業(yè)調(diào)度模型，并給出了求解該類問題的動態(tài)規(guī)劃算法。本文則是基于遺傳算法來設(shè)計與上述問題不同的越庫配送中心車輛運輸網(wǎng)絡(luò)。

1問題描述

本文所研究的問題為越庫配送中心車輛運輸網(wǎng)絡(luò)的設(shè)計，在配送中心內(nèi)部某些客戶需要的貨物較多且可以直接從供貨商或上級分銷商處運走，而無需經(jīng)過配送中心的整合運輸，因此主要考慮車輛是否直接從出發(fā)點或通過配送中心將貨物運輸至目的地，以及每條運輸線路上車輛的分配。例如，在連鎖超市行業(yè)中，門店的貨物主要通過配送中心集中進(jìn)貨與供貨，在降低門店庫存的同時，必須保證門店貨物供應(yīng)的及時性，以提高顧客滿意度。因此，必須對配送中心的配貨車輛及線路進(jìn)行設(shè)計，從而保證貨物及時、準(zhǔn)確的到達(dá)指定地點，降低運輸成本。為了更好地研究配送中心車輛調(diào)度問題，我們通過建立模型實現(xiàn)配送中心的車輛調(diào)度，確定各條線路上需要的車輛數(shù)（起點到終點、起點到配送中心）以及車輛線路安排。

圖1描述了該模型的運輸網(wǎng)絡(luò)，由圖可知：起點到終點的運輸方式，可以是直接運輸，也可通過配送中心整合后運輸?shù)浇K點。評價運輸方式好壞的指標(biāo)是運輸成本。其數(shù)學(xué)模型如下：

2遺傳算法的建立與求解

求解車輛調(diào)度問題的方法很多，常用的有旅行商法、動態(tài)規(guī)劃法、分支定界法、方案評價法等。遺傳算法的出現(xiàn)為求解物流配送問題及車輛優(yōu)化問題提供了新的工具。許多學(xué)者利用遺傳算法求解該類問題[5-7]。基于所研究問題的復(fù)雜性及問題的特點，本文亦采用遺傳算法進(jìn)行求解，下面針對算法具體參數(shù)進(jìn)行研究與分析。

2.1適應(yīng)度函數(shù)。針對本文研究的模型，不能直接簡單地將個體解碼后直接代入目標(biāo)函數(shù)中計算目標(biāo)函數(shù)值，從而衡量個體的適應(yīng)度。因為對于具有實際意義的模型，各個變量均有嚴(yán)格的約束條件，而個體在進(jìn)化過程中，無法保證一直滿足約束。因此，即使得到的目標(biāo)函數(shù)值很小，但只要不滿足約束條件，該個體依然屬于“劣質(zhì)”個體。為此，需要對約束條件進(jìn)行處理，使對個體好壞的評價更加符合實際情況。

2.2采用修改可行解的方法消除約束條件。很多研究表明：懲罰函數(shù)法消除模型約束條件在運輸問題中并不是非常有效，其主要原因是在約束條件非常多，且約束嚴(yán)格的條件下，個體通過交叉變異很難找到可行解，因此很難找到一種合理的懲罰函數(shù)，使選擇算子盡量地選擇可行解，同時不破壞群體的多樣性。DNA技術(shù)發(fā)展提示我們：依據(jù)醫(yī)學(xué)技術(shù)，對遺傳因子進(jìn)行人為修改，使它具有我們想要的特征[8]。基于這種啟發(fā)，設(shè)想對于本文所研究物流模型的遺傳算法，作如下變換：在由個體基因型解碼后，計算個體適應(yīng)度前，增加處理個體表現(xiàn)型的過程，使其滿足模型的約束條件。通過采用修改可行解的方法消除上述困難，且改進(jìn)后的算法在較短時間內(nèi)即可獲得滿意解。同時，修改可行解的方法也在很大限度上減少了解空間的編碼長度。其具體做法如下：模型初始的解空間為X

初始群體的生成。針對該模型特點，提出了初始群體的生成方法（把它命名為確定式隨機(jī)生成）：假設(shè)群體大小為M，個體順序按照0，1，…，n，…，M的順序，分別在0+i*j*n/4M，i*j*3/4+i*j*n/M范圍內(nèi)的代碼設(shè)置盡可能出現(xiàn)1，其它前i*j的代碼為0。但這樣，無疑在i*j/4，i*j*3/4范圍內(nèi)1的出現(xiàn)的頻次遠(yuǎn)大于其它位置，然后，隨機(jī)將該值改成0。這樣，每個位置的“0”和“1”出現(xiàn)的概率都一致，但不同的個體，“0”和“1”在不同的位置上，出現(xiàn)的概率不同。對于長度很大的代碼，可以盡可能的增加個體差異性，增大交叉算子的效果。

2.4遺傳操作。遺傳操作包括三個基本遺傳算子：選擇、交叉和變異。基于所研究模型的特點，選擇算子采用確定式采樣選擇：由于算法的適應(yīng)度就是模型目標(biāo)函數(shù)的值，雖然不同的配送方案目標(biāo)函數(shù)的差異很大，但輪盤算法依然很難保證選擇盡量多的個體。而確定式采樣選擇可保證選擇盡量多的個體，同時改進(jìn)了選擇算子，以保證遺傳群體的多樣性。交叉算子選擇多點交叉：由于個體編碼長度非常長，因此可采用多點交叉，以保證編碼充分的交叉，增加全局搜索的能力。同時，基于編碼的特點：前i*j個代碼為直接運輸?shù)臎Q策變量，它們對模型的影響要遠(yuǎn)遠(yuǎn)大于后面的其他代碼。而后面的代碼可能由于前面代碼的變化而做出相應(yīng)的修改。因此變異算子也要做出相應(yīng)的修改。

在遺傳算法前期，為了增加算法的全局搜索能力，對前i*j個代碼進(jìn)行變異，而前i*j個代碼每個代碼表示一個基因表現(xiàn)型，所以變異算子步驟如下：（1）隨機(jī)產(chǎn)生一個變異概率pr，決定一個群體中變異的個體數(shù)量。（pr*M為整數(shù)）；（2）隨機(jī)產(chǎn)生pr*M個0，M的整數(shù)，確定變異的個體；（3）對每個個體產(chǎn)生pm*i*j個0，pm*i*j的整數(shù)，確定每個個體的變異基因的個數(shù)和位置，并對其取反。

遺傳算法后期，主要增加的是算法的局部搜索能力，所以變異的主要基因作為i*j個代碼后面的代碼，方法和上面的一致。

3數(shù)值試驗

為了驗證算法的有效性，下面用實例來比較。實例如下：在某連鎖零售超市企業(yè)，其配送中心負(fù)責(zé)7個門店的貨物供應(yīng)，同時，所需貨物須向7個供應(yīng)商訂貨。根據(jù)其某一時期的需求量和各線路的運輸費用，通過算法獲得車輛的最佳調(diào)度模型。每輛卡車的載貨量為20，需求情況和運輸路費情況如下所示：

對于整數(shù)規(guī)劃問題可用Lindo軟件，因此下面就用該軟件求解此模型。同時將門店和供應(yīng)商數(shù)量增加為8個和9個，進(jìn)行比較。得到了如下結(jié)果：

采用遺傳算法求解時算法參數(shù)如下：二進(jìn)制編碼、隨機(jī)生成初始群體、確定式采樣選擇算子、群體大小為200、遺傳代數(shù)500、交叉概率0.8、交叉點個數(shù)5、變異個體個數(shù)概率0.05，變異點概率0.03、遺傳90％代后改變變異算子。通過算法計算得到了如下的結(jié)果：（同樣通過10次計算，得到10組滿意解的鈞值、方差，以此與Lindo計算情況作對比）

算法得到的滿意解與最優(yōu)解的誤差分別為0.78%、0.22%、-2.6%。其中-2.6%，其原因為Lindo所用分支定界法無法求得最優(yōu)值，程序內(nèi)存溢出前各分支的最小值。由結(jié)果分析可知：對于小規(guī)模越庫配送系統(tǒng)，此算法可以在很短的時間內(nèi)得到滿意的結(jié)果。而當(dāng)供需商達(dá)到各9個時，算法在30秒內(nèi)計算得到的滿意解，比Lindo計算的滿意解更接近最優(yōu)值，且計算時間縮短了近十倍。測試結(jié)果充分表明該算法的有效性和快速性。

對于大規(guī)模配送系統(tǒng)，可行解比小規(guī)模配送系統(tǒng)更具有多樣化。可能無法如同小規(guī)模配送系統(tǒng)案例那樣，在算法遺傳500代就得到足夠滿意的解。對于超過50個供應(yīng)商、50個門店，以及3個越庫配送中心的案例，也可以在30分種內(nèi)完成500代的算法計算。由遺傳算法的原理可知，遺傳代數(shù)和計算時間之間為線性關(guān)系，可以通過在可行的時間內(nèi)，通過增大遺傳代數(shù)的方法得到足夠滿意的解。

4結(jié)束語

本文研究了越庫配送網(wǎng)絡(luò)系統(tǒng)中車輛調(diào)度問題，在給出問題的數(shù)學(xué)描述后，提出了求解該問題的遺傳算法。算法特點為：（1）采用修改可行解的方法消除約束條件；（2）在算法后期改變變異算子的變異方法。

另外，本文的研究主要針對配送中心網(wǎng)絡(luò)，通過研究運輸車輛調(diào)度問題來減少網(wǎng)絡(luò)中的運輸費用。通過數(shù)值實驗，還可以看到配送系統(tǒng)合理設(shè)計取得的經(jīng)濟(jì)效益。對于一個較小規(guī)模的7個供應(yīng)商、7個門店、1個配送中心的案例，如果不經(jīng)過配送中心的配送，而是直接運輸，得到的運輸費用為654。而通過配送中心配送的最佳運輸方式的費用為382。這種規(guī)模經(jīng)濟(jì)效應(yīng)還會隨著配送網(wǎng)絡(luò)系統(tǒng)規(guī)模的增大而增大。由此可知物流配送技術(shù)的前景，同時說明了研究物流配送技術(shù)的重大意義。

參考文獻(xiàn)：

[1] Harvey Donaldson， Ellis L. Johnson， H. Donald Ratliff， Mei Zhang， Schedule-Driven Cross-Docking Networks[R]. Technical report. The Logistics Institute， Georgia Institute of Technology， Atlanta， GA. 2003.

[2] 陳火根，丁紅鋼，程耀東. 物流配送中心車輛調(diào)度模型與遺傳算法設(shè)計[J]. 浙江大學(xué)學(xué)報：工學(xué)版，2003(5):512-516.

[3] 林方明，馬建軍，龐淵. 物流配送決策中的運輸網(wǎng)絡(luò)優(yōu)化問題研究[J]. 山西建筑，2004(8):84-85.

[4] 馬東彥，陳峰. 以總加權(quán)完工時間和為目標(biāo)的約庫作業(yè)調(diào)度問題及其動態(tài)規(guī)劃算法研究[J]. 上海交通大學(xué)學(xué)報：自然科學(xué)版，2007(5):852-857.

[5] 孫福春，寧檳. 遺傳算法在車輛調(diào)度問題中的應(yīng)用[J]. 交通與計算機(jī)，2005(2):21-23.

[6] 李軍，謝秉磊，郭耀煌. 非滿載車輛調(diào)度問題的遺傳算法[J]. 系統(tǒng)工程理論方法應(yīng)用，2000(3):35-40.

[7] 王惠，陳燕. 基于遺傳算法的多目標(biāo)的有時間窗的車輛調(diào)度[J]. 計算機(jī)應(yīng)用，2004(9):144-147.

[8] 陳曦，林濤，唐賢瑛. 遺傳算法的參數(shù)設(shè)計與性能研究[J]. 計算機(jī)工程與設(shè)計，2004，25(8):1309-1310，1319.

[9] 姚城. 物流配送中心規(guī)劃與運作管理[M]. 廣東：廣東經(jīng)濟(jì)出版社，2004.

[10] 周明. 遺傳算法原理及應(yīng)用[M]. 北京：國防工業(yè)出版社，1999.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。