基于遺傳算法的鮮奶冷鏈物流配送路徑優(yōu)化

張培 武忠

摘 要：隨著物流領(lǐng)域的不斷發(fā)展，越來(lái)越多的方法可用于解決VRP問(wèn)題，其中，啟發(fā)式人工智能算法更是得到了巨大的發(fā)展。筆者首先對(duì)背景公司的配送現(xiàn)狀進(jìn)行了簡(jiǎn)要分析，然后分別用節(jié)約法和遺傳算法對(duì)實(shí)例進(jìn)行優(yōu)化求解并得出結(jié)果，其中遺傳算法的求解過(guò)程是借助Matlab軟件實(shí)現(xiàn)的。最后，將兩種方法求得的結(jié)果進(jìn)行綜合比較，發(fā)現(xiàn)在同樣的條件下，遺傳算法能夠更好地實(shí)現(xiàn)對(duì)配送路徑的優(yōu)化。

關(guān)鍵詞：車(chē)輛路徑優(yōu)化;節(jié)約法;遺傳算法

中圖分類(lèi)號(hào)：F252 ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? 文章編號(hào)：1008-4428（2018）03-15 ?-03

一、引言

車(chē)輛路徑優(yōu)化問(wèn)題（Vehicle Routing Problem），簡(jiǎn)稱(chēng)VRP問(wèn)題，指的是已知配送中心的位置和客戶(hù)需求點(diǎn)的位置、需求量，并且已知配送中心所擁有的一定數(shù)量的配送車(chē)輛的載貨量和容量，在滿(mǎn)足一定的約束條件前提下，以特定的優(yōu)化指標(biāo)（距離最短、時(shí)間最短等）為目標(biāo)，合理安排車(chē)輛的配送方案。文章以一鳴真鮮奶吧為背景，對(duì)其在杭州市江干區(qū)的一鳴真鮮奶吧的配送路徑進(jìn)行優(yōu)化。

一鳴真鮮奶吧隸屬于浙江一鳴食品股份有限公司。浙江一鳴食品股份有限公司主要生產(chǎn)經(jīng)營(yíng)與乳制品有關(guān)的產(chǎn)品，其打造的泰順高山牧場(chǎng)的奶源保證了產(chǎn)品的質(zhì)量。目前，溫州地區(qū)80%的奶源都由一鳴供應(yīng)，為了提升奶源的質(zhì)量，一鳴創(chuàng)建了全方位的牧業(yè)管理體系，集牧草種植、牧場(chǎng)管理、乳牛飼養(yǎng)、飼料加工等為一體，并且率先實(shí)行了“公司+農(nóng)戶(hù)”的生產(chǎn)方法，利用當(dāng)?shù)貏趧?dòng)力來(lái)維持牧場(chǎng)的日常生產(chǎn)，在節(jié)省勞動(dòng)力的同時(shí)也帶動(dòng)了當(dāng)?shù)亟?jīng)濟(jì)的發(fā)展。其采用招商加盟模式運(yùn)營(yíng)的一鳴真鮮奶吧由于新鮮的奶源、獨(dú)特的產(chǎn)品而廣受歡迎，店鋪已經(jīng)多達(dá)五百多家，利潤(rùn)頗豐。

二、配送存在的問(wèn)題

（一）車(chē)輛路線選擇的經(jīng)驗(yàn)操作性較強(qiáng)

公司的物流長(zhǎng)途上主要依賴(lài)與其他物流配送公司的合作，而短途配送則是雇有專(zhuān)門(mén)的司機(jī)，對(duì)司機(jī)的專(zhuān)業(yè)知識(shí)水平要求較低，司機(jī)每天配送一次，每個(gè)司機(jī)固定地負(fù)責(zé)一個(gè)區(qū)域，由于對(duì)時(shí)間沒(méi)有硬性要求，因此他們并不會(huì)也無(wú)法對(duì)配送線路問(wèn)題進(jìn)行系統(tǒng)的研究和優(yōu)化，因此經(jīng)驗(yàn)操作的成分較高。司機(jī)通常會(huì)根據(jù)自己的經(jīng)驗(yàn)選擇配送路徑，他們往往會(huì)因?yàn)轫樎坊蛘呔嚯x近而將兩家或多家門(mén)店歸為同一條線路。這種安排的方式常常會(huì)由于城市復(fù)雜的交通狀況而對(duì)配送產(chǎn)生較大的不確定性，因此這種方式就配送而言不夠科學(xué)，甚至經(jīng)常會(huì)出現(xiàn)重疊運(yùn)輸?shù)默F(xiàn)象。

（二）對(duì)時(shí)間約束認(rèn)識(shí)不足

專(zhuān)人負(fù)責(zé)專(zhuān)區(qū)，不存在業(yè)務(wù)競(jìng)爭(zhēng)，也沒(méi)有嚴(yán)格的獎(jiǎng)懲制度，只要求上午送到，沒(méi)有具體的時(shí)間約束，就導(dǎo)致司機(jī)對(duì)工作沒(méi)有緊張感。另外，車(chē)輛由配送中心安排，司機(jī)只負(fù)責(zé)運(yùn)輸，對(duì)冷藏車(chē)輛的消耗認(rèn)識(shí)不夠深刻，缺乏主人翁意識(shí)，所以他們通常采用隨遇而安的態(tài)度對(duì)待配送，對(duì)不必要的時(shí)間和成本消耗視而不見(jiàn)，對(duì)時(shí)間約束認(rèn)識(shí)不足。

