基于改進(jìn)遺傳算法的冷鏈物流配送路徑優(yōu)化

劉天麒 吝永紅

（1.天津理工大學(xué)管理學(xué)院，天津 300384；2.建科機(jī)械（天津）股份有限公司，天津 300408）

一、引言

近年來(lái)，我國(guó)電商行業(yè)的蓬勃發(fā)展，使得網(wǎng)上購(gòu)物成為人們的主要購(gòu)物消費(fèi)渠道，人們不僅在網(wǎng)上購(gòu)買日用品、美妝產(chǎn)品，還購(gòu)買生鮮食物產(chǎn)品。網(wǎng)購(gòu)的渠道也從淘寶、京東等大型購(gòu)物平臺(tái)，逐漸向直播帶貨平臺(tái)進(jìn)行分流，此種網(wǎng)購(gòu)趨勢(shì)使得對(duì)物流行業(yè)的需求逐漸增加。物流運(yùn)輸作為整個(gè)網(wǎng)購(gòu)流程的核心樞紐，占據(jù)著較為重要的位置。冷鏈物流是指在冷藏條件下進(jìn)行的物流活動(dòng)，它涉及食品、藥品等易腐、需要恒溫保存的商品。冷鏈物流配送路徑優(yōu)化是物流管理中的一個(gè)重要環(huán)節(jié)，直接影響物流成本、時(shí)效和服務(wù)質(zhì)量。遺傳算法作為一種啟發(fā)式搜索算法，具有良好的全局尋優(yōu)能力，已被廣泛應(yīng)用于各類優(yōu)化問(wèn)題。冷鏈物流配送路徑優(yōu)化問(wèn)題可描述為：在滿足冷藏商品質(zhì)量約束的條件下，規(guī)劃一組最優(yōu)的配送路徑，使得總的配送成本（包括運(yùn)輸成本、冷藏成本、時(shí)間懲罰成本等）最小化。該問(wèn)題具有多約束、非線性等特點(diǎn)，傳統(tǒng)的優(yōu)化方法難以有效求解。

基于此，本文將以冷鏈物流配送路徑作為研究對(duì)象，通過(guò)優(yōu)化配送車輛的路線，降低冷鏈運(yùn)輸造成的成本問(wèn)題，進(jìn)而提高物流運(yùn)輸?shù)呐渌托剩乙欢ǔ潭壬蠝p少碳排放量，降低物流運(yùn)輸對(duì)環(huán)境的污染，具有較為重要的現(xiàn)實(shí)意義。本文中構(gòu)建的模型算法設(shè)計(jì)，融合了遺傳算法和煙花算法，設(shè)計(jì)出一種改進(jìn)型煙花遺傳算法（IFWGA），該算法可以有效地解決冷鏈物流配送的車輛路徑問(wèn)題。借助Matlab2021a 進(jìn)行編碼運(yùn)算，并通過(guò)算例對(duì)結(jié)果進(jìn)行驗(yàn)證，可得出此算法研究的應(yīng)用結(jié)論。該算法能夠跟隨快速發(fā)展的物流行業(yè)趨勢(shì)，借助軟時(shí)間窗的約束條件，為冷鏈配送提供全新的優(yōu)化路徑，借此增強(qiáng)物流企業(yè)的運(yùn)輸效益，幫助電商企業(yè)降低運(yùn)輸成本，使物流企業(yè)凝練核心競(jìng)爭(zhēng)力，有效地推動(dòng)物流行業(yè)的快速發(fā)展。

二、模型構(gòu)建與算法設(shè)計(jì)

1.問(wèn)題描述

