遺傳算法在快遞配送領(lǐng)域的應(yīng)用分析

摘 要：隨著信息技術(shù)的發(fā)展，現(xiàn)代物流作為“第三個利潤源泉”是一種先進的組織方式和管理技術(shù)，已被世界各國廣泛采用，并形成商業(yè)產(chǎn)業(yè)化，在國民經(jīng)濟中發(fā)揮越來越重要的作用。物流優(yōu)化技術(shù)，正受到日益廣泛的重視，并處于巨大的發(fā)展浪潮中。

關(guān)鍵詞：遺傳算法;快遞配送;路徑優(yōu)化

在現(xiàn)代物流中，配送是一個重要的與消費者直接相連的環(huán)節(jié)，一方面可以體現(xiàn)企業(yè)的核心競爭力，另一方面通過線路優(yōu)化，可以提高企業(yè)的運作效率，降低配送成本，實現(xiàn)物流科學(xué)化配送。目前市場上倉儲類管理系統(tǒng)已經(jīng)比較完善，但對于不同需求的路線規(guī)劃還存在一定的短板，基于當(dāng)前末端配送路徑優(yōu)化的要求，本文引用遺傳算法，對某鄉(xiāng)鎮(zhèn)的郵政服務(wù)作了系統(tǒng)的設(shè)計和優(yōu)化。

1、問題提出：

某鄉(xiāng)鎮(zhèn)郵政服務(wù)點（用0表示）需要向管轄區(qū)內(nèi)的20個村委會提供郵政派件服務(wù)，其中服務(wù)點與20個村委會坐標(biāo)已知，見下表1-1，且每個村委會一次派送需求量也已知。要求郵件派送車完成派送任務(wù)后需返回服務(wù)點，同時一個村委會僅需要一輛派送車服務(wù)即可滿足派送需求。每輛派送車的行駛最遠里程均為50KM和裝載容量限制均為8t，派送車輛足夠多。要求設(shè)計一組配送路線在滿足車輛里程和容量限制的前提下使車輛行駛的總里程最短。服務(wù)點的坐標(biāo)為（14.15KM，13.10km）。

2、郵件派送服務(wù)優(yōu)化原理：

此類問題在數(shù)學(xué)上屬于典型的VRP問題，查閱相關(guān)資料也可以了解到解決此類問題的算法是多種多樣的，遺傳算法作為經(jīng)典的現(xiàn)代啟發(fā)式算法在解決這類問題上有得天獨厚的優(yōu)勢。所謂優(yōu)化就是指通過算法的設(shè)計讓一個現(xiàn)實問題變?yōu)橐粋€可運算的數(shù)學(xué)問題，通過運算來使目標(biāo)函數(shù)值越來越小，對于上面的問題就是指使總里程最短。

3、遺傳算法的設(shè)計：

3.1 遺傳算法簡介

遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。遺傳算法從代表問題潛在的一個種群開始的，而一個種群則由經(jīng)過基因編碼的個體組成。由于仿照基因編碼的工作很復(fù)雜，我們往往進行簡化，用二進制編碼來代替等，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代中，根據(jù)問題域中個體的適應(yīng)度大小來選擇個體，并借助于自然遺傳學(xué)的遺傳算子進行組合交叉和變異，產(chǎn)生出新一代的種群。

3.2遺傳算法設(shè)計

基于本題的實際情況來看，基因的編碼我們可以設(shè)計為一個車輛派送村委會的順序，如某一輛車從服務(wù)點出發(fā)依次經(jīng)過鄉(xiāng)鎮(zhèn)3，鄉(xiāng)鎮(zhèn)17，鄉(xiāng)鎮(zhèn)15，鄉(xiāng)鎮(zhèn)5，完成配送任務(wù)后返回到服務(wù)中心，則這一條基因編碼就可以是0-3-17-15-5-0，某一組解的所有車輛的配送順序構(gòu)成這一代種群的基因庫。在每一代繁殖的過程，遺傳因子可能發(fā)生交叉，前后順序顛倒等遺傳變異行為，種群的適應(yīng)度函數(shù)則可以設(shè)計為車輛行駛里程函數(shù)的倒數(shù)，基于本題來說，適應(yīng)度越大，代表行駛的總里程越短，越是我們需要的結(jié)果。假設(shè)某代種群中其中有兩條基因編碼分別為0-3-17-15-5-0，0-6-9-4-13-0，在發(fā)生復(fù)制遺傳的過程中遺傳因子的交叉操作第一種情況可以設(shè)計為第一條的基因15與第二條的基因9交換了順序，形成新的0-3-17-9-5-0，0-6-15-4-13-0兩條染色體。第二種情況可以設(shè)計為第一條染色體的尾部基因5添加到了第二條染色體的尾部，形成新的0-3-17-15-0，0-6-9-4-13-5-0兩條染色體。基因的前后順序顛倒則可以設(shè)計為如0-3-17-15-5-0，在復(fù)制過程中基因5和15交換了順序，形成了新的一條染色體為0-3-17-5-15-0，其中需要注意的是在每一代種群基因的遺傳中，交叉操作和前后順序顛倒操作必須是隨機發(fā)生的。在每一代種群復(fù)制以后，需要判斷新一代種群的適應(yīng)度函數(shù)值大小，如果適應(yīng)度較前一次大，則用新一代種群取代上一代種群，如果適應(yīng)度變小了，則種群依然采用上一代的種群，如此循環(huán)往復(fù)幾百上千次以后，將可以得到相對適應(yīng)度最大的種群即為我們做需要的種群。

3.3流程圖介紹

4、結(jié)果分析

基于以上的設(shè)計，利用MATLAB建模，并設(shè)置好各種參數(shù)，分別輸入迭代次數(shù)為100，200，300，400，500可以得出以下結(jié)果。

總的來看，迭代次數(shù)越多迭代所花費的時間就越多，不過得到的結(jié)果越接近于真實的最小值。通過這樣的研究，基本就能解決末端配送的的路徑問題了，這將極大地促進電商和物流行業(yè)的一同前進。

參考文獻：

[1] 鄭瑞卿.構(gòu)造節(jié)約遺傳算法解決電子商務(wù)環(huán)境下的物流配送路徑優(yōu)化問題研究[J].宜春學(xué)院學(xué)報，2018，40（12）：59-61.

[2] 宋金文. 現(xiàn)代物流配送系統(tǒng)的研究與實現(xiàn)[D].天津大學(xué)，2016.

作者簡介：

朱康林（1998），男，漢族，本科生，研究方向為電氣工程及其自動化方向。