“120”智能指揮調(diào)度算法設計與實踐

摘要:通過對“120”指揮調(diào)度的流程及特點進行研究，提出了一種可實現(xiàn)智能指揮調(diào)度的算法，該算法可綜合報警人位置、道路長短、交通狀況、醫(yī)療站點位置、急救車輛位置等多種因素，找到最優(yōu)的指揮調(diào)度方案。

關(guān)鍵詞:“120”系統(tǒng);智能指揮調(diào)度;指揮調(diào)度算法;最短路徑算法

中圖分類號:TP311.1文獻標識碼:A文章編號:1009-3044(2009)36-10316-02

Design and Practice of Intelligent \"120\" Command and Dispatch

YU Yong

(He'nan Economic and Trade Vocational College， Zhengzhou 450053， China)

Abstract: Through the study of the \"120\" Command and Dispatch Process and Features，made a algorithm that could be realized by intelligent command dispatching，the algorithm can be find a Optimal Dispatching scheme which Integrated such asAlarm one's position、Road length、Traffic Condition、Hospital Location、Emergency vehicle's locationand so on.

Key words: \"120\" system; intelligent command and dispatch; command and dispatch Algorithm; shortest-path algorithm

1 背景

隨著電子信息技術(shù)的發(fā)展，以及社會對公共衛(wèi)生事件的處置響應速度要求的提高，進一步提高“120”指揮調(diào)度系統(tǒng)的信息化水平和智能化水平在當前顯得非常迫切，各個城市都在尋求合適的系統(tǒng)進行應用推廣。通過參與某市“120”指揮調(diào)度系統(tǒng)的建設，深刻體會到急救工作是否及時、妥善，直接關(guān)系到傷病員的生命安危和愈后狀況，急救工作的狀況往往標志著一個國家、一個地區(qū)的醫(yī)療預防水平的高低，它不僅是醫(yī)學問題，也是社會和諧的重要體現(xiàn)。但，當前我們國家的“120”指揮調(diào)度系統(tǒng)的總體信息化水平還不高，指揮調(diào)度還停留在人工階段，對“120”指揮調(diào)度系統(tǒng)進行進一步研究有著現(xiàn)實意義。

通過對“120”指揮調(diào)度的流程進行研究，可使用智能化指揮調(diào)度代替當前的人工指揮調(diào)度，以提高指揮調(diào)度的效率和準確性。而要實現(xiàn)智能指揮調(diào)度則必須要智能生成指揮調(diào)度方案，該調(diào)度方案需要根據(jù)報警位置、道路長短、交通狀況、醫(yī)療站點位置、急救車輛位置等多種情況，找到報警位置到最佳的醫(yī)院或急救車輛的路徑，各單位、各部門人員密切配合和協(xié)作，通過該調(diào)度方案完成一次急救工作，因此，智能指揮調(diào)度的關(guān)鍵點在于需要一個算法綜合各種情況計算出最優(yōu)或較優(yōu)指揮調(diào)度方案。

要解決智能生成指揮調(diào)度方案的問題，我們可以結(jié)合地理信息技術(shù)(GIS)將道路網(wǎng)拓撲結(jié)構(gòu)進行提取、構(gòu)建和存儲，將道路網(wǎng)轉(zhuǎn)化為可以使用圖論的理論和方法進行分析的道路網(wǎng)拓撲結(jié)構(gòu)圖，從而將智能生成指揮調(diào)度方案的問題就轉(zhuǎn)化為求解圖的最短路徑問題。本文通過對常用的最短路徑算法進行研究，并結(jié)合“120”指揮調(diào)度的流程和特點，并提出了一個合理的、適合得出最優(yōu)或較優(yōu)指揮調(diào)度方案的算法，以支持構(gòu)建“120”智能指揮調(diào)度系統(tǒng)的需要。

2 常用最短路徑算法

最短路徑問題由來已久，且在現(xiàn)實生活中也經(jīng)常遇到，當前，它是運籌學、交通工程學、地理信息學等學科的研究熱點，國內(nèi)外很多專家學者對此問題進行了大量的研究，因此，新的最短路徑算法不斷涌現(xiàn)，它們在空間復雜度、時間復雜度、易實現(xiàn)性及應用范圍等方面各具特色，一些算法在一些特定領(lǐng)域得到了廣泛的應用，取得了較好的效果。目前，常用的最短路徑算法有Dijkstra算法及其改進算法、啟發(fā)式搜索算法、遺傳算法等幾類，下面對這幾類最短路徑算法做一簡單介紹。

1) Dijkstra算法及其改進算法