本文進(jìn)行的冷鏈物流配送模型研究中，需要從多個(gè)成本方面進(jìn)行考量，其中已知運(yùn)送生鮮農(nóng)產(chǎn)品的冷鏈物流配送車型及相關(guān)車型數(shù)量，同時(shí)要保證算法研究中能夠滿足客戶的運(yùn)輸需求，并需在客戶要求的期望送達(dá)時(shí)間內(nèi)完成運(yùn)送。基于上述條件方可建立運(yùn)輸路徑問(wèn)題的數(shù)學(xué)模型。確保研究能夠?qū)⑦\(yùn)輸成本控制在最低范圍內(nèi)，并規(guī)劃和計(jì)算出科學(xué)的物流配送方案，借此降低運(yùn)輸過(guò)程中產(chǎn)生的碳排放，并盡量減少由于車輛開關(guān)門造成的貨物損耗，其中需要從成本控制等方面創(chuàng)建模型，并從以下四個(gè)方面進(jìn)行綜合考量。

（1）固定成本

本研究中固定成本主要有車輛費(fèi)用、駕駛員人工費(fèi)用及一系列車輛固定成本等，若該配送中心共有K輛車，則配送過(guò)程中的固定成本可用C1表示，見(jiàn)式（1）。

（2）運(yùn)輸成本

由于本研究需要對(duì)運(yùn)輸路徑進(jìn)行規(guī)劃，因此運(yùn)輸成本屬于變量，需要根據(jù)車輛的行駛距離進(jìn)行確定，將由距離決定的運(yùn)輸成本表示為C2，見(jiàn)式（2）。

（3）懲罰成本

該數(shù)學(xué)模型構(gòu)建中，軟時(shí)間窗概念定義為客戶可接受的遲到時(shí)間范圍，懲罰成本C3見(jiàn)式(3)。

式（3）中：[eti，lti]為硬時(shí)間窗；[ei，li]為軟時(shí)間窗；的值決定j 車是否派送了客戶i（i 取值為0 或1，1 表示配送，0 表示不配送）；P1為單價(jià)；tik是實(shí)際配送過(guò)程中k 車到達(dá)坐標(biāo)點(diǎn)i 的時(shí)間；μ1、μ2是預(yù)先設(shè)置的懲罰系數(shù)；qi是i 客戶對(duì)生鮮農(nóng)產(chǎn)品的需求量；M 表示一個(gè)極大值。

（4）制冷成本

該成本計(jì)算可引入轉(zhuǎn)化系數(shù)作為參考，將熱負(fù)荷作為關(guān)門狀態(tài)下制冷劑的消耗成本，其中用Qk1來(lái)表示k 車運(yùn)行中產(chǎn)生的熱負(fù)荷，Qk2表示k 車開門狀態(tài)產(chǎn)生的熱量，C51表示關(guān)門狀態(tài)下的制冷成本，C52表示開關(guān)門過(guò)程中的制冷成本，見(jiàn)式（4）-式（7）。

式（4）-式（7）中：P2表示標(biāo)準(zhǔn)距離行駛成本；S 為車廂的表面積；Sw、Sn分別為外、內(nèi)部的車廂面積；R 表示傳熱系數(shù)；Tw、Tn分別為外、內(nèi)部的溫度；tij表示客戶i 到客戶j 的時(shí)間；α 代表了開門的頻率，其取值見(jiàn)表1。

表1 開門頻度系數(shù)

因此，總制冷成本C5見(jiàn)式（8）。

2.改進(jìn)遺傳算法設(shè)計(jì)

由于車輛路徑問(wèn)題中具有多種構(gòu)成因素，且跟隨構(gòu)成因素的不同組合，可形成不同的目標(biāo)。本研究中選擇遺傳算法進(jìn)行改進(jìn)設(shè)計(jì)，是因?yàn)檫z傳算法作為具有較強(qiáng)全局搜索能力的強(qiáng)智能算法，其應(yīng)用范圍更為廣泛。因此在傳統(tǒng)遺傳算法基礎(chǔ)上引入改進(jìn)策略，可有效避免遺傳操作過(guò)程中丟失潛在的最優(yōu)解，且能夠借此彌補(bǔ)出現(xiàn)的局部搜索不到位情況，另外該算法中存在的易早熟收斂、局部陷落等不足之處，可通過(guò)煙花算法進(jìn)行補(bǔ)足，借助其自身具有的高強(qiáng)尋優(yōu)能力，輔助遺傳算法的改進(jìn)。