三、公司實(shí)際問(wèn)題描述

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

為了方便求解，為余杭區(qū)的9家鮮奶吧進(jìn)行編號(hào)排序（見(jiàn)表1），各個(gè)門(mén)店之間的距離見(jiàn)表2。

四、節(jié)約法求解

（一）根據(jù)表2作各點(diǎn)之間的最短距離表（見(jiàn)表3）：

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

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

（四）根據(jù)表5，整理得到實(shí)例最終的配送路線為：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）。

五、遺傳算法求解

（一）遺傳算法結(jié)構(gòu)

先把需要求解的實(shí)際問(wèn)題具體表述成對(duì)目標(biāo)函數(shù)的尋優(yōu)問(wèn)題，這樣需要優(yōu)化的目標(biāo)函數(shù)就是種群對(duì)自然的適應(yīng)能力，個(gè)體的生物種群對(duì)應(yīng)于優(yōu)化變量，然后從當(dāng)前的種群出發(fā)，復(fù)制、交叉、變異和選擇產(chǎn)生新一代種群，這個(gè)過(guò)程是重復(fù)的，直到達(dá)到進(jìn)化時(shí)間的要求或者找到符合要求的種群，這就是遺傳算法優(yōu)化求解問(wèn)題的基本思路。其操作過(guò)程如下：

1.初始化數(shù)值：進(jìn)化代數(shù)的初始值設(shè)為t=0，同時(shí)確定最大迭代次數(shù)T的值，初始種群P（0）隨機(jī)生成，其中有N個(gè)個(gè)體。

2.評(píng)價(jià)個(gè)體：由適應(yīng)度函數(shù)的表達(dá)式求出每一代種群P（t）中所有個(gè)體的適應(yīng)度。

3.選擇操作：根據(jù)對(duì)種群中個(gè)體的適應(yīng)度的評(píng)估，把選擇算子作用到種群上。選擇運(yùn)算有兩個(gè)目標(biāo)，直接且優(yōu)秀的個(gè)體遺傳至子代，或者是遺傳由交叉或配對(duì)產(chǎn)生的新個(gè)體。

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

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

6.產(chǎn)生下一代：下一代種群P（t+1）將由種群P（t）經(jīng)過(guò)選擇、交叉、變異操作產(chǎn)生。

7.判斷終止條件：當(dāng)t=T時(shí)，即達(dá)到最大的迭代次數(shù)時(shí)，則會(huì)將進(jìn)化中獲得的有著最大適應(yīng)值的個(gè)體作為最優(yōu)解輸出。

（二）遺傳算法特點(diǎn)

遺傳算法的具體特點(diǎn)可以概述為如下：

1.與傳統(tǒng)算法不同，遺傳算法與其最大的差別就是遺傳算法是從問(wèn)題的解集出發(fā)的，而非單一的解。從初始解集開(kāi)始搜索擇優(yōu)，覆蓋的范圍較大，有利于全局范圍內(nèi)擇優(yōu)。

2.遺傳算法在搜索空間中同時(shí)評(píng)價(jià)多個(gè)解，即同時(shí)對(duì)多個(gè)個(gè)體的適應(yīng)度進(jìn)行計(jì)算，有效降低了陷入局部范圍最優(yōu)解的風(fēng)險(xiǎn)。

3.遺傳算法在運(yùn)算操作時(shí)，基本上只使用通過(guò)適應(yīng)度函數(shù)求得的數(shù)值來(lái)對(duì)個(gè)體進(jìn)行評(píng)估，而不需要搜索空間的知識(shí)或是其他輔助信息。適應(yīng)度函數(shù)自變量的范圍，也就是它的定義域可以隨便設(shè)置，并且不強(qiáng)求函數(shù)必須連續(xù)可微，此特性大大擴(kuò)展了遺傳算法適用的范圍。

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

5.遺傳算法的自組織性、自適應(yīng)性、自學(xué)習(xí)性使其根據(jù)運(yùn)算過(guò)程中得到的信息進(jìn)行查找時(shí)，保證適應(yīng)度較大的個(gè)體有更大的生存下去的可能性，并擁有更能適應(yīng)自然的基因結(jié)構(gòu)。

6.遺傳算法在進(jìn)化過(guò)程中也可以通過(guò)自身動(dòng)態(tài)的自適應(yīng)能力，自動(dòng)調(diào)節(jié)算法編碼的精度與參數(shù)的控制。

（三）Matlab軟件

