張立毅 ，費(fèi) 騰 ，劉 婷 ，張 錦

（1.天津商業(yè)大學(xué)信息工程學(xué)院，天津 300134；2.山西醫(yī)科大學(xué)第一醫(yī)院設(shè)備處，太原 030023）

應(yīng)急醫(yī)療器械物流是指在突發(fā)事件發(fā)生后，以向受災(zāi)點(diǎn)提供所需的醫(yī)療器械為目的，以時(shí)間最短化和配送效率最大化為目標(biāo)的一種特殊物流。應(yīng)急醫(yī)療器械物流不同于普通的物流，以時(shí)間最少為目標(biāo)。因?yàn)樵谕话l(fā)事件后，時(shí)間就是生命，到達(dá)受災(zāi)點(diǎn)的時(shí)間越早，生命財(cái)產(chǎn)損失就越少。

蟻群算法是一種仿生學(xué)算法，由意大利學(xué)者M(jìn).Dorigo等[1]提出，具有并行性、正反饋、魯棒性等特點(diǎn)，適用于求解復(fù)雜的組合優(yōu)化問題，已廣泛應(yīng)用于求解旅行商問題、分配問題、job-shop調(diào)度問題等，取得了較好的效果?；煦缡欠蔷€性動(dòng)力學(xué)系統(tǒng)在一定條件下所表現(xiàn)的一種運(yùn)動(dòng)形式，是系統(tǒng)處于非平衡過程中所呈現(xiàn)的隨機(jī)行為，產(chǎn)生混沌的機(jī)制往往又是簡單的非線性，是絲毫不帶隨機(jī)因素的固定規(guī)則[2]?；煦缢惴ㄗ鳛橐环N新型的搜索性算法，其基本思想是將混沌變量從混沌空間映射到解空間，然后利用混沌變量具有遍歷性、隨機(jī)性和規(guī)律性的特點(diǎn)進(jìn)行搜索[3]。

本文采用混沌蟻群算法（chaos ant colony optimization，簡稱CACO）來解決醫(yī)療器械應(yīng)急物流配送路徑優(yōu)化問題，并通過仿真驗(yàn)證了算法的有效性。

1 基本蟻群算法

1.1 蟻群算法的原理

在自然界中，螞蟻總是能夠找到洞穴與食物之間的最短距離。生物學(xué)家經(jīng)過研究發(fā)現(xiàn)，螞蟻利用一種稱為信息素（pheromone）的化學(xué)物質(zhì)作為媒介來進(jìn)行間接的信息傳遞，在尋找食物過程中，會(huì)在其經(jīng)過的路徑上釋放這種化學(xué)物質(zhì)，且能夠感知到信息素的強(qiáng)弱。螞蟻根據(jù)信息素的強(qiáng)度做出對較優(yōu)解的判斷選擇，蟻群的群體行為表現(xiàn)出一種信息正反饋現(xiàn)象，即后面的螞蟻會(huì)根據(jù)前面螞蟻所釋放的信息素選擇下一條路徑。一條路徑上的信息素越高，表明通過的螞蟻越多，被選擇的次數(shù)就越多，即該路徑的性能就好，從而導(dǎo)致后來螞蟻選擇該條路徑的概率增加。

1.2 蟻群算法的模型

隨著時(shí)間的推移，新的信息素加進(jìn)來，舊的信息素?fù)]發(fā)，ρ表示全局信息素的揮發(fā)因子，一般取值為[0，1）[4]，決定信息素?fù)]發(fā)的快慢。當(dāng)所有螞蟻完成一次周游后，各條路徑上的信息素為

式中：△τ（ijt）表示本次周游中路徑ij上的信息素增量，設(shè)初始時(shí)刻的 △τ（ij0）=0；△（t）表示第k只螞蟻在周游過程中釋放在路徑ij上的信息素，其值視螞蟻表現(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ù)式（4）選擇下一個(gè)要訪問的城市，螞蟻趨向于訪問具有較高信息素強(qiáng)度值的路徑。已經(jīng)去過的城市放入tabuk中，當(dāng)所有螞蟻完成了一次巡回后，由式（1）到式（3）更新每條路徑的信息素，反復(fù)上述過程，直到終止條件成立。