所謂遺傳算法是模仿自然界中繁衍的數(shù)學(xué)運(yùn)算方法，其具有操作簡(jiǎn)單，尋優(yōu)能力強(qiáng)的特性。本文采用遺傳算法為主框架，力求利用遺傳算法優(yōu)勢(shì)特點(diǎn)，結(jié)合煙花算法爆炸性優(yōu)勢(shì)，進(jìn)行巧妙的改進(jìn)，在眾多解決方式中選擇最接近最優(yōu)解的途徑，并進(jìn)行綜合比較選擇適宜的路徑。本研究中的煙花算法的變異算子設(shè)計(jì)為兩種步長(zhǎng)，根據(jù)步長(zhǎng)長(zhǎng)短分別定義為L(zhǎng)SMO 和SSMO。將在后文中進(jìn)行變異算子的形態(tài)切換，用以計(jì)算動(dòng)態(tài)概率值，且研究中根據(jù)迭代規(guī)律，前期將多使用LSMO，后期多使用SSMO。

3.算法操作

遺傳算法作為常用的全局搜索算法之一，可將可行性解決方案按照一定的編碼順序進(jìn)行組合編碼，形成染色體組合，并在計(jì)算中針對(duì)每個(gè)染色體進(jìn)行適應(yīng)度的計(jì)算，最終通過(guò)交叉、變異等操作得出全新的結(jié)論，此研究過(guò)程中可發(fā)現(xiàn)具有最大適應(yīng)度函數(shù)的染色體。此種算法操作過(guò)程，在種群的不斷繁衍中，能夠逐漸淘汰適應(yīng)度低的個(gè)體，而將適應(yīng)度高的個(gè)體進(jìn)行保存，便于后續(xù)進(jìn)行復(fù)制操作。因此，遺傳算法也包含上述染色體復(fù)制繁殖的特性。

（1）染色體編碼

作為遺傳算法的第一步驟，其需根據(jù)實(shí)際問(wèn)題進(jìn)行相應(yīng)的數(shù)據(jù)處理，便于選擇編碼方式，為后續(xù)的交叉等操作提供依據(jù)。其中函數(shù)模型構(gòu)建中，常用的編碼方式有二進(jìn)制編碼、自然數(shù)編碼、浮點(diǎn)數(shù)編碼等。其中利用數(shù)字1 和0 進(jìn)行組合的二進(jìn)制編碼較為容易實(shí)現(xiàn)，但編碼長(zhǎng)度會(huì)受到搜索效率的影響，而自然數(shù)編碼也較為常用，能夠?qū)?wèn)題進(jìn)行直接編碼，能夠使編碼結(jié)果明確清晰，亦具有更大的操作空間，搜索效果較好。因此，對(duì)遺傳算法進(jìn)行改進(jìn)中，本研究采用的編碼方式為自然數(shù)編碼。

（2）選擇

該操作亦是遺傳算法中的染色體復(fù)制環(huán)節(jié)，符合優(yōu)勝劣汰標(biāo)準(zhǔn)，被選中的個(gè)體可直接進(jìn)行復(fù)制，考量個(gè)體方案的適應(yīng)度，其中適應(yīng)度大的方案被選擇的幾率相應(yīng)升高，常見(jiàn)的選擇操作方法有輪盤賭選擇策略、精英保留策略、錦標(biāo)賽選擇策略等，本研究中選擇采用輪盤賭選擇策略，并在適當(dāng)?shù)臅r(shí)候引入精英保留策略。其中輪盤賭選擇策略能夠?qū)哂休^高適應(yīng)度的個(gè)體進(jìn)行選擇，但其亦存在錯(cuò)選的概率，易導(dǎo)致優(yōu)秀的路徑被遺漏，此選擇方法的最大優(yōu)勢(shì)是可使局部最優(yōu)化。而精英保留策略則主要是為了保證最優(yōu)秀的個(gè)體存留，采用直選的方式，防止優(yōu)秀的方案被交叉變異，此種選擇方法雖能夠解決局部最優(yōu)，但易使全局的搜索能力變差。將上述兩種操作方法進(jìn)行組合，可形成優(yōu)勢(shì)互補(bǔ)效果。

