基于改進(jìn)蟻群算法的醫(yī)藥冷鏈物流運(yùn)輸路徑優(yōu)化

陳鑫影,朱子青,胡明捷

(大連交通大學(xué) 計(jì)算機(jī)與通信工程學(xué)院,遼寧 大連 116028)

目前,我國醫(yī)藥冷鏈物流運(yùn)輸仍處于初級(jí)發(fā)展階段,在基礎(chǔ)設(shè)施、冷鏈質(zhì)量控制標(biāo)準(zhǔn)等方面存在較多不足,尚未形成完整的醫(yī)藥冷鏈物流體系[1],因此,有不少學(xué)者開始研究如何改變這種現(xiàn)狀。Qi等[2]以應(yīng)急冷鏈物流資源調(diào)度最短時(shí)間為目標(biāo),構(gòu)建了應(yīng)急冷鏈物流調(diào)度模型。Zhang等[3]考慮到如何實(shí)現(xiàn)將綠色低能碳經(jīng)濟(jì)產(chǎn)品物流與現(xiàn)代綠色冷鏈物流體系優(yōu)化相結(jié)合,建立了模型。Xiong[4]考慮到傳統(tǒng)的算法優(yōu)化方法搜索的時(shí)間長(zhǎng),提出一種改進(jìn)蟻群優(yōu)化算法。Liu等[5]以節(jié)約綜合經(jīng)濟(jì)分析系統(tǒng)成本最低限度為系統(tǒng)設(shè)計(jì)主要目的,建立整數(shù)規(guī)劃模型。Zhang等[6]以配送成本最小、顧客滿意值最大為目標(biāo),進(jìn)行求解。Ning等[7]根據(jù)其提出新的信息素平滑,增強(qiáng)信息素加強(qiáng)機(jī)制構(gòu)建出新的蟻群算法。Luan等[8]將蟻群和遺傳算法融合,解決供應(yīng)商選擇問題。Yue等[9]將懲罰策略融入蟻群算法,以解決無人汽車路徑規(guī)劃問題。Li等[10]將GA與TS算法相結(jié)合,解決了所提出的選址路由問題。Wang等[11]設(shè)計(jì)了一款基于啟發(fā)式規(guī)則的混合GA算法求解以最小成本為目標(biāo)的函數(shù)。Zhu等[12]以再次生成停止進(jìn)化粒子為目標(biāo),改進(jìn)了粒子群算法。Ba等[13]在需求不定的緊急情況下建立了具有時(shí)間窗的物流配送模型。

以上研究在路徑優(yōu)化模型方面取得了一定進(jìn)展,但并沒考慮到預(yù)冷環(huán)節(jié)對(duì)總成本的影響,這在一定程度上影響了最優(yōu)路徑的求解。為使總成本更加合理化,本文構(gòu)建了醫(yī)藥冷鏈配送路徑優(yōu)化模型,包括車輛的固定、運(yùn)輸、懲罰、貨損、碳排放以及制冷成本,同時(shí)采用基于遺傳算法改進(jìn)的蟻群優(yōu)化算法(Improved Ant Colony Optimization Algorithm Based On Genetic Algorithm, IGACO)對(duì)該模型進(jìn)行求解。由于IACO算法[4]存在收斂速度較慢以及易陷入局部最優(yōu)的問題,本文在原算法基礎(chǔ)上加入輪盤賭規(guī)則、單點(diǎn)交叉操作、變異因子,保證IGACO可以搜索的范圍更廣、收斂速度更快,最后通過仿真試驗(yàn)證明了IGACO算法的有效性。

1 模型約束條件

本文所提出醫(yī)藥冷鏈物流運(yùn)輸路徑優(yōu)化模型的問題描述如下:

(1)

(2)

(3)

(4)

(5)

其對(duì)應(yīng)的約束條件為:

qi≥0,?i∈V

(6)

eti≤Ati≤lti,i∈n

(7)

eti-Ati>0, ?i∈V

