探究遺傳算法應用于物流的配送運輸

摘要：隨著社會經濟和網絡技術的不斷發展，社會物流業也呈快速發展的趨勢。在物流業中，物流配送是很重要的環節之一。本文以臨沂地區的物流業為背景，為了更好地解決物流配送路徑優化問題，建立了一種遺傳算法模型。實驗計算表明，通過用遺傳算法進行物流配送路徑優化，可以方便有效地得到問題的最優解或者近似最優解。

關鍵詞：遺傳算法 物流配送 優化 臨沂地區

1.引言

市場經濟的改革以及跨地區貿易的發展共同促進了物流業的快速發展。物流配送是指將客戶所購的貨物及時的送交客戶的過程，物流配送不僅是物流業最重要的環節之一，同時物流配送的效率也直接影響著整個工作流程的效率，因此，需要不斷地改進、優化物流配送路徑。本文的研究背景是山東的臨沂地區，臨沂市被確定為省級物流節點城市，將利用商貿市場集聚的優勢，以建設大物流促進商貿流通發展為目標，建立連接江蘇、輻射長江三角洲，連通日照、連云港的商貿物流基地，服務于省內外商貿流通和經濟建設。那么在這樣一個重要的物流節點城市，合理地選擇配送路徑具有重要的意義，不僅能偶縮短配送時間，也能降低配送成本，在提高服務質量和提高經濟效益方面都有較大貢獻。

優化配送路徑是一個NP-Hard問題，為了解決這一問題，近年來提出了不少算法，比如節約法、掃描法等，本文通過一系列的研究，將遺傳算法應用于物流配送的決策分析中。遺傳算法（Genetic Algorithms，GA）最早是由John.H.Holland于1975年提出的，它是一種結合了生物自然選擇和基因遺傳學的優化搜索方法。它的優點非常多，比如魯棒性強、速度快、搜索范圍廣等而廣泛應用于各個領域。本文針對物流配送路徑優化問題，首先分析了其數學模型，然后引入了遺傳算法來優化，最后進行了實驗計算，研究表明，將遺傳算法應用于物流配送路徑優化問題是行之有效的方法，取得較好的結果。

2.優化物流配送路徑的數學模型

物流配送的優化可以描述為：配送中心用多輛汽車向多個客戶送貨，其中汽車的載量確定，客戶的位置和需求量確定，通過優化，使得汽車所行駛的總路程最短，并且滿足以下條件：

（1）各路徑上的客戶的總需求量小于等于汽車載量；

（2）各路徑總長度小于等于汽車配送一次可行駛的最大長度；

（3）一條路徑由一輛汽車進行配送，且必須滿足個客戶需求。

通過對以上條件的分析，建立物流配送路徑的數學模型。首先規定以下公式中各字母的意義：K為配送中心擁有的汽車總量；[Qk]（k=1，2，…，K）為各汽車的載量；[Dh]為汽車進行一次配送所行駛的最大長度；L為客戶總數；[qi]為客戶i的需求量；[d0j]為客戶與配送中心的長度；[dij]為客戶i和客戶j之間的長度；[nk]為第k輛汽車負責的配送的客戶數，若此值為0，則表示此汽車未使用；[Rk]為集合，表示第k條路徑，其中[rki]表示客戶[rki]在路徑k中的順序為i，令[rk0]=0表示配送中心。經過分析，建立如下數學模型：

3.優化物流配送路徑的遺傳算法

3.1遺傳算法的基本思想

遺傳算法是一種很好的搜索優化方法，它的操作對象為種群的所有個體，個體與問題的解是一一對應的，其中選擇、交叉和變異是最主要的操作。它的流程圖如下：

圖1 遺傳算法流程圖

這種算法主要包括6個基本要素：

（1）編碼：通過編碼將空間的數據轉變為基因型串數據，在編碼前先進行量化。

（2）生成種群：通過隨機方法產生初始種群，每個個體對應問題的一個解。

（3）評估適應度：用來評估個體的優劣，評估結果作為遺傳操作的依據。

（4）選擇：通過“適者生存”的選擇方法，從當前種群中選取適應度高的個體組成新的種群，適應度越高，被選擇幾率越大，但不能保證一定被選擇。

（5）交叉：將選出的個體存入配對庫，進行隨機配對，產生新的個體。

（6）變異：引入變異是為了解決在交叉過程中引起的信息遺失現象，按概率改變染色體基因位。

3.2優化配送路徑的遺傳算法構造

（1）編碼方法。在本文中，配送中心用0表示，客戶用1表示（L個1表示有L個不同客戶）。每條配送路徑的起點和終點都是配送中心，配送路徑的最大值由配送中心的汽車總數K決定，這樣，L個1或者K—1個0隨機排列成一條染色體，則對應一種配送路徑方案。

（2）初始種群的產生。由1和0構成的序列稱為一條染色體，那么由多條不同的染色體構成初始種群。

（3）適應度評估。在評價一種配送方案的優劣時，既要判斷是否能夠滿足約束條件，又要計算它的目標函數值。因此，在進行評估時，首先判斷各配送路徑方案是否滿足約束條件，如果不滿足，則該路徑為不可行的路徑，然后計算目標函數值。適應度[Fi]的計算公式如下所示：

[Fi=1Zi+MiG]

其中，[Zi]為目標函數值，[Mi]為染色體i所對應的不可行路徑數，G為權重因子，為值較大的正數。

（4）選擇操作。在本文中，綜合使用最優個體保留策略和輪盤賭法，首先，將所有染色體按照適應度小進行排序，對于適應度最高的染色體，則直接進行復制；然后采用輪盤賭法，使剩余的染色體產生下一代的N-1條染色體。每條染色體被選中的概率為它本身的適應度與種群中所有染色體的適應度之和的比值。

（5）交叉操作。交叉操作主要是按照交叉概率將除了第一條染色體外的其他染色體進行交叉配對，本文采用兩點交叉法。

（6）變異操作。本文所采用的變異操作是為了保證一旦某基因片段需要發生變異，那么另一片段也要發生變異，這個片段是隨機產生的。

4.實驗與計算

在本實驗中，采用C語言編程，以2輛汽車為5個客戶配送為例，其中汽車載量為8000千克，一次配送最大行駛長度為40千米，配送中心與客戶以及客戶與客戶之間的長度由下表表示（單位千米）：

5.小結

通過本文的理論分析與實驗證明，將遺傳算法應用于物流配送路徑優化方案中是可行的。本文首先分析了物流配送路徑的數學模型，然后簡介了遺傳算法的原理，并進一步將遺傳算法應用于物流配送路徑中，最后通過實驗計算，證明用遺傳算法能夠得到快速的得到物流配送路徑的最優解，是提高配送效率有效的方法。

參考文獻：

[1]王輝.基于改進遺傳算法的物流配送路徑優化研究[D].山東科技大學，2010，5

[2]黃曉濱，鄒書蓉，張洪偉.改進的遺傳算法及在物流配送路徑優化中的應用[J].西南民族大學學報（自然科學版）.2008（4）

[3]易榮貴，羅大庸.基于遺傳算法的物流配送路徑優化問題研究[J].計算機技術與發展.2008（6）

[4]郭淑紅，楊曉慧.遺傳算法在物流配送路徑優化問題中的應用[J].硅谷.2009（1）

作者簡介：

殷俊峰（1978- ），男，山東費縣人，漢，臨沂大學講師，山東大學碩士研究生，主要研究方向：統計學，運籌學，計量經濟學的應用問題、時間序列分析等。