李 慧，王晨曦，賈東寶，韓國凱，侯鵬飛，邢立豹，顧 勇

(江蘇海洋大學(xué) 計(jì)算機(jī)工程學(xué)院，江蘇 連云港 222005)

隨著我國工業(yè)發(fā)展的深入和工業(yè)生產(chǎn)規(guī)模的擴(kuò)大，包括火災(zāi)在內(nèi)的各類工業(yè)突發(fā)事故數(shù)量不斷增加，造成了嚴(yán)重的人員傷亡和財(cái)產(chǎn)損失。如何根據(jù)事故發(fā)生的實(shí)際情況，規(guī)劃出最佳的應(yīng)急救援路徑，用最少的時(shí)間展開應(yīng)急救援，減少人員傷亡，減輕財(cái)產(chǎn)損失，已經(jīng)成為相關(guān)領(lǐng)域的研究重點(diǎn)。

目前，主流的救護(hù)車調(diào)度算法可以分為三類。第一類是基于交通道路的擁擠情況對(duì)急救車輛進(jìn)行實(shí)時(shí)調(diào)度，如文獻(xiàn)[1]提出的根據(jù)車輛行駛時(shí)間，綜合考慮道路擁堵情況，實(shí)現(xiàn)救護(hù)車輛實(shí)時(shí)調(diào)度的方法；文獻(xiàn)[2]在救護(hù)車運(yùn)行控制過程中根據(jù)道路擁堵的情況動(dòng)態(tài)對(duì)救護(hù)車進(jìn)行調(diào)度。雖然這些調(diào)度方法考慮到了道路擁堵情況，但卻忽略了患者和救護(hù)車的地理位置、車輛使用情況及醫(yī)院救援物資情況等。第二類是基于遺傳算法對(duì)救護(hù)車調(diào)度進(jìn)行優(yōu)化，如文獻(xiàn)[3]使用遺傳算法對(duì)救護(hù)車部署和調(diào)度問題進(jìn)行了優(yōu)化，旨在最大限度地提高患者的預(yù)期存活概率；文獻(xiàn)[4]提出了基于遺傳算法的優(yōu)化框架，使用了響應(yīng)時(shí)間最小化、覆蓋范圍最大化的最近調(diào)度規(guī)則。第三類方法是對(duì)急救車輛在調(diào)度前實(shí)施一些預(yù)評(píng)估方案，如文獻(xiàn)[5]將生存功能納入調(diào)試方案，根據(jù)患者的類別預(yù)先建模，從而對(duì)救護(hù)車輛進(jìn)行分配；文獻(xiàn)[6]提出為滿足對(duì)救援物資的需求，同時(shí)考慮到每個(gè)需求的緊迫性，為每個(gè)節(jié)點(diǎn)設(shè)置優(yōu)先級(jí)，按照優(yōu)先級(jí)大小依次提供救援。雖然這些調(diào)度考慮到了醫(yī)療物資情況、病人救治率等因素，但未考慮調(diào)試過程中交通道路的擁堵情況，不利于救護(hù)車的實(shí)時(shí)調(diào)度。

本文采用改進(jìn)的弗洛伊德算法，綜合考慮道路擁堵情況、醫(yī)院救援物資情況、患者和醫(yī)院地理位置以及車輛空閑情況等重要因素，對(duì)不同路徑動(dòng)態(tài)賦予不同權(quán)值，得到一個(gè)綜合權(quán)值，以此規(guī)劃出最優(yōu)的救護(hù)路徑，從而實(shí)現(xiàn)對(duì)急救車輛的智能調(diào)度。

1 問題定義

救護(hù)車路徑選擇的目的是為實(shí)施救助的醫(yī)護(hù)人員規(guī)劃一條最佳路徑，以確保救護(hù)車輛能夠快速到達(dá)現(xiàn)場(chǎng)實(shí)施救援。規(guī)劃最優(yōu)路徑需要找到任意兩個(gè)地點(diǎn)之間的最短路徑，同時(shí)還要考慮道路擁堵狀況、醫(yī)院救援物資情況和車輛空閑情況，以及患者和醫(yī)院的地理位置信息等一系列因素，以此得到路徑選擇的最優(yōu)解。

為了評(píng)估所得解的優(yōu)劣，本文將救護(hù)車和被救治病人之間的權(quán)值作為目標(biāo)函數(shù)值。救護(hù)車路徑搜索問題建模如下:

W=(d[i][j]+h×ri+g×ri)×s；