（3）交叉

交叉操作的本質(zhì)是重組，即對(duì)兩個(gè)個(gè)體進(jìn)行交叉操作，使其能夠形成全新的算法，通過(guò)此種交叉方式能夠?qū)?wèn)題的解法空間進(jìn)行不斷的搜索，便于得出最優(yōu)答案，并且此種交叉操作能夠便于個(gè)性化的設(shè)計(jì)。常見(jiàn)的交叉方式有單點(diǎn)、多點(diǎn)、均勻交叉等。其中單點(diǎn)交叉操作較為簡(jiǎn)單，只需進(jìn)行一次交叉，針對(duì)某一節(jié)點(diǎn)和條件進(jìn)行交叉即可，適應(yīng)性較小。多點(diǎn)交叉則是在單點(diǎn)交叉基礎(chǔ)上進(jìn)行的交叉點(diǎn)的變量增加，能夠進(jìn)行全局的優(yōu)化操作。均勻交叉主要指增加問(wèn)題的多樣性條件，并基于全局搜索能力的考量，進(jìn)行交叉選擇，此種交叉結(jié)果的質(zhì)量難以控制。本研究中采用多點(diǎn)交叉的方式，進(jìn)行反復(fù)對(duì)比選擇。

（4）變異

變異操作中為增強(qiáng)個(gè)體方案的適應(yīng)度，可對(duì)全局進(jìn)行搜索，并給予交叉操作，進(jìn)行有效的交叉變異，其往往與交叉共同利用，形成對(duì)遺傳算法的改進(jìn)，提升其全局搜索能力及局部搜索能力。其中常用的變異方式有基本位變異、均勻變異、高斯變異等。

（5）煙花算法

利用煙花算法對(duì)遺傳算法進(jìn)行改進(jìn)。具體步驟如下。

①計(jì)算爆炸數(shù)目。爆炸數(shù)目的確定及半徑的計(jì)算需根據(jù)煙花種群及適應(yīng)度進(jìn)行計(jì)算，其中爆炸數(shù)目越多，適應(yīng)度越強(qiáng)，呈正比關(guān)系。爆炸火花數(shù)目si見(jiàn)式（9）。

公式（9）中：f(xi)表示個(gè)體的適應(yīng)度值；ymax是當(dāng)前種群中適應(yīng)度的最大值；M 為控量常數(shù)（M ≤10）；常數(shù)ε 為防止除數(shù)為0 而存在。

其中Smax為最大火花數(shù)目，Smin為最小火花數(shù)目，見(jiàn)式（10）、式（11）。

③產(chǎn)生變異火花。變異火花可根據(jù)路徑優(yōu)化特點(diǎn)，起到平衡搜索能力的作用。因此本研究中涉及兩種步長(zhǎng)差異條件，第一種變異算子步長(zhǎng)為1（SSMO），第二種變異步長(zhǎng)為6（LSMO）。其中maxgen 表示最大迭代次數(shù)，計(jì)算見(jiàn)式（13）。

4.改進(jìn)要素

（1）約束條件

