基于改進(jìn)遺傳算法的血液保障車(chē)輛應(yīng)急調(diào)度優(yōu)化研究

張澤瑞，段德光，李 昊，陶學(xué)強(qiáng)，鹿國(guó)偉，陳 恩

（1．軍事科學(xué)院系統(tǒng)工程研究院衛(wèi)勤保障技術(shù)研究所，天津 300161；2．西寧聯(lián)勤保障中心藥品儀器監(jiān)督檢驗(yàn)站，蘭州 730050）

0 引言

21世紀(jì)以來(lái)我國(guó)頻繁遭受自然災(zāi)害，諸如汶川、玉樹(shù)地震和舟曲泥石流等災(zāi)害事件給人民群眾的生命安全造成了巨大損失，特別是汶川地震，累計(jì)死亡69000余人，受傷374000余人[1-2]。應(yīng)急血液保障是災(zāi)害醫(yī)學(xué)救援工作中非常重要的環(huán)節(jié)[3]，充足且快速的血液供給是挽救災(zāi)區(qū)傷員生命、提高傷員救治率的重要保證，軍隊(duì)血站及其血液保障車(chē)輛在災(zāi)后應(yīng)急血液保障中發(fā)揮了重要作用，得到了實(shí)戰(zhàn)檢驗(yàn)[4-6]。

車(chē)輛應(yīng)急調(diào)度屬于典型的車(chē)輛路徑問(wèn)題（vehicle routing problem，VRP），基于其 NP-hard性質(zhì)，啟發(fā)式智能算法相較于精確算法更為適用，而遺傳算法具有智能性、并行性、良好的魯棒性等特點(diǎn)[7-8]，被廣泛運(yùn)用于VRP求解。傳統(tǒng)遺傳算法融合改進(jìn)策略是提升算法求解效率的主要方式，宋英華等[9]設(shè)計(jì)了一種加權(quán)遺傳算法求解以配送時(shí)間懲罰成本和駕駛員心理成本最小化的雙目標(biāo)車(chē)輛調(diào)度模型；Abbasi等[10]提出并行化遺傳算法用于加快智能交通系統(tǒng)中復(fù)雜VRP的求解。遺傳算子的選擇是影響遺傳算法性能的重要因素，Chaiy等[11]提出一種全新的多點(diǎn)交叉算子求解旅行商問(wèn)題；Wang等[12]簡(jiǎn)化編解碼方式，采用路徑復(fù)制交叉算子和基于衛(wèi)星選擇的變異算子用于遺傳算法的改進(jìn)。多種類(lèi)智能算法結(jié)合是近年來(lái)算法改進(jìn)的熱點(diǎn)方向，辜勇等[13]將蟻群算法與遺傳算法結(jié)合，使算法收斂速度得到了提高，解的質(zhì)量得到了優(yōu)化；Ariyani等[14]融合遺傳算法的全局搜索優(yōu)勢(shì)和模擬退火算法的局部搜索優(yōu)勢(shì)用于提升算法的搜索效率。以上算法對(duì)于VRP求解均展現(xiàn)出較好的性能。

目前，國(guó)內(nèi)外有關(guān)血液保障車(chē)輛調(diào)度與算法的研究仍然較少，且主要集中于平時(shí)保障，應(yīng)急保障涉及較少[15-17]。本研究在災(zāi)害醫(yī)學(xué)救援應(yīng)急血液保障的背景下，考慮血液運(yùn)輸?shù)奶厥庑院蜑?zāi)后道路路況的復(fù)雜性，構(gòu)建血液保障車(chē)輛應(yīng)急調(diào)度模型，設(shè)計(jì)并改進(jìn)經(jīng)典遺傳算法，最后進(jìn)行算例求解與分析，為應(yīng)急血液保障提供數(shù)據(jù)支撐與理論參考。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

本文研究的血液保障車(chē)輛（以下簡(jiǎn)稱(chēng)“運(yùn)血車(chē)”）應(yīng)急調(diào)度優(yōu)化問(wèn)題描述如下：軍隊(duì)血站（以下簡(jiǎn)稱(chēng)“血站”）和醫(yī)療救治點(diǎn)構(gòu)成無(wú)向圖 G=（O，I，D），O 表示血站，I表示醫(yī)療救治點(diǎn)，D為邊集，運(yùn)血車(chē)配屬在血站，按照任務(wù)要求完成對(duì)多個(gè)醫(yī)療救治點(diǎn)的血液最優(yōu)配送，如圖1所示。