(1)

(2)

Q=(q1,q2,q3，…，qf),f≥0；

(3)

M=(m1,m2,m3，…，mt),t≥0。

(4)

目標(biāo)函數(shù)(1)表示在緊急調(diào)度的過程中救護(hù)車和病人之間的權(quán)值，其值越大，所選路徑耗時(shí)越長；式(2)中R表示所有權(quán)值因素占比集合，且占比之和為1，用P矩陣來存儲(chǔ)醫(yī)院和患者之間的路徑信息，用D矩陣來存儲(chǔ)醫(yī)院和患者之間的最短路徑距離；式(3)中的Q表示道路擁堵情況集合；式(4)中M表示醫(yī)院的救援物資情況。本文根據(jù)CAD軟件繪制交通路線圖，通過ArcGIS的網(wǎng)絡(luò)數(shù)據(jù)集工具ArcMap在每一個(gè)交叉路口進(jìn)行打斷處理，建立如圖1所示的交通網(wǎng)絡(luò)模型[7]，然后將交叉點(diǎn)抽象為結(jié)點(diǎn)，路段抽象為邊，最終得到如圖2所示的路徑結(jié)點(diǎn)網(wǎng)絡(luò)。

圖1 交通道路網(wǎng)絡(luò)模型

圖2 路徑結(jié)點(diǎn)網(wǎng)絡(luò)

道路網(wǎng)絡(luò)模型可用式(5)表示[8]：

(5)

式中：RM表示交通道路網(wǎng)的模型；M表示在交通道路網(wǎng)中各個(gè)頂點(diǎn)的集合；R表示道路網(wǎng)中具體路徑的集合，其元素為有序?qū)?e,f)，(e,f)表示頂點(diǎn)e與頂點(diǎn)f之間有向連通，lef表示頂點(diǎn)e與頂點(diǎn)f之間的加權(quán)路徑長度[9]；LV表示道路網(wǎng)中連通兩點(diǎn)之間的加權(quán)路徑長度集合。路徑的加權(quán)長度僅僅是兩個(gè)頂點(diǎn)之間的距離。

2 傳統(tǒng)弗洛伊德算法

2.1 弗洛伊德算法描述

弗洛伊德算法是用來求加權(quán)圖之間的各個(gè)多源頂點(diǎn)之間最短路徑的算法，添加或減少任意頂點(diǎn)，它都可以動(dòng)態(tài)地實(shí)現(xiàn)最短路徑規(guī)劃。該算法以1978年圖靈獎(jiǎng)獲得者羅伯特·弗洛伊德命名[10]。

弗洛伊德算法的主要思想為：將所有的結(jié)點(diǎn)和邊都放在圖中進(jìn)行表示，圖中的權(quán)值表示兩個(gè)結(jié)點(diǎn)之間的距離，兩個(gè)頂點(diǎn)之間不直接可達(dá)的距離用無窮來表示，將圖中的信息轉(zhuǎn)化成鄰接矩陣的形式，每加入一個(gè)新的結(jié)點(diǎn)即更新鄰接矩陣的路徑長度，通過中間結(jié)點(diǎn)就可以求出任意兩個(gè)結(jié)點(diǎn)的最短路徑，新生成的路徑會(huì)儲(chǔ)存在路徑矩陣P中。

2.2 弗洛伊德算法實(shí)現(xiàn)步驟

首先對(duì)各條邊之間的權(quán)值進(jìn)行初始化。定義一個(gè)矩陣P用來記錄所插入點(diǎn)的信息，定義D矩陣用來記錄頂點(diǎn)之間的路徑長度信息。在D矩陣中，如果兩個(gè)頂點(diǎn)之間沒有直接連通的路徑,記D[i][j]=無窮大,如果兩個(gè)頂點(diǎn)之間可達(dá),則D[i][j]=d。對(duì)于圖中的任意一對(duì)頂點(diǎn)x和y，判斷是否存在一個(gè)頂點(diǎn)z，使得從x經(jīng)過z到y(tǒng)比已知的路徑更短,如果存在，那么就更新P矩陣。初始化P[i][j]=j，把各個(gè)頂點(diǎn)V插入圖中，比較插點(diǎn)后的距離與原來的距離，D[i][j]=min(D[i][j],D[i][k]+D[k][j])，如果D[i][j]的值變小，P[i][j]=k。例如，要尋找從V6到V2的路徑,根據(jù)P，假如P(6,2)=4,則說明從V6到V2經(jīng)過V4，路徑為{V6,V4,V2};如果P(6,3)=3，說明V6與V3直接相連;如果P(6,1)=1，說明V6與V1直接相連。

