考慮時效的應急物資配送路徑優化方法

梁永梅 房志明 黃嘉豪

摘? 要：針對城市區域的應急醫療物資配送問題，把醫療點作為節點，醫療點之間的路徑作為邊，構建了相應的應急醫療物資配送的圖模型。提出了兩種面向實際需求的模型求解目標，一種是路徑最短，該目標追求配送路徑/用時最短，另一種是時效性最優，該目標追求人均可利用配售時間最多，以減輕人群聚集情景。建立了基于遺傳算法的應急醫療物資配送模型求解方法，并針對一個實例進行了計算分析，結果表明，路徑最短的配送方案不一定能達到最優的人均配售時間，而如果想實現較多的人均配售時間，則可能需要花費較多的配送成本。

關鍵詞：醫療物資;配送;路徑;時效;遺傳算法

中圖分類號：F252.14? ? 文獻標識碼：A

Abstract： In the event of an infectious disease epidemic， the rational dispatch and distribution of emergency medical supplies is the basis for epidemic prevention to ensure the safety of people's lives. Aiming at the problem of emergency medical supplies distribution in urban areas， taking medical points as nodes and paths between medical points as edges， a corresponding graph model of emergency medical material distribution is constructed. Two model solution goals oriented to actual needs are proposed. One is the shortest path， which pursues the shortest delivery route/time， and the other is the best timeliness， which pursues the maximum time available for allotment to reduce crowd gathering. A genetic algorithm-based emergency medical supplies distribution model solution method is then established， and calculation and analysis for an example is carried out. The results show that the shortest path distribution plan may not achieve the optimal per capita distribution time， and more per capita distribution time may require more travel costs.

Key words： medical supplies; distribution; routing; timeliness; genetic algorithm

0? 引? 言

自2019年底開始的新型冠狀病毒肺炎疫情，給全球公共衛生帶來了嚴峻的挑戰。尤其2020年初，口罩、醫用防護服等重要醫療物資一直處于極度短缺狀態，應急醫療物資的生產與配送成為應對新冠肺炎疫情的關鍵。以口罩為例，作為阻斷新冠肺炎疫情在普通民眾間傳播的最經濟且有效的工具，其需求量急劇攀升，且遠遠超出了日常產量。在口罩產能不足之時，為了保障居民的正常生活需求，國內各地一度對口罩配售實行統一調度：居民在所屬地實名預約，口罩配送至定點藥店，居民憑預約信息至定點藥店購買。其中，口罩配送方案與路徑是否最優決定了統一調度是否高效。因此，研究口罩等應急醫療物資的配送優化問題具有重要現實意義。

李元亨等人[1]以新型冠狀病毒肺炎疫情應對中的醫療物資配置為例進行分析，發現突發公共衛生事件應急管理已經從本質上異于或超越了傳統的制度主義基本邏輯范疇。張麗娜等人[2]以新冠疫情發生后的醫用口罩需求動態為觀測點，搜集相關新聞、評論，發現應急醫療物資在疫情蔓延早期面臨著價格暴漲、質量良莠不齊、保障不足與分配失衡等問題，由此引發的民眾脆弱性和政府信任危機給疫情防治帶來了巨大挑戰。褚永華等人[3]探索了醫院醫療物資應急保障機制，指出醫院醫療物資保障團隊需要依據“開源節流、量出為入”的原則，實行積極的物資采購策略，根據風險等級制定物資分配優先級，以存量與用途為依據統一發放物資，并實行捐贈物資的可追溯化管理。韋艷等人[4]調研了新疆179家二級以上醫院的應急資金及物資管理、急救設備配備等情況，指出各級醫院的應急救援物資管理現狀不容樂觀，存在突發事件醫療救援應急資金儲備、設備管理體系建設不完善，急救設備不齊全，消毒凈化能力薄弱等問題。潘婷[5]針對突發事件下應急醫療物資的配送問題，根據受災區的災情等級、傷亡人數和交通路況等災情信息已知的情況，構建了完全災情信息下的應急醫療物資分配方法和運送模型，結合模糊數相關基本理論，構建了不完全災情信息下的應急醫療物資分配方法和運送模型。能夠依據受災區的具體實際受災情況，確定為各個受災區分配與其情景相符合的應急醫療物資的比例及數量，然后確定分配給各受災區的應急醫療物資分別由哪個或者哪幾個供應點提供以及提供多少，并將其及時有效地運送到各個受災區，以達到緩解災情、減少損失的目的，也可提高有限的應急醫療物資在應急響應中的使用效率。陳波[6]針對突發事件不確定性和緊急性，建立了應急醫療物資調度中的車輛路徑優化模型，設計有效的遺傳算法對模型進行求解，并用實例驗證了應急醫療物資調度中的車輛路徑優化模型及算法的有效性和可行性。陳思地[7]根據傳染疾病的特點探討了建立醫療物資生產基地、基于大數據確保安全庫存、通過ABC分類進行配送的方案，指出確保運輸道路暢通、市民有序理智購買預防物資對有效抗擊傳染疾病有重大意義。