在改進(jìn)遺傳算法進(jìn)行車輛路徑問(wèn)題研究中，需要將約束條件作為求解問(wèn)題的限定標(biāo)準(zhǔn)，算法的改進(jìn)需在約束條件基礎(chǔ)上進(jìn)行操作，不得出現(xiàn)超出約束條件的情況。約束條件的存在，使不同問(wèn)題求解的方法有了限定標(biāo)準(zhǔn)。在車輛路徑問(wèn)題研究中，常見(jiàn)的約束條件有：①車輛載重約束。裝載的貨物不得超出車輛的最大載物重量，此為國(guó)家標(biāo)準(zhǔn)的運(yùn)輸硬性要求。②車輛行駛距離約束。此要求主要是限定車輛的行駛距離，確保運(yùn)送路線規(guī)劃中不超出最大行駛距離，避免影響配送效率。③客戶點(diǎn)服務(wù)約束。需要根據(jù)整體的運(yùn)送要求，確保每個(gè)客戶點(diǎn)都能夠有運(yùn)輸?shù)能囕v，保證冷鏈運(yùn)輸?shù)母采w率。④車輛出發(fā)點(diǎn)約束。所有車輛的起始點(diǎn)都應(yīng)從貨物中心出發(fā)，并在完成運(yùn)輸任務(wù)后即刻返回中心停車區(qū)域。⑤客戶服務(wù)時(shí)間約束。對(duì)于客戶特定規(guī)定的配送運(yùn)輸時(shí)間，要進(jìn)行單獨(dú)的算法設(shè)定，不可過(guò)早或過(guò)晚，避免影響冷鏈運(yùn)輸?shù)姆?wù)質(zhì)量。

（2）目標(biāo)函數(shù)

在遺傳算法改進(jìn)過(guò)程中，設(shè)定的目標(biāo)函數(shù)需要跟最終的運(yùn)輸目標(biāo)具有一致性，并根據(jù)不同的運(yùn)輸條件及需求，建立不同的函數(shù)目標(biāo)，函數(shù)目標(biāo)具有不唯一性，可由一個(gè)或多個(gè)組成，在改進(jìn)算法中常見(jiàn)的目標(biāo)函數(shù)有：①配送距離最短化。該目標(biāo)主要是要求所有車輛在運(yùn)輸過(guò)程中能夠保證總距離最短。②配送成本最小化。此目標(biāo)是優(yōu)化運(yùn)輸路徑的最終目的，即降低運(yùn)輸成本，其中成本包括車輛維護(hù)的固定成本，車輛運(yùn)輸成本，以及其他成本等。③車輛數(shù)目最少化。該目標(biāo)力求在完成配送任務(wù)過(guò)程中，盡量提升車輛的裝載能力，利用最少的車輛數(shù)目完成運(yùn)輸任務(wù)。

（3）客戶需求

在路徑問(wèn)題構(gòu)成中，其可作為算法函數(shù)的限定條件，為求解問(wèn)題進(jìn)行特殊性設(shè)定，計(jì)算中需依據(jù)不同客戶需求進(jìn)行算法調(diào)整，建立算法模型。其中客戶需求可總結(jié)如下：①確定客戶需求量。貨物需求量決定著車輛運(yùn)輸?shù)穆窂郊败囕v數(shù)目，其能夠決定車輛的實(shí)際算法設(shè)定。②貨物裝載需求。該需求決定著車輛的路徑，在交叉篩選中，可設(shè)定可裝載和不裝載兩種限定條件，并分別制定路線規(guī)劃，其中裝載的卸貨時(shí)間需計(jì)算在總體規(guī)劃內(nèi)容中。③客戶的時(shí)間窗需求。該需求決定著路線規(guī)劃問(wèn)題，可作為算法中的必要條件和優(yōu)先級(jí)，為路線整體算法進(jìn)行時(shí)間范圍限定。④多輛車服務(wù)需求。客戶有權(quán)利要求進(jìn)行單車?yán)滏溸\(yùn)輸服務(wù)，此種服務(wù)要求一定程度上增加了車輛的運(yùn)輸成本，但也會(huì)同樣減少多車服務(wù)的條件限定。

三、實(shí)例分析

1.實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)以某生鮮連鎖超市為載體，利用IFWGA 算法嘗試優(yōu)化超市的生鮮貨物物流配送路徑問(wèn)題，探究此種算法的優(yōu)化可行性。由于該生鮮連鎖超市根據(jù)GPS 導(dǎo)航地圖數(shù)據(jù)反饋，檢索出分店區(qū)域范圍，選定中點(diǎn)位置為配送中心，并模擬設(shè)定客戶需求及時(shí)間窗，根據(jù)市面上對(duì)于生鮮冷鏈的配送要求進(jìn)行配送，保證每日上午完成配送。因此，時(shí)間可限定為6：00-12：00 之間，并根據(jù)車容量實(shí)載情況，隨機(jī)生成需求量派單，貨物運(yùn)送的計(jì)數(shù)單位為噸。