2 醫(yī)療器械應(yīng)急物流配送路徑優(yōu)化問題

2.1 問題描述

運(yùn)輸車輛從單一的醫(yī)療器械應(yīng)急配送中心出發(fā)，依次對多個(gè)需求點(diǎn)進(jìn)行應(yīng)急配送服務(wù)，要求每個(gè)需求點(diǎn)有且僅有一輛車輛通過，由于應(yīng)急車輛是從各地調(diào)配到應(yīng)急配送中心的，因此車輛在完成配送任務(wù)后，車輛不必再回到醫(yī)療器械應(yīng)急配送中心。該問題求解的目標(biāo)是尋求經(jīng)過醫(yī)療器械需求點(diǎn)的先后次序，用以求得運(yùn)行時(shí)間最小化。

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

為了方便模型建立，對醫(yī)療器械應(yīng)急物流配送路徑優(yōu)化問題作如下假設(shè)：

1）救援中心的車輛屬于同種車型，在配送中不考慮最大行駛距離及是否出現(xiàn)故障；

2）考慮車輛載重時(shí)，物資的體積不作考慮；

3）所有受災(zāi)點(diǎn)以及受災(zāi)點(diǎn)與救援中心之間都存在直線連接線路；

4）所有道路條件都是理想的，不考慮其對車輛速度的影響。

在此假設(shè)下，建立使配送時(shí)間最短的數(shù)學(xué)模型為

醫(yī)療器械應(yīng)急中心的坐標(biāo)是（x0，y0），有 l輛載重量為Q的配送車輛；現(xiàn)有n個(gè)需求點(diǎn)，其點(diǎn)坐標(biāo)分別為（xi，yi）（i=1，2，n），需求量為qi，所需救援物資必須在Ti前送達(dá)，受災(zāi)點(diǎn)i到受災(zāi)點(diǎn)j的距離為dij，行駛時(shí)間為tij。式（5）是模型的目標(biāo)函數(shù)，以配送時(shí)間最短為目標(biāo)。式（6）定義了車輛在需求點(diǎn)之間的行駛時(shí)間，v是在無道路障礙影響下的平均速度；式（7）保證了每輛車的裝載量不超過載重量；式（8）規(guī)定了每個(gè)需求點(diǎn)只能由一輛車來配送；式（9）和式（10）是變量wijk和變量φik之間的關(guān)系；式（11）是車輛到達(dá)需求點(diǎn)j所用的時(shí)間，ti是到達(dá)需求點(diǎn)i的時(shí)間，τi為卸貨時(shí)間；式（12）是車輛到達(dá)需求點(diǎn)i的時(shí)間約束，即不能滯后于時(shí)間 Ti；式（13）和式（14）是變量 wijk和 φik的定義式；式（15）是需求點(diǎn)i的卸貨時(shí)間是否算入總時(shí)間的判定。

3 混沌蟻群算法求解模型

由于受到自然界螞蟻行走的混沌特點(diǎn)和整個(gè)種群的自組織特點(diǎn)的啟發(fā)，利用混沌遍歷性等特點(diǎn)，將混沌擾動(dòng)算子引入蟻群算法中，能夠優(yōu)化搜索，有效彌補(bǔ)蟻群算法陷入局部最小、收斂速度慢等缺點(diǎn)[3]。

蟻群算法在進(jìn)行初始化時(shí)，各路徑上的信息素是相等的，螞蟻按照相同的概率選擇路徑，尋優(yōu)比較困難，因此收斂速度較慢?；煦缦伻核惴ɡ没煦邕\(yùn)動(dòng)的遍歷性進(jìn)行混沌初始化，選擇典型的混沌系統(tǒng)——Logistics映射作為混沌變量，迭代公式如下[5]

式中，μ 為控制參數(shù)，取值為[3.56，4][4]；當(dāng) μ =4、0≤Zij（0）≤1時(shí)，Logistics映射完全處于混沌狀態(tài)。利用全排列理論[4]，每一個(gè)混沌量對應(yīng)一條配送路徑，即每條路徑的信息素初始值根據(jù)混沌量而給出。

