基于遺傳算法的鮮奶冷鏈物流配送路徑優化

張培 武忠

摘 要：隨著物流領域的不斷發展，越來越多的方法可用于解決VRP問題，其中，啟發式人工智能算法更是得到了巨大的發展。筆者首先對背景公司的配送現狀進行了簡要分析，然后分別用節約法和遺傳算法對實例進行優化求解并得出結果，其中遺傳算法的求解過程是借助Matlab軟件實現的。最后，將兩種方法求得的結果進行綜合比較，發現在同樣的條件下，遺傳算法能夠更好地實現對配送路徑的優化。

關鍵詞：車輛路徑優化;節約法;遺傳算法

中圖分類號：F252 ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? 文章編號：1008-4428（2018）03-15 ?-03

一、引言

車輛路徑優化問題（Vehicle Routing Problem），簡稱VRP問題，指的是已知配送中心的位置和客戶需求點的位置、需求量，并且已知配送中心所擁有的一定數量的配送車輛的載貨量和容量，在滿足一定的約束條件前提下，以特定的優化指標（距離最短、時間最短等）為目標，合理安排車輛的配送方案。文章以一鳴真鮮奶吧為背景，對其在杭州市江干區的一鳴真鮮奶吧的配送路徑進行優化。

一鳴真鮮奶吧隸屬于浙江一鳴食品股份有限公司。浙江一鳴食品股份有限公司主要生產經營與乳制品有關的產品，其打造的泰順高山牧場的奶源保證了產品的質量。目前，溫州地區80%的奶源都由一鳴供應，為了提升奶源的質量，一鳴創建了全方位的牧業管理體系，集牧草種植、牧場管理、乳牛飼養、飼料加工等為一體，并且率先實行了“公司+農戶”的生產方法，利用當地勞動力來維持牧場的日常生產，在節省勞動力的同時也帶動了當地經濟的發展。其采用招商加盟模式運營的一鳴真鮮奶吧由于新鮮的奶源、獨特的產品而廣受歡迎，店鋪已經多達五百多家，利潤頗豐。

二、配送存在的問題

（一）車輛路線選擇的經驗操作性較強

公司的物流長途上主要依賴與其他物流配送公司的合作，而短途配送則是雇有專門的司機，對司機的專業知識水平要求較低，司機每天配送一次，每個司機固定地負責一個區域，由于對時間沒有硬性要求，因此他們并不會也無法對配送線路問題進行系統的研究和優化，因此經驗操作的成分較高。司機通常會根據自己的經驗選擇配送路徑，他們往往會因為順路或者距離近而將兩家或多家門店歸為同一條線路。這種安排的方式常常會由于城市復雜的交通狀況而對配送產生較大的不確定性，因此這種方式就配送而言不夠科學，甚至經常會出現重疊運輸的現象。

（二）對時間約束認識不足

專人負責專區，不存在業務競爭，也沒有嚴格的獎懲制度，只要求上午送到，沒有具體的時間約束，就導致司機對工作沒有緊張感。另外，車輛由配送中心安排，司機只負責運輸，對冷藏車輛的消耗認識不夠深刻，缺乏主人翁意識，所以他們通常采用隨遇而安的態度對待配送，對不必要的時間和成本消耗視而不見，對時間約束認識不足。

三、公司實際問題描述

該公司共有500多家鮮奶吧，為了便于研究，本文選取了該公司在杭州市余杭區的鮮奶吧進行研究，共9家一鳴真鮮奶吧。為了保證奶制品的質量，契合其經營理念，該公司所有的乳制品都是采用當天配送當天銷售的方式，每天鮮奶從生產地溫州裝車配送，而該公司在杭州地區沒有配送中心或中轉站，所以鮮奶一般是直接運送到門店。據了解，由于門店需求有限以及牛奶體積較小，杭州市江干區的部分鮮奶吧和余杭區的鮮奶吧由同一輛車配送，司機通常是配送完江干區的再去余杭區進行配送，江干區最后配送的鮮奶吧是計量店，所以將其假定為配送中心，并且假定配送完余杭區的門店之后車輛最后回到配送中心。由于給江干區的門店配送完后是九點，所以給余杭區的門店配送是在九點之后，避開了擁堵高峰期，所以假設道路通暢。配送中心要選擇最短路徑完成其所有的送貨任務。

