免疫蟻群算法在常規(guī)醫(yī)療器械配送路徑優(yōu)化中的應(yīng)用

費(fèi) 騰,張立毅,韓應(yīng)征,張 錦

(1.太原理工大學(xué)信息工程學(xué)院,太原 030024;2.天津商業(yè)大學(xué)信息工程學(xué)院,天津 300134)

0 引 言

近年來,隨著醫(yī)療事業(yè)的蓬勃發(fā)展,醫(yī)療器械的需求也隨之增加,使得醫(yī)療器械物流成為物流產(chǎn)業(yè)的重要組成部分。但由于我國醫(yī)療器械物流相對(duì)于西方發(fā)達(dá)國家起步較晚,尤其是醫(yī)療器械作為一種特殊物品,目前既缺乏專業(yè)性的物流隊(duì)伍,也缺乏科學(xué)規(guī)范的物流管理。如何快速有效、安全經(jīng)濟(jì)地配送醫(yī)療器械是目前醫(yī)療器械物流的研究重點(diǎn)和熱點(diǎn)。

本文將免疫蟻群算法(Immune Ant Colony Optimization,IACO)應(yīng)用于常規(guī)醫(yī)療器械物流配送的路徑優(yōu)化中,以合理調(diào)度車輛,獲得最短路徑,減少配送成本,降低患者負(fù)擔(dān)。

1 醫(yī)療器械物流配送路徑優(yōu)化模型

為了方便模型建立,對(duì)常規(guī)醫(yī)療器械物流配送的路徑優(yōu)化問題作如下假設(shè):

(1)僅考慮位置已知的單一醫(yī)療器械配送中心,所有配送車輛起點(diǎn)和終點(diǎn)均是醫(yī)療器械配送中心。

(2)車輛運(yùn)輸?shù)尼t(yī)療器械可以混裝,且每個(gè)醫(yī)療器械需求點(diǎn)所需要的醫(yī)療器械不超過車輛的最大載重量。

(3)每個(gè)醫(yī)療器械需求點(diǎn)的位置和需求量都已知,其需求由且僅由一輛車一次送貨滿足。

(4)車輛的載重量已知。

(5)車輛對(duì)每個(gè)醫(yī)療器械需求點(diǎn)服務(wù),途中只有卸貨而無裝貨的情況。

在上述基本假設(shè)的前提下,以配送成本為最小,構(gòu)造配送路徑的目標(biāo)函數(shù)為[1]

式中,L為醫(yī)療器械需求點(diǎn)的個(gè)數(shù);c0為出車的單位成本;m′為車輛數(shù);c為車輛行駛距離的單位成本;dij(i,j=0,1,2,…,L)為醫(yī)療器械需求點(diǎn) i與醫(yī)療器械需求點(diǎn) j點(diǎn)之間的距離;c1為超載懲罰系數(shù);g1為第 i個(gè)醫(yī)療器械需求點(diǎn)的需求量;q為車輛的最大載重量;k(k=1,2,…,m′)為車輛的編號(hào)。

將醫(yī)療器械配送中心編號(hào)為 0,醫(yī)療器械需求點(diǎn)編號(hào)為 1、2、3、…、L,定義變量 xijk、yki為

式(1)包括3部分,第一項(xiàng)為車輛的固定成本,第二項(xiàng)是車輛的運(yùn)輸成本,第三項(xiàng)是超載懲罰成本。式(2)與式(8)為約束條件;式(2)表示車輛在運(yùn)輸過程中,對(duì)任何一輛車而言,所裝醫(yī)療器械的總重量不會(huì)超過其車輛本身的最大載重量;式(3)、式(4)和式(5)保證每個(gè)醫(yī)療器械需求點(diǎn)有且僅有一輛車通過;式(6)表示第 j需求點(diǎn)的任務(wù)由第 k輛車完成時(shí),車輛 k從需求點(diǎn) j行駛到需求點(diǎn)j;式(7)表示第 i需求點(diǎn)的任務(wù)由第k輛車完成時(shí),車輛 k從需求點(diǎn) j行駛到需求點(diǎn) i;式(8)保證了所有車輛從醫(yī)療器械配送中心出發(fā),最后回到醫(yī)療器械配送中心。

2 蟻群算法

蟻群算法是一種仿生學(xué)算法,由意大利學(xué)者M(jìn).Dorigo[2]等人提出。設(shè)有 n座城市,任意兩座城市 i、j之間的距離為 dij(i,j=1,2,…,n),bi(t)表示t時(shí)刻位于城市 t的螞蟻個(gè)數(shù),蟻的總數(shù),τij(t)表示 t時(shí)刻支路 ij上的信息素量,在 t=0時(shí)刻,各條路徑上的信息量強(qiáng)度相等。Δτij(t)=C(C為常數(shù))。

隨著時(shí)間的推移,新的信息素加進(jìn)來,舊的信息素要揮發(fā),設(shè) ρ為信息素的揮發(fā)因子,一般取值為[0,1][3],表征信息素的揮發(fā)快慢。當(dāng)所有螞蟻完成一次周游后,各條路徑上的信息素為