圖1 運(yùn)血車(chē)應(yīng)急調(diào)度優(yōu)化示意圖

1.2 模型假設(shè)

運(yùn)血車(chē)實(shí)際調(diào)度的過(guò)程復(fù)雜，涉及因素眾多，需進(jìn)行一定的抽象和簡(jiǎn)化。本文主要研究由單一血站出發(fā)，同車(chē)種、有容量和時(shí)間窗約束的車(chē)輛調(diào)度問(wèn)題，具體假設(shè)如下：

（1）運(yùn)往各醫(yī)療救治點(diǎn)的血液全部在保質(zhì)期內(nèi)，不存在過(guò)期情況；（2）運(yùn)送的血液不考慮血型，默認(rèn)全部為統(tǒng)一血型；（3）不同血液類(lèi)型（全血、懸浮紅細(xì)胞、冰凍血漿）均采用統(tǒng)一單位U表示；（4）血液運(yùn)送采用同種型號(hào)運(yùn)血車(chē)，且具有相同的容量限制，始終保持勻速行駛；（5）每一輛運(yùn)血車(chē)均從血站出發(fā)，完成運(yùn)送任務(wù)后返回出發(fā)點(diǎn)；（6）各醫(yī)療救治點(diǎn)的血液需求只能由同一輛運(yùn)血車(chē)滿足，且每條巡回路徑上只有1輛運(yùn)血車(chē)。

1.3 模型構(gòu)建

地震、洪澇等自然災(zāi)害發(fā)生后，傷病員大量產(chǎn)生，血液需求急劇增多，故模型只考慮時(shí)間成本，不考慮經(jīng)濟(jì)成本。災(zāi)害發(fā)生地多位于山區(qū)，路況差異大[18]，受損概率高，直接影響了血液運(yùn)輸時(shí)間，因此考慮災(zāi)后道路路況對(duì)配送時(shí)間的影響和多種類(lèi)血液需求的特殊性，設(shè)置單邊硬時(shí)間窗和運(yùn)血車(chē)雙血庫(kù)容量限制等約束條件，構(gòu)建以總配送時(shí)間最小化為目標(biāo)的運(yùn)血車(chē)調(diào)度模型，使模型更加貼近現(xiàn)實(shí)情況。模型符號(hào)說(shuō)明詳見(jiàn)表1。

表1 模型符號(hào)說(shuō)明

模型構(gòu)建如式（1）～（11）所示：

模型中：式（1）為目標(biāo)函數(shù)，表示總配送時(shí)間最短；式（2）表示全血和懸浮紅細(xì)胞配送總數(shù)不超過(guò)運(yùn)血車(chē)?yán)洳匮獛?kù)的容量限制；式（3）表示冰凍血漿配送總數(shù)不超過(guò)運(yùn)血車(chē)?yán)鋬鲅獛?kù)的容量限制；式（4）表示每一個(gè)醫(yī)療救治點(diǎn)只能由一輛運(yùn)血車(chē)提供服務(wù)；式（5）表示派出的運(yùn)血車(chē)數(shù)量不超過(guò)擁有數(shù)；式（6）表示運(yùn)血車(chē)行駛時(shí)間；式（7）表示時(shí)間窗約束，運(yùn)血車(chē)需要在規(guī)定時(shí)間窗內(nèi)將血液送達(dá)；式（8）表示運(yùn)血車(chē)到達(dá)醫(yī)療救治點(diǎn)后的服務(wù)時(shí)間；式（9）表示運(yùn)血車(chē)到達(dá)各醫(yī)療救治點(diǎn)時(shí)間；式（10）、（11）為決策變量。

2 算法設(shè)計(jì)

本文在經(jīng)典遺傳算法的基礎(chǔ)上引入高效的染色體編碼方式，選用指數(shù)排序選擇算子、順序交叉算子和倒位變異算子設(shè)計(jì)改進(jìn)遺傳算法，提高運(yùn)血車(chē)最優(yōu)配送方案求解效率。

2.1 編碼及種群初始化