(8)

lti-Ati<0, ?i∈V

(9)

式中:式(1)為車輛從配送點(diǎn)出發(fā)服務(wù),完成后返回配送點(diǎn);式(2)為每個(gè)用戶只可接受一個(gè)車的服務(wù);式(3)為配送中心的車輛數(shù)有限,上限值為J;式(4)為路線客戶總需求小于車輛自身載重上限;式(5)為決策變量,值為0或1;式(6)為客戶需求量不得為負(fù);式(7)為時(shí)間窗要求;式(8) 、式(9)為車輛或早或晚到達(dá)配送地。

2 數(shù)學(xué)模型的建立

在追求低碳大環(huán)境下,本文不僅將碳排放考慮進(jìn)模型中,同時(shí)還將所需使用制冷劑的每個(gè)環(huán)節(jié)細(xì)化,從而構(gòu)成改進(jìn)后的制冷成本,以下為改進(jìn)后的冷鏈配送路徑模型組成。

2.1 固定成本

固定成本費(fèi)用包括但卻不僅僅局限在司機(jī)工資、車輛的磨損、折舊費(fèi)等,因此固定成本C1可定義為:

(10)

2.2 運(yùn)輸成本

運(yùn)輸成本指車輛在實(shí)際配送服務(wù)過程中所產(chǎn)生的所有相關(guān)費(fèi)用,包括但不局限于行駛中產(chǎn)生的燃油消耗以及車輛維修費(fèi)用等,因此運(yùn)輸成本C2可定義為:

(11)

式中:Wc代表每單位重量運(yùn)費(fèi)價(jià)格;dij為客戶i到j(luò)的距離;qi為客戶需求量。

2.3 懲罰成本

懲罰成本隨客戶的滿意度呈線性變化,同時(shí)滿意度被定義為配送車輛響應(yīng)客戶需求所需時(shí)間的度量,若在客戶期望時(shí)間中,滿意度則為最高?？蛻舻钠谕麜r(shí)間周期為[eti,lti],且每個(gè)客戶都有自己?jiǎn)为?dú)的時(shí)間窗要求,因此懲罰成本C3可定義為:

(12)

式中:Ati表示車輛配送到達(dá)時(shí)間;n為客戶數(shù)量,配送的客戶滿意度總值設(shè)為100;ε1、ε2代表早到、晚到對(duì)時(shí)間的窗敏感度。

2.4 碳排放成本

冷鏈配送車輛所產(chǎn)生的碳排放主要包括兩個(gè)方面,首先是車輛行駛過程中燃油消耗所產(chǎn)生的碳排放,其次就是車輛的制冷設(shè)備所產(chǎn)生的碳排放。車輛的燃油消耗所產(chǎn)生的碳排放量與車輛自身裝載重量以及配送距離的遠(yuǎn)近相關(guān)。當(dāng)車輛裝載量為X時(shí),燃油消耗由e(X)表示,因此e(X)可表示為:

(13)

式中:Q為車輛滿載重量;e*為滿載時(shí)燃油消耗量;e0為空載時(shí)燃油消耗量。

有裝載的配送車在行駛過程中所產(chǎn)生的碳排放量,E1可表示為:

(14)

式中:CA為二氧化碳排放系數(shù);dij為行駛距離;vij為車輛從i到j(luò)的行駛速度。

制冷設(shè)備所產(chǎn)生的碳排放量E2與載重、車輛行駛距離也有密切關(guān)系,可表示為:

(15)

式中:F為制冷設(shè)備所產(chǎn)生的碳排放。因此,總碳排放成本C4可表示為:

(16)

式中:c0為每單位碳稅價(jià)格。

2.5 貨損成本

貨損成本主要包含以下幾個(gè)部分:在裝載貨物之前,應(yīng)當(dāng)將制冷設(shè)備進(jìn)行預(yù)冷,以達(dá)到提前降低貨艙溫度的目的,從而降低貨物因過高溫度而導(dǎo)致的損壞。同時(shí),設(shè)備預(yù)冷時(shí)間、卸載貨物時(shí)間與貨損成本有直接關(guān)系,本文設(shè)置一個(gè)腐敗率函數(shù):