本文關注應急醫療物資配送路徑優化問題，在考慮最短路徑配送基礎上，引入配送時效性概念，從最短路徑和實效性兩方面構建應急醫療物資配送模型，并建立基于遺傳算法的模型求解方法。

1? 模? 型

1.1? 模型構建

本文關注某一城市或區域的簡化應急醫療物資配送問題，假設有n個定點配售點，只有1只配送隊伍負責將應急醫療物資由起始位置運送至各個配售點。基于圖論構建上述問題數學模型：

（1）假設應急醫療物資配送需求n個醫療點，每個醫療點作為節點，醫療點之間的距離記做d，則可用簡單圖G

=V，E，D描述該問題，其中V為節點集合，數量為n;E為每兩個節點之間邊的集合;D為每兩個節點之間距離的集合，節點與自身的距離記為0，不直接連通節點之間的距離記為∞。

（2）進一步，可用如下鄰接矩陣表示該模型，矩陣中的元素記錄的是每兩個節點之間的距離。

（1）

（3）記起始位置為Sx，y，該配送問題即為從S位置出發，遍歷圖中每個節點。

1.2? 模型求解目標

針對上述配送問題，本文提出兩種求解目標：

目標一：路徑最短。該目標下，配送隊伍從起始位置出發，遍歷每個節點所用路徑最短，不考慮路況影響，此時的用時也最少。對有n個節點的圖，記路徑中到第i-1節點到第i節點的距離為d，則該最優目標可表示為：

min∑d? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

目標二：時效性最優。由于城區居民分布及醫療點分布不均勻，各個醫療點服務的人群數量有可能差異較大。因此，本文認為在配送過程中，需要考慮各節點（醫療點）的權重（服務人群數量），使得人均可利用配售時間最多。以口罩統一配送為例，各個醫療點的預約人群數量不一樣，為了減少不必要的人群排隊聚集，應該使得人均購買配時（醫療點的統一配售時間

/醫療點的預約人數）越大越好。記總的可用時間為T，配送速度為v，則第i節點可用的配售時間為t=T-∑d/v，記每個節點的權重為w（值越大代表服務人數越多），則時效性最優目標可表示為：

max∑T-/w? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

1.3? 基于遺傳算法的模型求解方法

本文研究的配送問題屬于一個典型的NP-hard問題，這類問題通常無法通過精確算法進行求解，只能利用近似算法求取近似最優解。常見的近似算法有貪心算法、遺傳算法、概率算法等。而遺傳算法作為一種近似算法，在求解較為復雜的組合優化問題時，相對一些常規的優化算法，通常能夠較快地獲得較好的優化結果，并且具有群體搜索的特點，它的搜索過程是從一個具有多個個體的初始群體開始的，這樣既可以有效地避免搜索一些不必搜索的點，同時也能避免傳統的單點搜索方法的弊端，不會陷入某個局部極值點，有著非常好的并行化和全局搜索性。因此本文采用遺傳算法來求取模型的最優解。

在本文模型與常規遺傳算法邏輯基礎上，求解算法設計如下：

（1）遺傳編碼的設計

基因編碼目的在于使求解的目標問題與所要用的遺傳算法的染色體之間建立聯系。本文選取實物編碼作為編碼方式，首先對模型中每一個節點（醫療點）都按照一定規律進行編號，再利用編號排列的先后順序來表示救援路徑。其中，每個節點編號抽象為一個基因編碼，一條完整的配送路徑的節點編號序列抽象成一條染色體。

（2）種群的初始化

種群規模的初始化設置會對問題的優化程度產生較大影響，因為初始化設置的種群的質量會直接影響遺傳算法的收斂速

度[8]。若種群規模過小，將不利于增加種群的樣本多樣性，可能會在后面的迭代過程中造成收斂過快的現象，從而丟失最優點，而最終收斂于局部最優解。反之若種群規模過大，將會極大地增加算法的計算量和算法的收斂時間。依據經驗，本文將種群規模設計為150。

（3）適應度函數的設計

適應度函數是遺傳算法中的一種評判的標準，作為一種重要選擇機制，和后續的選擇和交叉工作有著密切的關系。本文的目標函數是求最短路徑或最大的配時，直接從種群中挑選出達到相應目標的路徑作為最優解，即把目標函數直接設置為適應度函數。

（4）遺傳操作

設定好適應度函數后，通過適應度函數可以得到不同個體的適應度大小，但是真正的篩選過程則需要經過一系列的遺傳操作，對優劣程度不同的個體進行篩選。以下是三種操作過程：

①交叉操作

遺傳算法交叉操作模擬的是生物體在有性繁殖過程的基因重組過程，兩個配對好的染色體通過某種方式交換它們各自部分基因，從而產生出兩個新的個體。交叉操作的過程中需要確定交叉概率和交叉操作模式。本文中，一個基因表示一個醫療點，所以在新生成的染色體中，原有的基因不能消失，也不能重復。根據以上特點，本文選擇采取兩點交叉的操作模式。根據經驗，設定交叉概率為0.8，即對每一條染色體，在0到1間隨機生成一個數，對生成的隨機數小于交叉概率的染色體進行交叉操作。