為了方便求解，為余杭區的9家鮮奶吧進行編號排序（見表1），各個門店之間的距離見表2。

四、節約法求解

（一）根據表2作各點之間的最短距離表（見表3）：

（二）根據表3，利用節約法的基本原理計算出若合并巡回路線，各需求門店之間的可以節約的里程數，作節約里程表（見表4）：

（三）將表4中的節約的路程總數按由大到小的順序排序，然后作出節約里程排序表（見表5），從而盡量滿足總的節約里程數最多的目的。

（四）根據表5，整理得到實例最終的配送路線為：0-7-8-

6-5-4-3-2-9-1-0，該路線的總路程為：11.5+36.7+8.7+1.4+1.5+

1+27.8+13.8+28+7.7=138.1（km）。

五、遺傳算法求解

（一）遺傳算法結構

先把需要求解的實際問題具體表述成對目標函數的尋優問題，這樣需要優化的目標函數就是種群對自然的適應能力，個體的生物種群對應于優化變量，然后從當前的種群出發，復制、交叉、變異和選擇產生新一代種群，這個過程是重復的，直到達到進化時間的要求或者找到符合要求的種群，這就是遺傳算法優化求解問題的基本思路。其操作過程如下：

1.初始化數值：進化代數的初始值設為t=0，同時確定最大迭代次數T的值，初始種群P（0）隨機生成，其中有N個個體。

2.評價個體：由適應度函數的表達式求出每一代種群P（t）中所有個體的適應度。

3.選擇操作：根據對種群中個體的適應度的評估，把選擇算子作用到種群上。選擇運算有兩個目標，直接且優秀的個體遺傳至子代，或者是遺傳由交叉或配對產生的新個體。

4.交叉操作：把交叉算子作用到種群上，這是最核心的算子。

5.變異操作：把變異算子作用到種群上，這是在更改種群中個體串的某一些基因座上的基因值。

6.產生下一代：下一代種群P（t+1）將由種群P（t）經過選擇、交叉、變異操作產生。

7.判斷終止條件：當t=T時，即達到最大的迭代次數時，則會將進化中獲得的有著最大適應值的個體作為最優解輸出。

（二）遺傳算法特點

遺傳算法的具體特點可以概述為如下：

1.與傳統算法不同，遺傳算法與其最大的差別就是遺傳算法是從問題的解集出發的，而非單一的解。從初始解集開始搜索擇優，覆蓋的范圍較大，有利于全局范圍內擇優。

2.遺傳算法在搜索空間中同時評價多個解，即同時對多個個體的適應度進行計算，有效降低了陷入局部范圍最優解的風險。

3.遺傳算法在運算操作時，基本上只使用通過適應度函數求得的數值來對個體進行評估，而不需要搜索空間的知識或是其他輔助信息。適應度函數自變量的范圍，也就是它的定義域可以隨便設置，并且不強求函數必須連續可微，此特性大大擴展了遺傳算法適用的范圍。

4.遺傳算法利用概率變遷原則來確定其查找的方向，而非確定性規則。

5.遺傳算法的自組織性、自適應性、自學習性使其根據運算過程中得到的信息進行查找時，保證適應度較大的個體有更大的生存下去的可能性，并擁有更能適應自然的基因結構。

6.遺傳算法在進化過程中也可以通過自身動態的自適應能力，自動調節算法編碼的精度與參數的控制。

（三）Matlab軟件

Matlab軟件主要是提供了面對交互式程序設計、可視化以及科學計算的高科技的計算環境。它提供了一個方便使用的視窗環境，其中融合了矩陣計算、數值分析和Matlab軟件主要是提供了面對交互式程序設計、可視化以及科學計算的高科技的計算環境。它提供了一個方便使用的視窗環境，其中融合了矩陣計算、數值分析和非線性動態系統的建模和仿真等功能，為科研、工程設計等很多科學領域提供了完備的處理方案，并且可以說是跳出了以往的非交互式程序設計語言的編輯模式，是當前有著先進水平的國際科學計算軟件的代表。