R(t)=R0K-θt

(17)

式中:R0為貨物初始狀態(tài)時(shí)的質(zhì)量;t為車輛配送貨物所需要的時(shí)間;θ為貨物質(zhì)量對(duì)溫度的敏感系數(shù);K為產(chǎn)品在某個(gè)衡定溫度下變質(zhì)的常規(guī)速率。因此,貨損成本可表示為:

(18)

式中:t0表示的是車輛出發(fā)時(shí)的時(shí)間點(diǎn);t1為車輛到達(dá)目的地的時(shí)間點(diǎn);θ為進(jìn)行預(yù)冷后貨物質(zhì)量對(duì)溫度的敏感系數(shù);θ1為卸貨過程中貨物對(duì)溫度的敏感系數(shù);q1為每件貨物的單價(jià);tj為卸貨時(shí)間。

2.6 制冷成本

制冷成本是冷鏈配送過程中配送車輛消耗制冷劑的成本,包括車輛提前預(yù)冷以及配送過程中制冷所產(chǎn)生的制冷劑消耗的費(fèi)用總和。預(yù)冷操作時(shí)產(chǎn)生的制冷費(fèi)用C61、運(yùn)輸過程中固定產(chǎn)生的制冷費(fèi)用C62以及卸貨過程中產(chǎn)生的制冷費(fèi)用C63可表示為:

(19)

(20)

(21)

(22)

(23)

(24)

C6=C61+C62+C63

(25)

綜上所述,冷鏈物流配送優(yōu)化路徑的總成本目標(biāo)函數(shù)可表示為:

Z=Min(C1+C2+C3+C4+C5+C6)

(26)

3 基于遺傳算法改進(jìn)的蟻群優(yōu)化算法(IGACO)

本文將Xiong等[4]所提出的IACO算法中的啟發(fā)式因子放置于ACO算法中,并與遺傳算法相結(jié)合,使用改進(jìn)后的ACO算法作為基礎(chǔ)解,在此基礎(chǔ)上進(jìn)行單點(diǎn)交叉算子的操作,并將輪盤賭策略加入其中,這種方式可以擴(kuò)大搜索范圍,從而達(dá)到篩選出不同適應(yīng)度值的解,最后對(duì)適應(yīng)度較低的解集,進(jìn)一步進(jìn)行變異操作,直到所有解集都達(dá)到理想的適應(yīng)度值。通過遺傳算法的獨(dú)有特性,進(jìn)而提高改進(jìn)蟻群算法全局搜索能力,從而有效避免了過早陷入局部搜索最優(yōu)化,同時(shí)進(jìn)一步加快了算法全局的搜索收斂速度。

3.1 交叉變異策略

采取交叉操作有助于將優(yōu)良的染色體傳給下一代,同時(shí)起到全局搜索作用,減少局部最優(yōu)可能,例如將來自兩條不同的組合在隨機(jī)選擇位置進(jìn)行分割,并交換右側(cè)部分的元素,從而得到全新的組合,見圖1。

圖1 單點(diǎn)交叉演示圖

采取變異操作對(duì)算法尋優(yōu)與算法進(jìn)化有著非常重要的作用,若當(dāng)算法陷入局部最優(yōu)時(shí),采取變異的操作,可以跳出局部的最優(yōu)算法時(shí),變異的操作則是直接將染色體序列中的某一部分進(jìn)行隨機(jī)變異,對(duì)適應(yīng)度較高的地區(qū)加強(qiáng)搜索,同時(shí)對(duì)適應(yīng)度較低的部分繼續(xù)進(jìn)行變異操作,直到達(dá)到給定的適應(yīng)度閾值,從而終止變異操作。此操作在一定程度上增加了選擇的可能性,從而進(jìn)一步防止算法過早陷入局部最優(yōu)狀態(tài),同時(shí)提高了算法的收斂度。