②變異操作

變異操作可以有效地增加種群數目，首先在種群中選擇出要變異的個體，再選擇個體中的染色體上要進行變異的基因。本文中的基因不能憑空消失，也不能任意的插入其他染色體中。根據這個特點，本文采用換位變異的方式，變異概率的值則設為0.002。在選出要進行變異的染色體之后，需要對它的每位基因都取一個0到1之間的隨機數，然后交換隨機數最大的兩個基因，以達到變異的目的。

③選擇操作

選擇操作指按照某種特定的規則，在之前得到的種群中不同個體的適應度值中，選出適應度較好的個體遺傳到下一代的過程[9]。基因的選擇方式有很多種。本文選擇采用輪盤賭方式，輪盤賭方式是一種基于適應度比例的選擇方法，能夠增大適應度大的個體遺傳到下一代的概率。假設個體i的適應度為F，則所有個體適應度的總和為∑F，這樣就得到了i的選擇概率如公式（4）所示：

P=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

其中： N=150表示種群規模的大小。

（5）終止條件

為了提高運算效率并且得到滿意的運算結果，需要對遺傳算法設置進化的終止條件，本文選擇在迭代的次數達到30 000次時終止。

2? 實例分析

為了檢驗模型，假設一個實例進行分析，該實例如表1所示，主要元素及模型參數設置如下：

（1）假設有18個醫療點，標記其ID為1～18，每個醫療點的坐標值及權重在表1中給出;

（2）表1中ID為0點作為起始位置，即S0，0點為起始點;

（3）起始點與各個節點、各個節點之間的距離即是坐標點之間的直線距離;

（4）假設T=24，v=50。

分別針對公式（2）與公式（3）的目標，基于遺傳算法進行分析計算，結果如表2和圖1所示。可以看到，兩種目標下的結果并不一致：（1）到達各個醫療點的次序不同，時效性最優目標下甚至出現了路徑交叉的情況（圖1b）;（2）路徑最短目標下的路徑長度為281.36，時效性最優目標下為341.53，高出了21.39%;（3）路徑最短目標下的時效為8.55，時效性最優目標下為8.63，多出了0.94%。結果表明路徑最短的配送方案不一定能達到最優的人均配售時間，而如果想實現較多的人均配售時間，則可能需要花費較多的配送成本（路徑增加導致的成本增加）。

3? 結? 論

針對城市區域的應急醫療物資配送問題，把醫療點作為節點，醫療點之間的路徑作為邊，構建了相應的應急醫療物資配送的圖模型。并給出了兩種模型目標以對應兩種實際需求，一種是路徑最短，該目標追求配送路徑/用時最短，另一種是時效性最優，該目標追求人均可利用配售時間最多，以減輕人群聚集情景。

建立了基于遺傳算法的應急醫療物資配送模型求解方法，該方法中將節點作為基因，將配送路徑試做染色體，并把模型的目標函數設置為適應度函數。針對一個實例進行了計算分析，結果表明，路徑最短的配送方案不一定能達到最優的人均配售時間，而如果想實現較多的人均配售時間，則可能需要花費較多的配送成本（路徑增加導致的成本增加）。本文建立的模型能夠從兩種不同的角度考慮應急醫療物資配送問題，可供決策者視實際需求而選擇合適的配送方案。

參考文獻：

[1] 李元亨，王亦冬，趙思奇，等. 新型冠狀病毒肺炎疫情防控醫療物資配置策略研究[J]. 中國醫院管理，2020，40（4）：5-7.

[2] 張麗娜，峗怡. 以醫用口罩為例探討新型冠狀病毒肺炎疫情中政府應急衛生資源保障對策[J]. 中國醫療管理科學，2020（3）：15-17.

[3] 褚永華，鄒瞿超，謝慧玲，等. 新冠肺炎疫情下醫院醫療物資應急保障機制探索[J]. 中華醫院管理雜志，2020，36（4）：345-348.

[4] 韋艷，李偉. 新疆179家醫院突發事件醫療救援應急物資管理現狀調查[J]. 職業衛生與應急救援，2020，38（4）：381-384.

[5] 潘婷. 突發事件下應急醫療物資配送問題研究[D]. 西安：西安工程大學（碩士學位論文），2019.

[6] 陳波. 應急醫療物資調度中的車輛路徑優化研究[D]. 武漢：武漢理工大學（博士學位論文），2013.

[7] 陳思地. 傳染疾病情景下的應急物流研究[J]. 物流工程與管理，2020，42（4）：103-104.

[8] 張立仿，張喜平. 量子遺傳算法優化BP神經網絡的網絡流量預測[J]. 計算機工程與科學，2016（1）：114-119.

[9] 吳志杰，孔凡敏，李康. 基于遺傳算法的BP神經網絡的LED壽命預測模型[J]. 半導體技術， 2018，43（5）：62-67.