由上述分析可知，任意加入一個(gè)新的節(jié)點(diǎn)，通過弗洛伊德算法都可以求得任意兩個(gè)頂點(diǎn)之間的最短路徑。

弗洛伊德算法可用下面?zhèn)未a表示：

Void Floyd()

{

int s,t,h;

for(h=1;h<=n;h++)

for(s=1;s<=n;s++)

for(t=1;t<=n;t++) if(dist[s][h]+dist[h][t]

dist[s][t]= dist[s][h]+dist[h][t]

}

3 弗洛伊德算法優(yōu)化

3.1 權(quán)值優(yōu)化

傳統(tǒng)的弗洛伊德算法雖然可以用來進(jìn)行最短路徑規(guī)劃，但是它僅僅考慮了路徑的長度而忽略了道路擁擠情況、救援物資情況、車輛空閑情況等其他因素對(duì)結(jié)點(diǎn)之間權(quán)值的影響，所以需要在傳統(tǒng)弗洛伊德算法的基礎(chǔ)上進(jìn)行優(yōu)化。

對(duì)式(5)中的lef進(jìn)行優(yōu)化并重新對(duì)權(quán)值進(jìn)行賦值，將各個(gè)因素都納入到權(quán)值的占比中，對(duì)每個(gè)部分的占比進(jìn)行靈活分配，將各個(gè)因素進(jìn)行加權(quán)求和之后得到一個(gè)新的權(quán)值，然后再采用弗洛伊德最短路徑算法規(guī)劃出一條最佳的路徑。改進(jìn)后的算法流程如圖3所示。

圖3 改進(jìn)后弗洛伊德算法流程

3.2 改進(jìn)弗洛伊德算法步驟

第一步，為了對(duì)弗洛伊德算法進(jìn)行進(jìn)一步優(yōu)化，將所有的信息進(jìn)行初始化。首先將整個(gè)醫(yī)院地圖信息優(yōu)化成完全帶權(quán)圖G，將醫(yī)院設(shè)為節(jié)點(diǎn)v0，然后在患者求救時(shí)將患者的節(jié)點(diǎn)v1，v2,…,vn加入到集合V中。

第二步，對(duì)醫(yī)院與患者之間的路徑權(quán)值進(jìn)行動(dòng)態(tài)規(guī)劃。首先通過地圖測(cè)出醫(yī)院與患者或者患者與患者之間的實(shí)際路徑長度，即圖中各個(gè)頂點(diǎn)之間的實(shí)際距離di。其次對(duì)每個(gè)因素劃分為11個(gè)等級(jí)。例如，道路擁堵情況劃分為0～10共11個(gè)等級(jí)，根據(jù)實(shí)際道路情況確定等級(jí)，道路擁堵時(shí)可以取值為9或10，道路暢通時(shí)可以取值為0或1。

為了便于理解，本文僅考慮道路的擁堵情況和醫(yī)院的物資情況兩個(gè)因素，對(duì)道路擁堵情況的評(píng)級(jí)用h表示，對(duì)醫(yī)療物資的情況評(píng)級(jí)用g表示。根據(jù)W=(d[i][j]+h×ri+g×ri)×s計(jì)算出權(quán)值。

第三步，引入AK(i,j)，表示從i到j(luò)的途中不經(jīng)過索引比k大的最短路徑，然后用最短路徑計(jì)算公式

AK(i,j)=min{AK-1(i,j),AK-1(i,k)+AK-1(k,j)}

計(jì)算出AK(i,j)，當(dāng)K=n時(shí)(n為索引的總個(gè)數(shù))，An(i,j)=D[i][j],即可求出經(jīng)過多種因素下的最短路徑。并令P[i][j]=k，將經(jīng)過的最短路徑節(jié)點(diǎn)加入到集合p中。

采用了改進(jìn)弗洛伊德算法后，對(duì)各個(gè)結(jié)點(diǎn)的權(quán)值進(jìn)行重新賦值可以更加實(shí)際地實(shí)現(xiàn)對(duì)急救車輛的調(diào)度。

4 實(shí)例分析

本文采用 CAD，Visual Studio，ArcMap，IDEA等工具開發(fā)了救護(hù)車智能調(diào)度軟件。選取連云港市的交通道路網(wǎng)絡(luò)作為研究數(shù)據(jù)，將各種交通路口、市區(qū)主干道等要素添加到數(shù)據(jù)庫中，并通過CAD的圖形繪制工具得到如圖4所示的連云港交通路線圖。

圖4 連云港交通路線圖

以下是一個(gè)弗洛伊德算法實(shí)例。

(1) 將起點(diǎn)V0加入到Path[]數(shù)組中得到新的Dist[]矩陣(a)和Path[]矩陣(b)。

b Path[]矩陣

(2) 起點(diǎn)V1加入到Path[]數(shù)組中，得到新的Dist[]矩陣(c) 和Path[]矩陣(d) 。

d Path[]矩陣

c Dist[]矩陣

(3) 以此類推，當(dāng)起點(diǎn)V8加入到Path[]數(shù)組中時(shí)算法結(jié)束。此時(shí)得到新的Dist[]矩陣(e)和Path[]矩陣(f)。

a Dist[]矩陣

f Path[]矩陣

(4) 根據(jù)距離矩陣和路徑矩陣可得到任意兩點(diǎn)間的最短距離。例如從V4→V7的最短路徑，從P矩陣可得最短路徑為V4→V6→V7。綜合考慮各個(gè)因素的影響,重新對(duì)權(quán)值進(jìn)行賦值。

對(duì)每個(gè)可能因素都賦予不同的比例，計(jì)算出最合理的權(quán)值，此時(shí)得到的結(jié)果和路徑更為準(zhǔn)確，能高效地運(yùn)用在救護(hù)車的智能調(diào)度中。將傳統(tǒng)的Dijkstra算法嵌入到軟件中，規(guī)劃出了如圖5所示的應(yīng)急救護(hù)車最短路徑(圖中加粗線段)。

圖5 弗洛伊德算法下的最短路徑

本文對(duì)道路擁堵情況、救援物資情況、車輛空閑情況以及患者和醫(yī)院的地理位置等進(jìn)行綜合考慮后，將改進(jìn)的弗洛伊德算法嵌入到軟件中，重新規(guī)劃出了如圖6所示的最短路徑(圖中加粗線段)。

圖6 改進(jìn)弗洛伊德算法下的最短路徑

假設(shè)車輛勻速行駛，經(jīng)過一個(gè)交叉路口平均等待30 s。圖5的路徑長度為1 508.6 m，經(jīng)過11個(gè)交叉路口，用時(shí)15.6 min。圖6的路線長1 709.8 m，經(jīng)過8個(gè)交叉路口，用時(shí)13.5 min。圖6路線在實(shí)際運(yùn)行過程中有效地避開了擁堵路段，且綜合考慮了患者求救的地理位置信息，雖然其路徑比圖5規(guī)劃路徑更長，但用時(shí)更少，救治效率更高。

5 仿真實(shí)驗(yàn)結(jié)果與分析

5.1 網(wǎng)絡(luò)結(jié)構(gòu)的仿真實(shí)驗(yàn)

采用文獻(xiàn)[11]網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)取8)，將弗洛伊德算法和改進(jìn)的弗洛伊德算法進(jìn)行比較，以驗(yàn)證所提算法的有效性。實(shí)驗(yàn)在Matlab 2016b上對(duì)每種算法求得的最優(yōu)解進(jìn)行多次仿真測(cè)試。弗洛伊德算法不考慮其他因素的影響，故路徑權(quán)重因子賦值為0，而改進(jìn)的弗洛伊德算法考慮其他因素的影響，故路徑權(quán)重因子賦值為1。不同路徑權(quán)重因子的網(wǎng)絡(luò)結(jié)構(gòu)如圖7和圖8所示。