在信息素更新策略中,加入一個(gè)不斷變化的隨機(jī)函數(shù)q*,該參數(shù)將在給定的迭代范圍內(nèi)隨機(jī)變化,從而增加選擇多樣性?；谝陨喜呗?蟻群算法信息素濃度更新將更改為:

(27)

(28)

(29)

啟發(fā)式因子為:

用戶檢索后，進(jìn)入二級(jí)目錄，網(wǎng)頁左側(cè)為數(shù)據(jù)庫分類，右側(cè)為該數(shù)據(jù)庫中包含的檢索結(jié)果，此種設(shè)計(jì)可提高用戶的檢索效率，如圖3所示。

(30)

式中:Li為螞蟻已經(jīng)到達(dá)i點(diǎn)的距離總長(zhǎng);dij為地點(diǎn)i到地點(diǎn)j的距離;djp為將來走過各點(diǎn)之間的距離。

綜上所述,基于遺傳算法改進(jìn)的蟻群算法可表示為:

(31)

3.2 IGACO算法流程

IGACO算法具體操作步驟如下:

步驟一:對(duì)算法初始解進(jìn)行構(gòu)建,并將此解作為算法初始解集。

步驟二:對(duì)初始解進(jìn)行適應(yīng)度值的求解,并根據(jù)適應(yīng)度設(shè)置范圍篩選適應(yīng)度較高的解。

步驟三:對(duì)信息素值進(jìn)行更新,同時(shí)定義信息素矩陣,將矩陣中的信息素進(jìn)行更新,并更新解向量,最后判斷是否達(dá)到算法設(shè)定迭代次數(shù),若沒達(dá)到,返回步驟二,若達(dá)到則進(jìn)行下一步。

步驟四:將信息素矩陣進(jìn)行輸出,并進(jìn)行交叉、變異操作。進(jìn)行完交叉、變異后對(duì)矩陣進(jìn)行拆解,最后判斷是否滿足算法終止條件,若滿足則輸出最優(yōu)解,若不滿足則繼續(xù)進(jìn)行此步驟。

圖2 IGACO算法流程圖

4 試驗(yàn)設(shè)置與分析

本文分析了IGACO算法解決改進(jìn)冷鏈模型的性能。IGACO的相關(guān)試驗(yàn)參數(shù)設(shè)置:螞蟻數(shù)量為30只,迭代次數(shù)為500次,信息素蒸發(fā)量設(shè)置為0.2,信息素強(qiáng)度設(shè)置為l×108,交叉概率設(shè)置為0.8,變異概率設(shè)置為0.1。

改進(jìn)模型參數(shù)見表1。

表1 模型相關(guān)的參數(shù)

4.1 收斂度對(duì)比

使用本文所提出的IGACO算法與現(xiàn)有的IACO算法、ACO算法、GA算法做試驗(yàn)對(duì)比,從對(duì)比結(jié)果可以看出IGACO算法的收斂速度更快,可以看出IGACO相對(duì)其他算法更具優(yōu)勢(shì),算法收斂度對(duì)比如圖3所示。可知,IGACO算法迭代數(shù)為在187次時(shí),就已經(jīng)達(dá)到最優(yōu)狀態(tài),而IACO算法、ACO算法、GA算法迭代數(shù)分別于第249、385、439次時(shí)才達(dá)到最優(yōu)狀態(tài)。

圖3 算法收斂度對(duì)比

4.2 行走路徑對(duì)比

本文通過四種算法,對(duì)試驗(yàn)數(shù)據(jù)集進(jìn)行求解,并繪制車輛配送路線圖見圖4～圖7,可知IGACO算法配送路線所用成本相較于其余3種算法更低。

圖4 IGACO算法路徑圖