Matlab軟件主要是提供了面對(duì)交互式程序設(shè)計(jì)、可視化以及科學(xué)計(jì)算的高科技的計(jì)算環(huán)境。它提供了一個(gè)方便使用的視窗環(huán)境，其中融合了矩陣計(jì)算、數(shù)值分析和Matlab軟件主要是提供了面對(duì)交互式程序設(shè)計(jì)、可視化以及科學(xué)計(jì)算的高科技的計(jì)算環(huán)境。它提供了一個(gè)方便使用的視窗環(huán)境，其中融合了矩陣計(jì)算、數(shù)值分析和非線性動(dòng)態(tài)系統(tǒng)的建模和仿真等功能，為科研、工程設(shè)計(jì)等很多科學(xué)領(lǐng)域提供了完備的處理方案，并且可以說(shuō)是跳出了以往的非交互式程序設(shè)計(jì)語(yǔ)言的編輯模式，是當(dāng)前有著先進(jìn)水平的國(guó)際科學(xué)計(jì)算軟件的代表。

在數(shù)值計(jì)算方面，Matlab在數(shù)學(xué)方面的科技應(yīng)用軟件中始終處于領(lǐng)先地位，由于其強(qiáng)大的創(chuàng)建用戶(hù)界面、繪制函數(shù)和數(shù)據(jù)、實(shí)現(xiàn)算法、矩陣運(yùn)算、連接其他編程語(yǔ)言的程序等功能，在圖像處理、金融建模設(shè)計(jì)、信號(hào)處理與通訊、信號(hào)檢測(cè)、工程計(jì)算、控制設(shè)計(jì)與分析等領(lǐng)域中都有應(yīng)用。

（四）仿真求解

通過(guò)具體問(wèn)題的描述，結(jié)合實(shí)際構(gòu)建的模型，為了保證求解結(jié)果的準(zhǔn)確性，本文借助Matlab對(duì)該問(wèn)題進(jìn)行了仿真，求解最優(yōu)路徑，具體操作過(guò)程如下：

打開(kāi)Matlab通過(guò)具體問(wèn)題的描述，結(jié)合實(shí)際構(gòu)建的模型，為了保證求解結(jié)果的準(zhǔn)確性，本文借助Matlab對(duì)該問(wèn)題進(jìn)行了仿真，求解最優(yōu)路徑，具體操作過(guò)程如下：

1.打開(kāi)Matlab。

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

3.代碼共分為兩部分，首先分別編輯選擇、交叉、變異部分，最后編輯主程序，程序運(yùn)行時(shí)運(yùn)行主程序，其中自動(dòng)調(diào)用選擇、交叉、變異程序。

4.改變?cè)O(shè)置參數(shù)，比較仿真結(jié)果，部分結(jié)果見(jiàn)表6：

運(yùn)行程序，發(fā)現(xiàn)經(jīng)多次反復(fù)實(shí)驗(yàn)，當(dāng)初始種群為200時(shí)，總里程數(shù)最少。

（五）結(jié)果分析

由于遺傳算法的操作是基于概率而非確定的，所以其運(yùn)算結(jié)果并不是唯一的，這也是其相比于其他方法最大的缺點(diǎn)。并且由上述仿真過(guò)程可知，參數(shù)的設(shè)置會(huì)導(dǎo)致仿真結(jié)果出現(xiàn)不同，所以使用遺傳算法求解具有很大的不確定性，需要多次改變參數(shù)設(shè)置和反復(fù)運(yùn)行程序才能得到最優(yōu)解，找到最優(yōu)路徑。

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

節(jié)約法與遺傳算法求解結(jié)果見(jiàn)表7。通過(guò)對(duì)結(jié)果的分析比較發(fā)現(xiàn)，遺傳算法比節(jié)約法節(jié)省了30km路程，雖然遺傳算法具有不穩(wěn)定性，但是其運(yùn)算結(jié)果總體來(lái)說(shuō)還是由于節(jié)約法的，即用遺傳算法求出的最優(yōu)路徑下的總路程明顯比用節(jié)約法求出的要短，說(shuō)明使用遺傳算法可以更有效地解決VRP問(wèn)題。通過(guò)分析對(duì)比，可將其運(yùn)用到實(shí)際配送過(guò)程中去，將會(huì)實(shí)現(xiàn)車(chē)輛路徑選擇的科學(xué)性。

六、結(jié)論

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

參考文獻(xiàn)：

[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]楊丹婷.冷鏈物流配送路徑優(yōu)化研究[D].大連：大連海事大學(xué)，2014.

[3]趙光哲.大學(xué)排課問(wèn)題中的遺傳算法設(shè)計(jì)[J].延邊大學(xué)學(xué)報(bào)，2006，32（1）：64-68.

[4]周欣.多學(xué)科虛擬樣機(jī)工具軟件集成技術(shù)研究與實(shí)現(xiàn)[D].南京：南京航空航天大學(xué)，2010.

[5]彭敏.基于改進(jìn)遺傳算法的農(nóng)產(chǎn)品物流配送車(chē)輛路徑優(yōu)化研究[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2009.

作者簡(jiǎn)介：

張培，女，江蘇鎮(zhèn)江人，東南大學(xué)經(jīng)濟(jì)管理學(xué)院研究生，研究方向：物流與供應(yīng)鏈管理;

武忠，男，內(nèi)蒙古人，東南大學(xué)經(jīng)濟(jì)管理學(xué)院副教授、博士，研究方向：電子商務(wù)。