為了提高收斂速度，可事先確定一個(gè)閥值，以避免螞蟻周游一次后，較差解所帶來的無效搜索。同時(shí)，為避免蟻群算法陷入局部最小，在調(diào)整信息素時(shí)，引入混沌擾動(dòng)，用以跳出局部最小點(diǎn)。改進(jìn)后各條路徑上的信息素調(diào)整為

式中：Zij（t）是混沌變量，由式（16）迭代得到；q1為系數(shù)。

混沌蟻群算法求解模型的步驟：

Step1 令 NC=0（NC為迭代次數(shù)），load_bus=0（load_bus為車輛的負(fù)載），進(jìn)行參數(shù)初始化和混沌初始化；

Step2 將只螞蟻放在醫(yī)療器械應(yīng)急配送中心；

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

Step4 檢查tabuk是否滿。若為否，回到step3，否則，繼續(xù)step5；

Step5 計(jì)算目標(biāo)函數(shù)和Lk，記錄當(dāng)前的最好解；

Step6 對于Lk小于某一給定值的路徑，根據(jù)式（17）進(jìn)行信息素更新。

Step7 若 NC ＜ NCmax，NC=NC+1，清空 tabuk，回到step2。若NC=NCmax，結(jié)束。

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

假定醫(yī)療器械應(yīng)急配送中心的坐標(biāo)是（14.5，13.0），醫(yī)療器械應(yīng)急配送中心現(xiàn)有4輛車向20個(gè)醫(yī)療器械需求點(diǎn)運(yùn)送醫(yī)療器械。表1所示為各個(gè)醫(yī)療器械需求點(diǎn)的坐標(biāo)、結(jié)束時(shí)間、卸貨時(shí)間及需求量。每輛車的最大裝載量為8 t。汽車速度為45 km/h。文獻(xiàn)[6]中給出了參數(shù)α、β、ρ的設(shè)置依據(jù)。經(jīng)多次試驗(yàn)得出，當(dāng)α=1、β=5、ρ=0.6時(shí)，運(yùn)算結(jié)果最好?；煦缱兞縕ij（0）=0.5且q1=1。各個(gè)需求點(diǎn)之間以及需求點(diǎn)與醫(yī)療器械應(yīng)急配送中心之間的距離利用距離公式計(jì)算，即

表1 實(shí)驗(yàn)數(shù)據(jù)Tab.1 Data of experiments

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

混沌蟻群算法4條運(yùn)行路線分別為：0（醫(yī)療器械應(yīng)急配送中心）→18，0→5→14→4→3→17，0→7→8→19→9→12→2→10→1，0→20→11→6→13→16→15。

基本蟻群算法的4條運(yùn)行路線分別為：0→17，0→5→14→4→3→18，0→20→11→6→19→8→7→1，0→2→10→12→9→15→16→13。

圖3的仿真結(jié)果表明，在求解醫(yī)療器械應(yīng)急物流配送路徑優(yōu)化問題時(shí)，混沌蟻群算法所得的結(jié)果優(yōu)于基本蟻群算法。這是由于引入了混沌變量，克服了蟻群算法搜索時(shí)間過長的問題，有效地避免了搜索過程中陷入局部最優(yōu)。

5 結(jié)語

混沌蟻群算法由于引入了混沌變量，克服了蟻群算法過早收斂的問題，有效地避免了搜索過程中陷入局部最優(yōu)。在求解醫(yī)療器械應(yīng)急物流配送路徑優(yōu)化問題中，可以有效規(guī)劃配送路徑，獲得最短的配送時(shí)間。

[1]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．

[2]李 文．基于混沌優(yōu)化的混合優(yōu)化算法研究[D]．長沙：中南大學(xué)，2004．

[3]李 賓，蔣慰孫．混沌優(yōu)化方法及其應(yīng)用[J]．控制理論及其應(yīng)用，1997，14（4）：613-615．

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

[5]高 尚．旅行商問題的混沌蟻群算法[J]．系統(tǒng)工程理論與實(shí)踐，2005，8（9）：100-103．

[6]葉志偉，鄭肇葆．蟻群算法中參數(shù)設(shè)置的研究——以TSP問題為例[J]．武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，29（7）：597-601．