圖4試驗(yàn)共使用9輛車,對(duì)30個(gè)收貨點(diǎn)進(jìn)行產(chǎn)品配送,驗(yàn)證配送所用成本。每輛車配送路線分別為:0→19→10→29→0,0→13→21→5→22→0,0→15→20→9→0,0→4→24→26→7→0,0→16→23→28→27→0, 0→18→6→0, 0→1→3→23→0, 0→25→2→14→0,0→8→30→12→17→0。

圖5試驗(yàn)共使用9輛車對(duì)30個(gè)收貨點(diǎn)進(jìn)行產(chǎn)品配送,驗(yàn)證配送所用成本。每輛車配送路線分別為: 0→18→11→17→22→0,0→10→2→19→0,0→16→9→0, 0→25→3→23→24→27→0, 0→26→24→1→30→12→0,0→13→21→15→0, 0→7→8→29→28→0,0→4→20→0,0→6→5→0。

圖5 IACO算法路徑圖

圖6試驗(yàn)共使用9輛車對(duì)30個(gè)收貨點(diǎn),進(jìn)行產(chǎn)品配送,驗(yàn)證配送所用成本。每輛車配送路線分別為:0→25→12→23→3→11→0,0→13→7→14→0,0→16→5→0, 0→17→1→10→29→0,0→21→15→0,0→28→8→0,0→2→24→4→20→23→0,0→18→27→26→22→0,0→19→9→6→0。

圖6 ACO算法路徑圖

圖7試驗(yàn)共使用9輛車對(duì)30個(gè)收貨點(diǎn)進(jìn)行產(chǎn)品配送,驗(yàn)證配送所用成本。每輛車配送路線分別為:0→13→15→20→21→0,0→5→11→4→0,0→28→23→0,0→9→6→27→12→0,0→16→22→8→0,0→14→10→24→26→2→0,0→18→30→1→0,0→29→17→25→3→0,0→7→19→0。

以上 4 種算法中,IGACO、IACO、ACO、GA 算法求解模型總成本分別為 5 661.460 4、 5 940.018 5、6 636.764 5、 7 281.553 5 元。IGACO算法在總成本方面,較IACO、ACO、GA算法分別減少了4.9%、17.2%、28.6%。

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

分別對(duì)IGACO算法、IACO算法、ACO算法、GA算法進(jìn)行運(yùn)行時(shí)間對(duì)比,每種算法均運(yùn)行6次,對(duì)比結(jié)果見表2。

表2 4種算法運(yùn)行時(shí)間對(duì)比 s

由表2可以看出, IGACO算法較ACO算法、GA算法、IACO算法分別提高了4.57、4.84、0.74 s,IGACO算法從運(yùn)行時(shí)間上看是有提升的。

5 結(jié)論

本文對(duì)醫(yī)藥冷鏈物流運(yùn)輸成本模型進(jìn)行改進(jìn),在制冷成本中加入預(yù)冷參數(shù),使制冷成本的組成因素更加合理化,同時(shí)提出的IGACO算法對(duì)傳統(tǒng)蟻群算法啟發(fā)式因子進(jìn)行改進(jìn),并將解作為基礎(chǔ)解加上遺傳算法中的交叉操作以及變異因子,從而擴(kuò)大算法搜索范圍,進(jìn)一步避免算法陷入局部最優(yōu)的可能。試驗(yàn)發(fā)現(xiàn),在運(yùn)行速度、總成本計(jì)算、迭代次數(shù)方面,IGACO算法均優(yōu)于其他幾種對(duì)比算法,具有較好的優(yōu)越性和可靠性。

本文在某些方面考慮的并不是很充足,在今后工作中,冷鏈運(yùn)輸模型參數(shù)可能會(huì)得到一定程度上的優(yōu)化,隨著研究的繼續(xù)深入,新的算法模型或許也將考慮引進(jìn)新的因子,以使算法效率進(jìn)一步提升,本文沒有將多目標(biāo)作為最終的求解目標(biāo),這將是下一個(gè)研究目標(biāo)。