在數值計算方面，Matlab在數學方面的科技應用軟件中始終處于領先地位，由于其強大的創建用戶界面、繪制函數和數據、實現算法、矩陣運算、連接其他編程語言的程序等功能，在圖像處理、金融建模設計、信號處理與通訊、信號檢測、工程計算、控制設計與分析等領域中都有應用。

（四）仿真求解

通過具體問題的描述，結合實際構建的模型，為了保證求解結果的準確性，本文借助Matlab對該問題進行了仿真，求解最優路徑，具體操作過程如下：

打開Matlab通過具體問題的描述，結合實際構建的模型，為了保證求解結果的準確性，本文借助Matlab對該問題進行了仿真，求解最優路徑，具體操作過程如下：

1.打開Matlab。

2.新建M文件，編輯代碼，設置參數：迭代次數為50，交叉概率為0.7，變異概率為0.02，更新百分比為0.7，設置配送車輛數為1，由于實例中所有需求點都是由同一輛車進行配送，不存在載重限制問題，所以為了方便計算，將車輛的最大載重能力設為10，需求量全部設為0。

3.代碼共分為兩部分，首先分別編輯選擇、交叉、變異部分，最后編輯主程序，程序運行時運行主程序，其中自動調用選擇、交叉、變異程序。

4.改變設置參數，比較仿真結果，部分結果見表6：

運行程序，發現經多次反復實驗，當初始種群為200時，總里程數最少。

（五）結果分析

由于遺傳算法的操作是基于概率而非確定的，所以其運算結果并不是唯一的，這也是其相比于其他方法最大的缺點。并且由上述仿真過程可知，參數的設置會導致仿真結果出現不同，所以使用遺傳算法求解具有很大的不確定性，需要多次改變參數設置和反復運行程序才能得到最優解，找到最優路徑。

由Matlab軟件進行仿真之后的結果顯示，使用遺傳算法求解案例時，最終的最優配送路徑為：0-8-7-5-6-9-3-4-2-1-0，總路程為108.1km。

節約法與遺傳算法求解結果見表7。通過對結果的分析比較發現，遺傳算法比節約法節省了30km路程，雖然遺傳算法具有不穩定性，但是其運算結果總體來說還是由于節約法的，即用遺傳算法求出的最優路徑下的總路程明顯比用節約法求出的要短，說明使用遺傳算法可以更有效地解決VRP問題。通過分析對比，可將其運用到實際配送過程中去，將會實現車輛路徑選擇的科學性。

六、結論

文章調查分析了浙江一鳴食品股份有限公司對杭州市余杭區的鮮奶吧配送的實際情況，并以該區的一鳴真鮮奶吧為例，建立了配送路徑最短的數學模型;在相同背景條件下，分別運用節約法和遺傳算法對實例進行優化分析，人工智能算法一般需要借助計算機實現，因此在使用遺傳算法時，求解是通過Matlab對其仿真而進行的，從而得到了不同方法下的最優解;對兩種方法求得的最優結果進行對比分析，發現運用遺傳算法求得的結果要優于節約法，今后可將此方法大量運用于同類問題中。

參考文獻：

[1]Chen P， Huang H，Dong X Y. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem [J]. Expert Systems with Applications， 2010，37（2）： 1620-1627.

[2]楊丹婷.冷鏈物流配送路徑優化研究[D].大連：大連海事大學，2014.

[3]趙光哲.大學排課問題中的遺傳算法設計[J].延邊大學學報，2006，32（1）：64-68.

[4]周欣.多學科虛擬樣機工具軟件集成技術研究與實現[D].南京：南京航空航天大學，2010.

[5]彭敏.基于改進遺傳算法的農產品物流配送車輛路徑優化研究[D].長沙：長沙理工大學，2009.

作者簡介：

張培，女，江蘇鎮江人，東南大學經濟管理學院研究生，研究方向：物流與供應鏈管理;

武忠，男，內蒙古人，東南大學經濟管理學院副教授、博士，研究方向：電子商務。