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

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

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

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

1、問題提出：

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

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

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

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

3.1 遺傳算法簡(jiǎn)介

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

3.2遺傳算法設(shè)計(jì)

基于本題的實(shí)際情況來看，基因的編碼我們可以設(shè)計(jì)為一個(gè)車輛派送村委會(huì)的順序，如某一輛車從服務(wù)點(diǎn)出發(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è)計(jì)為車輛行駛里程函數(shù)的倒數(shù)，基于本題來說，適應(yīng)度越大，代表行駛的總里程越短，越是我們需要的結(jié)果。假設(shè)某代種群中其中有兩條基因編碼分別為0-3-17-15-5-0，0-6-9-4-13-0，在發(fā)生復(fù)制遺傳的過程中遺傳因子的交叉操作第一種情況可以設(shè)計(jì)為第一條的基因15與第二條的基因9交換了順序，形成新的0-3-17-9-5-0，0-6-15-4-13-0兩條染色體。第二種情況可以設(shè)計(jì)為第一條染色體的尾部基因5添加到了第二條染色體的尾部，形成新的0-3-17-15-0，0-6-9-4-13-5-0兩條染色體?；虻那昂箜樞蝾嵉箘t可以設(shè)計(jì)為如0-3-17-15-5-0，在復(fù)制過程中基因5和15交換了順序，形成了新的一條染色體為0-3-17-5-15-0，其中需要注意的是在每一代種群基因的遺傳中，交叉操作和前后順序顛倒操作必須是隨機(jī)發(fā)生的。在每一代種群復(fù)制以后，需要判斷新一代種群的適應(yīng)度函數(shù)值大小，如果適應(yīng)度較前一次大，則用新一代種群取代上一代種群，如果適應(yīng)度變小了，則種群依然采用上一代的種群，如此循環(huán)往復(fù)幾百上千次以后，將可以得到相對(duì)適應(yīng)度最大的種群即為我們做需要的種群。

3.3流程圖介紹

4、結(jié)果分析

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

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

參考文獻(xiàn)：

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

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

作者簡(jiǎn)介：

朱康林（1998），男，漢族，本科生，研究方向?yàn)殡姎夤こ碳捌渥詣?dòng)化方向。