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

張澤瑞，段德光，李 昊，陶學強，鹿國偉，陳 恩

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

0 引言

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

1.2 模型假設(shè)

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

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

1.3 模型構(gòu)建

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

表1 模型符號說明

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

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

2 算法設(shè)計

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

2.1 編碼及種群初始化

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

圖2 染色體編碼圖

2.2 適應(yīng)度評價

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

2.3 選擇操作

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

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

2.4 交叉操作

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

圖3 交叉操作示意圖

2.5 變異操作

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

圖4 變異操作示意圖

2.6 運算步驟

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

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

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

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

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

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

步驟七：采用順序交叉算子進行交叉操作。

步驟八：采用倒位變異算子進行變異操作。

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

運算流程如圖5所示。

圖5 改進遺傳算法運算流程圖

3 案例求解與分析

3.1 案例描述

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

表2 各點位坐標和時間窗

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

表4 各點位、各類型血液需求量 單位：U

3.2 案例求解

（1）運行環(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)境下運行。運血車參數(shù)設(shè)置：冷藏血庫載容量L1=500 U，冷凍血庫載容量L2=250 U，平均行駛速度v=50 km/h，醫(yī)療救治點單位時間內(nèi)接收血液數(shù)量μ=200 U/h。

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

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

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

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

3.3 案例分析

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

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

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

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

圖8 3種遺傳算法運行對比圖

分別運行3種算法各20次，記錄每次搜索到的平均最優(yōu)適應(yīng)度值，對3組平均最優(yōu)適應(yīng)度值數(shù)組做顯著性分析（如圖9所示），各組進行多重比較后得出：改進遺傳算法的平均最優(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），故改進遺傳算法較算法1、算法2具備更好的求解性能。

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

4 結(jié)語

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

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