圖7 路徑權(quán)重因子為0的網(wǎng)絡(luò)結(jié)構(gòu)

圖8 路徑權(quán)重因子為1的網(wǎng)絡(luò)結(jié)構(gòu)

由圖7可知，當(dāng)路徑權(quán)重因子為0時(shí)，此時(shí)未考慮其他因素的影響，可認(rèn)為是采用弗洛伊德算法求得起點(diǎn)到終點(diǎn)的最短距離(即圖中加粗線段)，圖中權(quán)值僅代表由各路徑間距離計(jì)算出的權(quán)值。當(dāng)路徑權(quán)重為1時(shí)，結(jié)合式(2)和式(3)，綜合考慮道路擁堵情況、醫(yī)院救援物資情況、患者和醫(yī)院地理位置、車輛空閑情況等，對(duì)權(quán)值公式進(jìn)行計(jì)算得到如圖8所示的網(wǎng)絡(luò)結(jié)構(gòu)。此時(shí)的權(quán)值代表綜合各因素后的地點(diǎn)之間的路徑長度，此時(shí)再采用弗洛伊德算法求得從起點(diǎn)到終點(diǎn)的最短路徑(即圖8中加粗線段)。

下面通過仿真模擬環(huán)境1(路徑權(quán)重因子為0)和模擬環(huán)境2(路徑權(quán)重因子為1)的實(shí)驗(yàn)結(jié)果(見表1)，來具體比較兩種算法在救護(hù)車智能調(diào)度中的效率(車輛運(yùn)行速度取80 km/h)。