本文采用整數(shù)編碼的方式，染色體長(zhǎng)度為n+m，整數(shù)I1～I(xiàn)n表示醫(yī)療救治點(diǎn)編碼，整數(shù)K1～Km表示運(yùn)血車(chē)配送點(diǎn)位數(shù)量編碼，染色體編碼圖如圖2所示。該種編碼方式將整條染色體分為m段，形成m個(gè)子回路，每個(gè)子回路代表一輛運(yùn)血車(chē)的配送路徑。該種編碼方式簡(jiǎn)便且易于理解，能夠快速生成大規(guī)模染色體群體，且染色體基因段種類(lèi)豐富。為提升計(jì)算效率與收斂效果，縮短不可行解在計(jì)算過(guò)程中浪費(fèi)的時(shí)間，在初始化種群的過(guò)程中加入時(shí)間窗和載質(zhì)量約束篩選因子，將不符合約束的染色體直接去除，直至生成滿足種群數(shù)量的染色體。

圖2 染色體編碼圖

2.2 適應(yīng)度評(píng)價(jià)

適應(yīng)度是指種群中的個(gè)體接近最優(yōu)解的程度，適應(yīng)度越大，表示解的性能越好。本文構(gòu)建的模型目標(biāo)函數(shù)是最小化運(yùn)血車(chē)完成所有配送任務(wù)所用的時(shí)間，因此以目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，即

2.3 選擇操作

本文采用指數(shù)排序選擇方式增加優(yōu)質(zhì)染色體被選擇的概率。種群需按照適應(yīng)度值進(jìn)行降序排序，排序后個(gè)體被選擇的概率P（i）為