Δτij(t)表示本次周游中路徑 ij上的信息素增量 ,初始時(shí)刻,Δτij(0)=0;Δτkij(t)表示第k只螞蟻在周游過程中釋放在路徑上的信息素,其值視螞蟻表現(xiàn)的優(yōu)劣程度而定。路徑越短釋放的信息素就越多。

式中,Q為常數(shù),Lk表示本次周游第k只螞蟻所形成的回路長度。螞蟻k在周游時(shí)由城市 i向城市 j的轉(zhuǎn)移概率 pkij為

其中,allowedk=(1,2,…,n)-tabuk表示螞蟻 k當(dāng)前能選擇的城市集合;tabuk(k=1,2,…,m)表示第 k只螞蟻的禁忌表,記錄螞蟻 k已經(jīng)經(jīng)過的城市,用來說明螞蟻的記憶性。ηij(t)為啟發(fā)函數(shù),表示由城市 i轉(zhuǎn)移到城市 j的期望程度,一般取ηij(t)=1/dij。α為路徑 ij上殘留信息的重要程度,β為啟發(fā)信息的重要程度。

蟻群算法基本運(yùn)行過程:m只螞蟻同時(shí)從某個(gè)城市出發(fā),根據(jù)式(12)選擇下一個(gè)要訪問的城市,螞蟻趨向于訪問具有較高信息素強(qiáng)度量的路徑。已經(jīng)去過的城市放入 tabuk中,當(dāng)所有的螞蟻完成了一次巡回后,由式(9)到式(11)更新每條路徑的信息素,反復(fù)上述過程,直到終止條件成立。

3 免疫蟻群算法求解模型

免疫算法具有快速隨機(jī)的全局搜索能力,但對(duì)于系統(tǒng)中的反饋信息利用不足,當(dāng)求解到一定范圍時(shí)往往做大量無為的冗余迭代,求解效率低;而蟻群算法具有分布式并行搜索能力,通過信息量的積累和更新收斂于最優(yōu)路徑上,但其初期信息素匱乏,求解速度較慢。[4]免疫算法和蟻群算法相結(jié)合的免疫蟻群算法不僅體現(xiàn)了免疫算法的自適應(yīng)性、多樣性、全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn),而且有效克服了蟻群算法搜索時(shí)間長、易陷入停滯等缺點(diǎn)。免疫蟻群算法首先利用免疫算法尋找可行的較優(yōu)解,利用尋找出的較優(yōu)解產(chǎn)生信息素的初始值,然后再利用蟻群算法求解,從而縮短了搜索時(shí)間。

(1)抗體的編碼

把目標(biāo)函數(shù)和約束條件作為抗原,抗體采用自然編碼方式,利用需求點(diǎn)直接排列方法。[5]

隨機(jī)產(chǎn)生 L個(gè)需求點(diǎn)的全排列(i=1,2,…,m1-1,m1,…,n1-1,n1,…,L)若q,則將 m1至 L逐個(gè)后移一位,將 0插入第 m1位。若q,則將 n1至L逐個(gè)后移一位。將0插入第 n1位。按照這樣的方法繼續(xù),直至將 m′(m′為車輛數(shù))個(gè) 0全部插入到相應(yīng)位置。這樣就形成了一條長度為 L+m′+1的初始抗體

車輛 1從配送中心 0出發(fā),服務(wù)需求點(diǎn) 1到需求點(diǎn)m1-1,然后返回配送中心0,形成子路線1;車輛 2從配送中心0出發(fā),服務(wù)需求點(diǎn)m1到需求點(diǎn)n1-1,然后返回配送中心 0,形成子路線 2。以此類推,形成子路線。

(2)親和力函數(shù)

1)抗體和抗原之間的親和力

抗體和抗原之間的親和力表示抗體與抗原之間的匹配程度?？贵w s和抗原之間的親和力由配送路徑的目標(biāo)函數(shù) Z(s)變換而成,即

2)抗體和抗體之間的親和力 Bs,t

抗體和抗體之間的親和力表示抗體與抗體之間的匹配程度和抗體與抗體之間的相似程度,采用基于配送路徑的目標(biāo)函數(shù)差的方法將抗體 s與抗體 t之間的親和力定義為

(3)產(chǎn)生新的抗體

采用選擇、交叉、變異三個(gè)操作用以產(chǎn)生新的抗體。

1)選擇操作

選擇操作的目的是為了把優(yōu)質(zhì)的個(gè)體直接傳到下一代或通過交叉配對(duì)產(chǎn)生新的個(gè)體再傳到下一代。選擇操作選用輪盤賭選擇[5]的方法,按照一定的淘汰概率淘汰一部分劣質(zhì)的個(gè)體。

2)交叉操作

交叉操作的作用是從當(dāng)前種群中選出優(yōu)良個(gè)體作為父代以繁殖下一代。交叉操作可分為兩個(gè)步驟:第一步是將新復(fù)制產(chǎn)生的匹配的抗體隨機(jī)兩兩匹配,第二步進(jìn)行交叉繁殖。

3)變異操作