Dijkstra算法是荷蘭數(shù)學家E.W.Dijkstra于1959年提出的一個適用于非負值網(wǎng)絡的最短路徑算法，其思路清晰，搜索準確，但是耗時長，占用空間大，鑒于以上缺點，人們對算法進行了做了很多改進。改進主要是集中在Dijkstra算法的數(shù)據(jù)結(jié)構(gòu)和搜索策略上。在數(shù)據(jù)結(jié)構(gòu)方面將結(jié)點組織成用二進制堆(binary heap)表示的優(yōu)先隊列，或采用Fibonacci堆表示的優(yōu)先隊列，或者使用一個新的數(shù)據(jù)結(jié)構(gòu)-基數(shù)堆(radix heap)，這些對數(shù)據(jù)結(jié)構(gòu)的改進，大大提高了Dijkstra算法的執(zhí)行效率。

在搜索策略上，主要有限制搜索區(qū)域Dijkstra算法，大大縮小了算法的搜索區(qū)域，提高了算法的搜索效率;并提出了雙向Dijkstra算法，采用起點和終點雙向同時搜索的方法，將算法的搜索空間在理論上減少了百分之五十。

2) 啟發(fā)式搜索算法

啟發(fā)式搜索算法是基于知識的搜索策略，即通過選定一種估價函數(shù)，在搜索過程中都尋找估價函數(shù)數(shù)值最高的節(jié)點作為下一個搜索節(jié)點，從而快速的向目標靠近，達到提高算法搜索效率的目的。基于啟發(fā)式搜索的算法主要有Costed 算法、分支界定法、限制搜索區(qū)域法、A*算法等。目前，A*算法在路徑規(guī)劃領(lǐng)域應用的非常廣泛，它對實現(xiàn)道路網(wǎng)絡的最佳優(yōu)先搜索很有效。對A*算法的進一步改進算法有:雙向啟發(fā)式搜索、動態(tài)管理優(yōu)化A*算法等。

3) 遺傳算法

遺傳算法是20世紀60年代，由美國Michigan大學的J.H.Holland 教授首先提出來的。遺傳算法是一種優(yōu)化選擇算法，在某種意義上，它是“仿生學”在數(shù)學領(lǐng)域的直接應用，該算法的有效性雖尚未有嚴格的數(shù)學論證，然而該算法卻在實踐上已經(jīng)有成功的實例，因此，得到了廣泛的關(guān)注。

4) 其它的一些最短路徑算法

除了以上介紹的幾類最短路徑算法外，還有基于神經(jīng)網(wǎng)絡的最短路徑算法、多條最短路徑算法、基于GIS空間查詢語言的最短路徑算法等，它們都在一些特定領(lǐng)域，或在解決一些實際問題上取得了成功的應用。

3 智能指揮調(diào)度算法設計

通過對各類最短路徑算法進行對比分析，并結(jié)合生成指揮調(diào)度方案對算法的要求，我們可以在傳統(tǒng)的Dijkstra算法的基礎上對其進行改進，使之可以滿足進行智能指揮調(diào)度的需要，改進的Dijkstra算法基本思想是:

將網(wǎng)絡節(jié)點分成5部分:源節(jié)點、未標記節(jié)點、臨時標記節(jié)點、永久標記節(jié)點、目標節(jié)點(多個)。網(wǎng)絡中所有節(jié)點首先初始化為未標記節(jié)點，接著將與源節(jié)點相連通的節(jié)點標識為第一批臨時標記節(jié)點，并選擇其中與源節(jié)點路徑長度最短的節(jié)點標識為永久標記節(jié)點，從而形成一個從源節(jié)點出發(fā)的最短路徑，接著繼續(xù)搜索，在搜索過程中，與最短路徑中的節(jié)點相連通的節(jié)點，且該節(jié)點在指定的搜索范圍之內(nèi)，則該節(jié)點被標識為臨時標記節(jié)點，每次循環(huán)都是從臨時標記節(jié)點中搜索距源點路徑長度最短的節(jié)點作為永久標記節(jié)點，每次循環(huán)，如果找到目標節(jié)點中的一個，則得到一個最短路徑，并將最短路徑計數(shù)器加1，直至最短路徑計數(shù)器達到一定值來結(jié)束算法，如果指定范圍內(nèi)的所有節(jié)點都成為永久標記結(jié)點，且最短路徑計數(shù)器未達到指定值，則增大搜索范圍，繼續(xù)搜索，直至到達搜索范圍的上限或搜索出所有需要的最短路徑來結(jié)束算法。

改進的Dijkstra算法的求解描述如下:

給定帶權(quán)有向圖G=(V，E)、源點S0、圓形限制搜索區(qū)域半徑R、圓形限制搜索區(qū)域半徑增長步長R’、目標節(jié)點的集合D、要搜索的最短路徑數(shù)量Cnt，其中V是包含n個節(jié)點的節(jié)點集，E是包含m條邊的邊集，設S為已求得的最短路徑的終點的集合，i為已搜索到的最短路徑的數(shù)量，求S0到目標節(jié)點集合D中前Cnt個節(jié)點的最短路徑生成算法如下:

第一步:利用十字鏈表CLink來表示帶權(quán)有向圖G，Lij表示弧<νi，νj >上的長度，Wij表示弧<νi，νj >上的權(quán)值，若弧<νi，νj >不存在，則將Lij設為∞，Wij設為1。令S為已找到從S0出發(fā)的最短路徑的終點的集合，將其初始化為空集，令i為已搜索到的最短路徑的數(shù)量，將其初值設為0。用di表示從S0出發(fā)到終點vi的可能到達的最短距離，取其初始化值為:

di=L(s0，vi)*W(s0，vi)vi∈V (1)

第二步:選擇vj，使得

dj=min{di│νi∈V-S}(2)

且滿足

Dis(S0 ， Vj)

其中Dis(i，j)為距離計算函數(shù)，表示結(jié)點i到結(jié)點j的直線距離，

則νj就是當前從S0出發(fā)的最短路徑的終點，

若

vj∈D(4)

則令

i=i+1(5)

令

S= S∪{vj} (6)

V=V-{vj}(7)

第三步:修改從S0出發(fā)到集合V-S中任一頂點νk的可達最短路徑長度，如果

dj+ L(j，k)*W(j，k)< dk(8)

則修改dk為

dk= dj+ L(j，k)*W(j，k)(9)

重復操作第二步、第三步，直到i=Cnt，由此可求得按路徑長度遞增次序排列的從S0出發(fā)至目標節(jié)點集合D中前Cnt個節(jié)點的最短路徑序列。

4 智能指揮調(diào)度算法實現(xiàn)

上面討論了改進Dijkstra算法進行“120”指揮調(diào)度方案求解的過程，下面將具體給出使用改進Dijkstra算法智能生成“120”指揮調(diào)度方案的程序流程圖，如圖1所示。

在本流程圖中，首先需要進行一些參數(shù)的定義和初始化工作，其中包括:定義十字鏈表Clink來表示帶權(quán)有向圖G，其中G就是表示道路網(wǎng)拓撲結(jié)構(gòu)的有向圖，其定義為G=(V，E)，其中V是G中所有節(jié)點的節(jié)點集，假設有n個節(jié)點，E是G中所有弧的集合，假設有m條弧;十字鏈表Clink、節(jié)點個數(shù)n、弧的個數(shù)m在加載道路網(wǎng)拓撲結(jié)構(gòu)圖時初始化;定義D為目標節(jié)點的集合，也就是所有醫(yī)院節(jié)點組成的集合，在加載道路網(wǎng)拓撲結(jié)構(gòu)圖時初始化;定義S0表示源點，也是患者的位置所在，S0在調(diào)用該算法時初始化;定義R為圓形限制搜索區(qū)域半徑;定義R’為圓形限制搜索區(qū)域半徑增長步長;定義Cnt為要搜索的最短路徑數(shù)量;變量R、R’、Cnt由系統(tǒng)配置參數(shù)進行初始化;定義集合變量S為已求得的最短路徑的終點的集合，并初始化為空集;定義變量i為已搜索到的最短路徑的數(shù)量，并初始化為0;設Lij表示弧<νi，νj >上的長度，Wij表示弧<νi，νj >上的權(quán)值，若弧<νi，νj >不存在，則將Lij設為∞，Wij設為1。用di表示從S0出發(fā)到終點vi的可能到達的最短距離，取其初始化值為L(s0，vi)*W(s0，vi)。使用改進Dijkstra算法進行“120”指揮調(diào)度方案求解的過程如圖1。

5 結(jié)束語

通過對“120”指揮調(diào)度流程和方法進行研究，并結(jié)合地理信息技術(shù)及各類最短路徑算法，提出了一種合理的、適合智能生成指揮調(diào)度方案的“120”智能指揮調(diào)度算法，該算法可大幅提高“120”系統(tǒng)的信息化水平和智能化程度，提高“120”指揮調(diào)度的準確性和效率，對當前“120”系統(tǒng)建設具有借鑒意義。

參考文獻:

[1] 陸鋒，盧東梅，崔偉宏.交通網(wǎng)絡限制搜索區(qū)域時間最短路徑算法[J].中國圖像圖形學報，1999，4(10).

[2] 付夢印，李杰，鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學學報，2004，24(10).

[3] 斳曉強.雙向Dijkstra算法及中間鏈表加速方法[J].計算機仿真，2004，21(9):79-80.

[4] 孟慶浩，張明路，劉大維，彭商賢.基于雙向A*算法的自主車全局路徑規(guī)劃[J].天津大學學報，1998(31):24-29.

[5] 段莉瓊，朱建軍，馬玲.改進的最短路徑搜索A*算法的高效實現(xiàn)[J].海洋測繪，2004，24(5):19-21.

[6] Dijkstra E W.A note on two problems in connexion with graphs[J].Numberische Mathmatik，1959，1(1):269-271.