式中，i、j代表個(gè)體的排序；N代表種群數(shù)量；c代表底數(shù)，c∈[0，1）。c越小最優(yōu)個(gè)體被選擇的概率就越大，若c=0，則設(shè)置最優(yōu)個(gè)體被選擇的概率為1，而其他所有個(gè)體被選擇的概率為0；c越趨近于1，所有個(gè)體越接近等概率選擇。

2.4 交叉操作

交叉算子是模仿生物進(jìn)化中同源染色體交配重組的過(guò)程，是種群產(chǎn)生新個(gè)體的關(guān)鍵，本文采取文獻(xiàn)[19]對(duì)比中性能最好的順序交叉算子，即在父代1中隨機(jī)選擇2個(gè)交叉點(diǎn)，找到父代2中截取交叉基因段基因，使子代1與子代2分別保持截取基因段且對(duì)應(yīng)截取基因位置不變，其余按照父代順序填入，如圖3所示。該交叉算子能夠在一定程度上實(shí)現(xiàn)優(yōu)良個(gè)體的保存，增加種群的多樣性，同時(shí)避免沖突檢測(cè)，提高運(yùn)行效率。

圖3 交叉操作示意圖

2.5 變異操作

變異是模仿自然界中染色體發(fā)生基因突變的現(xiàn)象，是輔助交叉操作，能夠恢復(fù)因交叉操作而消失的基因。染色體編碼中有部分基因段屬于最優(yōu)解基因段，傳統(tǒng)基因位突變方式極易造成優(yōu)質(zhì)基因段被破壞，故本文采用倒位變異算子[20]，即在個(gè)體上隨機(jī)選擇2個(gè)變異點(diǎn)，將變異區(qū)域的基因序列逆序排列后得到新個(gè)體，運(yùn)血車(chē)配送點(diǎn)位數(shù)量編碼不參與變異操作。倒位變異算子在較好地避免優(yōu)質(zhì)基因段被破壞的同時(shí)，增加了種群多樣性，降低了早熟率。變異操作如圖4所示。

圖4 變異操作示意圖

2.6 運(yùn)算步驟

步驟一：設(shè)置算法控制參數(shù)（種群大小Sizepop、指數(shù)排序選擇參數(shù)c、交叉概率Pc、變異概率Pm、最大迭代數(shù)Maxgen）。

步驟二：對(duì)運(yùn)血車(chē)路徑編碼，生成Sizepop數(shù)量的初始解（染色體），當(dāng)前迭代次數(shù)gen=0。

步驟三：計(jì)算種群中所有染色體適應(yīng)度值Z，記錄當(dāng)前最優(yōu)個(gè)體Rbest。

步驟四：比較上一代最優(yōu)個(gè)體Rbest*的適應(yīng)度值Zold與當(dāng)前最優(yōu)個(gè)體Rbest的適應(yīng)度值Znew的大小，若Znew＜Zold，則 Rbest=Rbest*，否則不更新。

步驟五：若gen＞Maxgen，跳出循環(huán)，生成最終種群，程序結(jié)束，否則繼續(xù)。

步驟六：采用指數(shù)排序選擇算子進(jìn)行選擇操作。

步驟七：采用順序交叉算子進(jìn)行交叉操作。

步驟八：采用倒位變異算子進(jìn)行變異操作。

步驟九：gen=gen+1，并跳轉(zhuǎn)至步驟三。

運(yùn)算流程如圖5所示。

圖5 改進(jìn)遺傳算法運(yùn)算流程圖

3 案例求解與分析

3.1 案例描述

某地區(qū)發(fā)生地震，該保障區(qū)域內(nèi)軍隊(duì)血站迅速完成部署，接受上級(jí)指派血液配送任務(wù)。該血站共有3輛同種型號(hào)的運(yùn)血車(chē)可供調(diào)運(yùn)，運(yùn)血車(chē)具備雙血庫(kù)，其中冷藏血庫(kù)（4±2）℃可滿足全血和懸浮紅細(xì)胞的儲(chǔ)存，冷凍血庫(kù)（-20±2）℃可滿足冰凍血漿的儲(chǔ)存，需要在規(guī)定時(shí)間內(nèi)完成15個(gè)醫(yī)療救治點(diǎn)的多種類(lèi)血液冷鏈運(yùn)輸。設(shè)血站坐標(biāo)為（102，104），單位為km，隨機(jī)設(shè)置其余點(diǎn)位坐標(biāo)和時(shí)間窗參數(shù)（見(jiàn)表2）、路況系數(shù)（見(jiàn)表3），各醫(yī)療救治點(diǎn)間距離可近似用歐氏距離公式計(jì)算，即。參考汶川地震中全血、懸浮紅細(xì)胞和冰凍血漿消耗的比例[21-22]，生成各點(diǎn)位、各類(lèi)型血液需求量（見(jiàn)表4）。

表2 各點(diǎn)位坐標(biāo)和時(shí)間窗

表3 各點(diǎn)位間路況系數(shù)

表4 各點(diǎn)位、各類(lèi)型血液需求量 單位：U

3.2 案例求解

（1）運(yùn)行環(huán)境與參數(shù)設(shè)置。

采用MATLAB編程，軟件在 CPU為 Intel（R）Core（TM）i5-9400 ＠ 2．90 GHz、內(nèi)存 16 GiB、操作系統(tǒng)為Windows 10的環(huán)境下運(yùn)行。運(yùn)血車(chē)參數(shù)設(shè)置：冷藏血庫(kù)載容量L1=500 U，冷凍血庫(kù)載容量L2=250 U，平均行駛速度v=50 km/h，醫(yī)療救治點(diǎn)單位時(shí)間內(nèi)接收血液數(shù)量μ=200 U/h。

（2）算法參數(shù)敏感性分析。

設(shè)置不同種群大小Sizepop、指數(shù)排序選擇參數(shù)c、交叉概率Pc、變異概率Pm和最大迭代數(shù)Maxgen，對(duì)不同參數(shù)組合做算法參數(shù)敏感性分析（見(jiàn)表5），對(duì)比平均最優(yōu)適應(yīng)度值、最優(yōu)解次數(shù)和平均運(yùn)行時(shí)間可知，一方面，增加Sizepop和Maxgen會(huì)豐富染色體多樣性，有利于最優(yōu)解的尋找，但影響本算法的運(yùn)行效率，原因主要在于種群編碼和迭代次數(shù)，Sizepop越大，Maxgen越大，算法求解速度越慢；另一方面，c、Pc、Pm對(duì)求解效率的影響是非線性的，在一定范圍內(nèi)具備較好的性能，故綜合考慮本文算法參數(shù)設(shè)置選擇組合1。不同參數(shù)組合下的算法運(yùn)行結(jié)果圖如圖6所示。

表5 不同參數(shù)組合下的算法運(yùn)行結(jié)果

圖6 不同參數(shù)組合下的算法運(yùn)行結(jié)果圖

3.3 案例分析

最優(yōu)配送路徑數(shù)據(jù)見(jiàn)表6，最優(yōu)配送路徑如圖7所示，結(jié)果表明，運(yùn)血車(chē)有能力在規(guī)定時(shí)間內(nèi)完成血液配送任務(wù)，運(yùn)血車(chē)1配送路徑耗時(shí)為 10．13h，運(yùn)血車(chē) 2 為 10．98 h，運(yùn)血車(chē)3為11．35 h，均未超出時(shí)間窗限制；運(yùn)血車(chē)1、運(yùn)血車(chē)2、運(yùn)血車(chē)3冷藏血庫(kù)滿載率分別為86．00%、97．00%、97．40%，冷凍血庫(kù)滿載率分別為 61．20%、69．20%、73．60%，整體血庫(kù)滿載率分別為77．73%、87．73%、89．74%，均未超過(guò)載容量限制，因此驗(yàn)證了該算法對(duì)于運(yùn)血車(chē)調(diào)度問(wèn)題求解的有效性。

表6 最優(yōu)配送路徑數(shù)據(jù)

圖7 最優(yōu)配送路徑圖

分別用經(jīng)典遺傳算法[23]（記為算法1）、文獻(xiàn)[24]的遺傳算法（記為算法2）與本文的改進(jìn)遺傳算法對(duì)比計(jì)算，迭代過(guò)程中平均最優(yōu)適應(yīng)度值變化如圖8所示。由圖8可知，本文設(shè)計(jì)的改進(jìn)遺傳算法在迭代22代后保持平穩(wěn)，即搜索到了最優(yōu)解32．46，算法1在第87代時(shí)開(kāi)始趨于平穩(wěn)，算法2在第74代以前陷入了局部最優(yōu)解，直到第75代才搜索到全局最優(yōu)解，故本文算法相較于算法1和算法2收斂速度更快，具備更好的運(yùn)算效率和全局搜索能力。

圖8 3種遺傳算法運(yùn)行對(duì)比圖

分別運(yùn)行3種算法各20次，記錄每次搜索到的平均最優(yōu)適應(yīng)度值，對(duì)3組平均最優(yōu)適應(yīng)度值數(shù)組做顯著性分析（如圖9所示），各組進(jìn)行多重比較后得出：改進(jìn)遺傳算法的平均最優(yōu)適應(yīng)度值（32．68）最小，與算法1的平均最優(yōu)適應(yīng)度值（35．24）具有極顯著差異（P＜0．01），與算法 2的平均最優(yōu)適應(yīng)度值（34．63）具有顯著差異（P＜0．05），故改進(jìn)遺傳算法較算法1、算法2具備更好的求解性能。

圖9 3種遺傳算法顯著性差異分析圖

4 結(jié)語(yǔ)

本文基于軍隊(duì)血站在災(zāi)害醫(yī)學(xué)救援中的職能任務(wù)與特點(diǎn)，考慮災(zāi)后道路路況、多種類(lèi)血液需求、時(shí)間窗和運(yùn)血車(chē)載容限制等條件，構(gòu)建以總配送時(shí)間最小化為目標(biāo)的血液保障車(chē)輛應(yīng)急調(diào)度模型，并在基本遺傳算法的基礎(chǔ)上引入高效的染色體編碼方式，選用了順序交叉算子、指數(shù)排序選擇算子和倒位變異算子，實(shí)現(xiàn)了運(yùn)血車(chē)最優(yōu)調(diào)度方案的高效求解，對(duì)大規(guī)模災(zāi)害救援初期運(yùn)力受限情況下的血液資源調(diào)度問(wèn)題具有較強(qiáng)的借鑒意義。

但應(yīng)急血液資源調(diào)度在國(guó)內(nèi)外仍屬于新興研究領(lǐng)域，實(shí)際調(diào)運(yùn)過(guò)程中需要考慮的因素很多，如血液的儲(chǔ)存周期、運(yùn)輸損耗、不同血型血液需求等，均為研究提供了新的思路與方向。下一步將加強(qiáng)模型構(gòu)建的有效性與智能優(yōu)化算法創(chuàng)新，為血液資源與保障裝備的優(yōu)化配置提供更有效的輔助決策支持。