變異操作采用反轉(zhuǎn)變異,即在個(gè)體編碼中,隨機(jī)選擇兩點(diǎn)(兩點(diǎn)之間稱為反轉(zhuǎn)區(qū)域),再將反轉(zhuǎn)區(qū)域按反序插入到原來位置中即完成反轉(zhuǎn)變異操作。[5]

(4)免疫蟻群算法求解模型步驟

Step 1輸入代價(jià)函數(shù)和約束條件確定抗原。

Step 2對(duì)抗體進(jìn)行編碼,產(chǎn)生初始抗體。

Step 3計(jì)算抗體和抗原之間的親和力以及抗體和抗體之間的親和力。

Step 4進(jìn)行選擇、交叉、變異產(chǎn)生新的抗體,從而產(chǎn)生可行的較優(yōu)解,產(chǎn)生信息素的初始值 。

Step 5令NC=0(NC為迭代次數(shù)),load bus=0(load bus為車輛的負(fù)載),初始化參數(shù)。

Step 6將 m只螞蟻都放在醫(yī)療器械配送中心。

Step 7根據(jù)式(12)計(jì)算螞蟻 k的轉(zhuǎn)移概率,選擇并移動(dòng)到下一個(gè)城市 j,同時(shí)將 j加入到 tabuk。檢查車輛的負(fù)載是否達(dá)到最大載重。若達(dá)到,返回醫(yī)療器械配送中心。

Step8 tabuk是否滿。若為否,回到 step 7,否則 ,繼續(xù) step 9。

step 9計(jì)算目標(biāo)函數(shù),記錄當(dāng)前的最好解,進(jìn)行信息素更新。初始時(shí)刻的信息素由式(15)決定。

step 10若 NC

4 實(shí)驗(yàn)仿真

假定醫(yī)療器械配送中心的坐標(biāo)是(14.5,13.0),醫(yī)療器械配送中心需要向 20個(gè)醫(yī)療器械需求點(diǎn)運(yùn)送醫(yī)療器械。表 1所示為各個(gè)醫(yī)療器械需求點(diǎn)的坐標(biāo)及需求量。每輛車的最大裝載量為 8噸。仿真時(shí),令 c0=0,則費(fèi)用只與車輛運(yùn)行路程有關(guān)。令單位路程的代價(jià) c=1,則費(fèi)用與運(yùn)行長度相等,即車輛運(yùn)行 1個(gè)單位距離,費(fèi)用就增加一元。超載懲罰系數(shù) c1=1。文獻(xiàn)[6]中給出了對(duì) α、β、ρ設(shè)置的研究結(jié)果,經(jīng)過多次試驗(yàn),當(dāng) α=1、β=5、ρ=0.6時(shí),運(yùn)算結(jié)果最好。各醫(yī)療器械需求點(diǎn)之間以及各醫(yī)療器械需求點(diǎn)與醫(yī)療器械配送中心的距離,利用距離公式計(jì)算,即

運(yùn)輸車輛數(shù)為

式中[·]表示取整,λ∈ (0,1),可根據(jù)裝車的復(fù)雜性及約束多少調(diào)整,一般裝車越復(fù)雜,λ越小,反之則越大。[7]

由于各個(gè)醫(yī)療器械需求點(diǎn)的總需求量為 23.7噸,根據(jù)式(17),取 λ=0.98,故需車輛數(shù)為

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

圖 1所示為基本蟻群算法的一次最優(yōu)解的運(yùn)行路線。圖 2所示為免疫蟻群算法的一次最優(yōu)解的運(yùn)行路線。圖 3所示為免疫蟻群算法與基本蟻群算法在相同運(yùn)行環(huán)境下的一次最優(yōu)解尋優(yōu)曲線。

圖1 基本蟻群算法一次最優(yōu)解路線圖

實(shí)驗(yàn)仿真表明,免疫蟻群算法的收斂速度高于基本蟻群算法,因而免疫蟻群算法有效地縮短了搜索時(shí)間。

5 結(jié)束語

本文將免疫蟻群算法用于常規(guī)醫(yī)療器械配送路徑優(yōu)化中。實(shí)驗(yàn)仿真表明,該算法在一般醫(yī)療器械配送的路徑優(yōu)化問題中,具有全局尋優(yōu)能力,收斂速度快等優(yōu)點(diǎn),為解決常規(guī)醫(yī)療器械配送路徑的優(yōu)化提出了一條新的思路。

[1] 朱樹人,李文彬,匡芳君.一種帶軟時(shí)間窗的物流配送路徑優(yōu)化遺傳算法[J].計(jì)算機(jī)工程與科學(xué),2005,27(12):108-110.

[2] Dorigo M.Ant Colony System:A Cooperative Learning approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[3] 劉立東.改進(jìn)蟻群優(yōu)化算法的研究[D].成都:西南交通大學(xué),2005.

[4] 梁嘯.基于蟻群和免疫組合算法的物流配送路徑優(yōu)化問題的研究[D].吉林:吉林大學(xué),2007.

[5] 閆旺.基于免疫算法的物流配送車輛優(yōu)化調(diào)度研究[D].西安:長安大學(xué),2005.