2.實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中根據(jù)不同算法截取的不同結(jié)果路徑圖（圖1），分別代表著GA、FWA-EI、IFWGA 和FWGA 算法的結(jié)果路徑演示結(jié)果，且進(jìn)行了十次求解，便于進(jìn)行數(shù)據(jù)對(duì)比。

圖1 4種算法路徑圖

質(zhì)量結(jié)果對(duì)比分析可發(fā)現(xiàn)IFWGA 多次求解均獲得最優(yōu)解，相比GA、FWA-EI 和FWGA 結(jié)果都有明顯的優(yōu)化，僅一次略遜于FWGA 的運(yùn)行結(jié)果；總成本結(jié)果分析中（表2），IFWGA 比GA 優(yōu)化了39.8%，比FWA-EI 優(yōu)化了16.9%，比FWGA 優(yōu)化了16.2%，具有較大的成本控制優(yōu)勢(shì)。運(yùn)行時(shí)間對(duì)比可見(jiàn)表3。各算法的平均運(yùn)行時(shí)間如下：GA=54.38s；FWA-EI=76.23s；FWGA=65.72s；IFWGA=63.44s。IFWGA 運(yùn)行時(shí)間較FWGA 及FWA-EI 算法有明顯優(yōu)化效果，但卻比GA 運(yùn)行時(shí)間稍長(zhǎng)，但I(xiàn)FWGA 在實(shí)際運(yùn)行中的求解質(zhì)量高于其他算法。

表2 總成本對(duì)比

表3 運(yùn)行時(shí)間對(duì)比

四、結(jié)語(yǔ)

通過(guò)對(duì)遺傳算法進(jìn)行改進(jìn)，借助適應(yīng)度的調(diào)整及煙花算法的優(yōu)化，能夠通過(guò)上述函數(shù)總結(jié)出種群的最優(yōu)解，為實(shí)驗(yàn)尋求到最佳適應(yīng)度方案。通過(guò)時(shí)間結(jié)果對(duì)比分析，可發(fā)現(xiàn)傳統(tǒng)遺傳算法收效甚微，只能得出局部最優(yōu)解，且求得的質(zhì)量不高。而采用煙花算法對(duì)遺傳算法進(jìn)行改進(jìn)之后，能夠得到多數(shù)函數(shù)收斂，更具適應(yīng)性，可實(shí)現(xiàn)全局搜索能力和局部搜索能力的提升，增強(qiáng)算法的性能。

基于上述算法模型的改進(jìn)研究，將其應(yīng)用到物流運(yùn)輸領(lǐng)域中，可以有效的解決車輛路徑規(guī)劃問(wèn)題，為生鮮冷鏈的運(yùn)輸尋求到最佳運(yùn)輸路徑。通過(guò)將改進(jìn)后的遺傳算法應(yīng)用到冷鏈物流配送路徑優(yōu)化中，在容量約束條件下，若客戶未提出加急服務(wù)要求，可應(yīng)用此改進(jìn)算法進(jìn)行路線規(guī)劃；該算法的應(yīng)用能夠有效的為物流行業(yè)提供全新的配送思路，增強(qiáng)冷鏈運(yùn)送的服務(wù)質(zhì)量；并通過(guò)改進(jìn)算法應(yīng)用，為物流運(yùn)輸尋找到更加高效的配送方式，借助數(shù)據(jù)模型的計(jì)算，能夠快速為物流公司提供最佳配送路線，減少規(guī)劃路線的時(shí)間，減少運(yùn)輸成本，有助于提高物流冷鏈的收益。此外，此種路線上的優(yōu)化，能夠有效的增加客戶冷鏈運(yùn)送的滿意度，優(yōu)化客戶的消費(fèi)體驗(yàn)。