表1 模擬環(huán)境下的實(shí)驗(yàn)結(jié)果

比較發(fā)現(xiàn)，當(dāng)權(quán)重因子為0時(shí)，起點(diǎn)到終點(diǎn)的距離由最短路徑長度決定，此時(shí)最短路徑經(jīng)過的結(jié)點(diǎn)為0→1→3→6→8，由弗洛伊德算法計(jì)算可得用時(shí)為16.5 min。但實(shí)測(cè)用時(shí)為22.0 min，表明算法的局限性極大地影響了急救車輛的調(diào)度效率。當(dāng)權(quán)重因子為1時(shí)，綜合考慮道路擁擠、救援物資、患者和醫(yī)院地理位置、車輛空閑等因素影響，得到最短路徑為0→2→5→8，所用最短時(shí)間為21.5 min，實(shí)測(cè)用時(shí)22.0 min?？梢钥闯?，采用改進(jìn)的弗洛伊德算法效率較高，與實(shí)際用時(shí)相差僅為2.27%。

5.2 隨機(jī)生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的仿真實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)弗洛伊德算法的通用性和有效性，本文采用salam網(wǎng)絡(luò)拓?fù)潆S機(jī)生成算法生成10～45個(gè)節(jié)點(diǎn)的對(duì)稱網(wǎng)絡(luò)結(jié)構(gòu)，將網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)量擴(kuò)大并隨機(jī)生成。仿真實(shí)驗(yàn)不僅可以驗(yàn)證本文算法的正確性,還可以擴(kuò)展到較大的網(wǎng)絡(luò)結(jié)構(gòu)[12-13]。

在此基礎(chǔ)上，本文定義路由優(yōu)化失敗率，它表示在運(yùn)行算法時(shí)找不到最短調(diào)度時(shí)間的次數(shù)占總次數(shù)的百分比。一般認(rèn)為,路徑失敗的相對(duì)頻率接近于所計(jì)算的路徑不是最短調(diào)度時(shí)間的概率。每種節(jié)點(diǎn)數(shù)情況下隨機(jī)生成20種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對(duì)應(yīng)每種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)各算法均運(yùn)行50次節(jié)點(diǎn)數(shù)，失敗率取平均值[12]。

圖9表示不同節(jié)點(diǎn)數(shù)下改進(jìn)弗洛伊德算法與經(jīng)典弗洛伊德算法的優(yōu)化失敗率對(duì)比情況。改進(jìn)弗洛伊德算法的計(jì)算優(yōu)化失敗率較經(jīng)典弗洛依德算法低，算法表現(xiàn)較好，在不同網(wǎng)絡(luò)結(jié)構(gòu)下性能表現(xiàn)較穩(wěn)定，尋優(yōu)能力更強(qiáng)。綜合所有仿真實(shí)驗(yàn)可以得出，改進(jìn)的弗洛伊德算法在急救車救援調(diào)度中效率更高，出錯(cuò)率更低，能更好地對(duì)急救車輛進(jìn)行調(diào)度。

圖9 兩種算法路由最短路徑優(yōu)化率的比較

6 結(jié)語

本文針對(duì)應(yīng)急救援過程中救護(hù)車輛智能調(diào)度這一難點(diǎn)問題，對(duì)相關(guān)算法進(jìn)行比較驗(yàn)證。采取改進(jìn)弗洛伊德算法對(duì)道路擁堵狀況、醫(yī)院救援物資情況、患者和醫(yī)院的地理位置、車輛空閑狀況等進(jìn)行綜合考慮，找到了最佳路徑，為救護(hù)車輛的智能調(diào)度問題提供了一個(gè)切實(shí)可行的解決方案，有效提升了智能救助的信息化水平。