【正文】 息 系 統(tǒng) ）是 城 市應 急 聯(lián) 動 系 統(tǒng) 中 非 常 重 要 的 組 成 部 分 ， 城 市 應 急 聯(lián) 動 系 統(tǒng) 是 保 障 城 市 公 共 安 全的 綜 合 救 援 體 系 及 集 成 技 術 平 臺 ， 是 集 通 信 、 計 算 機 、 網 絡 、 地 理 信 息 、 全 球定 位 、 圖 形 圖 像 、 視 頻 監(jiān) 控 、 數(shù) 據(jù) 庫 與 信 息 處 理 等 多 種 技 術 為 一 體 的 通 信 、 信息 及 指 揮 系 統(tǒng) 平 臺 [2,3]。公安部研究開發(fā)的服務于警用業(yè)務的指揮調度系統(tǒng)，首先在各省會城市和開封，深圳等試點城市進行試運行。目前類似火災救援，醫(yī)療救護等應急活動，都發(fā)展了各自的信息化調度系統(tǒng)，其核心思想也是路徑優(yōu)化的算法。 系 統(tǒng) 可 對 現(xiàn) 場 的 公 安 、 交 警 、 消防 和 救 護 資 源 進 行 指 揮 控 制 。最短路徑問題也一直是運籌學、交通工程學、計算機科學、地理信息學等學科的一個研究熱點。當具體應用在不同的方面時有許多不同的算法和實現(xiàn)。最短路徑是運籌學、圖論等應用數(shù)學領域中一個基本概念，關于它的算法研究己得到相關領域學者的長期關注，并已有許多的研究成果。對于最短路徑問題也提出了許多新的算法，為最優(yōu)路徑的選擇提供了更多的選擇空間。對于動態(tài)路徑規(guī)劃 [11]。4車輛路徑問題是路線優(yōu)化的一個重要分支，目前其在物流中的應用具有相當?shù)膹V泛性并且具有重大的經濟價值。1991 年，Gendrcau 等人將禁忌k搜索方法應用于 VRP[16]。紀壽文等根據(jù)深圳市科技園的實際路網圖，采用神經網絡的方法對運輸車輛優(yōu)化調度進行了試驗研究 [6]。崔雪麗等基于近些年出現(xiàn)的新型智能優(yōu)化思想——人工螞蟻系統(tǒng)，給出了一種可快速求解 VRP 的蟻群搜索算法 [7]。這些都為 110 出警最優(yōu)路徑的選擇提供了更多的備選工具。5MAPGIS 是新一代面向網絡超大型分布式地理信息系統(tǒng)基礎軟件平臺。每一個使用 ArcObjects 建成的 ArcGIS 產品都為開發(fā)者提供了一個應用開發(fā)的容器，包括桌面 GIS（ArcGIS Desktop） ，嵌入式GIS（ArcGIS Engine ）以及服務端 GIS（ArcGIS Server） 。MapInfo Professional 是一套強大的基于 Windows 平臺的地圖化解決方案，可以方便地將數(shù)據(jù)和地理信息的關系直觀的展現(xiàn)，其復雜而詳細的數(shù)據(jù)分析能力可幫助用戶從地理的角度更好地理解各種信息；可以增強報表和數(shù)據(jù)表現(xiàn)能力，找出以前無法看到的模式和趨勢，創(chuàng)建高質量的地圖以便做出高效的決策；憑借其新特性和增強功能，MapInfo Professional 使得桌面地圖化和分析功能更快和更容易并可延伸至整個企業(yè)。 支持 Oracle8i 完全讀/ 寫，通過 OCI 對Oracle8i 及通過 ODBC 對其它數(shù)據(jù)源的實時訪問。MapBasic 功能強大，用戶僅用幾行代碼即可在應用軟件中實現(xiàn)圖層疊加，并具備其他地理功能。無論是熟練的還是剛入門的程序員，都能使用該語言根據(jù)用戶的需求開發(fā)出功能更加強大的桌面地圖信息系統(tǒng)應用軟件包。因此可以利用 MapBasic 進行算法的編程，而不借助于其他運籌軟件的輔助，有利于提高運算的效率。隨著科學技術的飛速發(fā)展，信息化成為時代的主旋律，如何將信息化應用到社會服務中去，形成生產力的轉化，是科學技術變?yōu)樯a力的關鍵環(huán)節(jié)。7 論文的主要工作本 論 文 是 從 工 作 中 的 實 際 體 會 和 所 學 專 業(yè) 知 識 出 發(fā) ， 對 目 前 濰 坊 市 公 安 系統(tǒng) 出 警 調 度 系 統(tǒng) 現(xiàn) 狀 所 作 的 一 些 嘗 試 和 改 進 。論文的主要內容包括 4 個方面。闡述論文的研究背景和意義，介紹 110 出警線路優(yōu)化信息系統(tǒng)的發(fā)展現(xiàn)狀及發(fā)展趨勢，重點介紹了路徑規(guī)劃算法研究現(xiàn)狀。本文以優(yōu)化道路網中路徑的阻抗權值為出發(fā)點，結合公安工作實際情況的特點，運用層次分析法（Analytic 8Hierarchy Process，簡稱 AHP）綜合評定道路的阻抗權值。針對濰坊市的路網環(huán)境，基于MapInfo 和 MapBasic 地理信息系統(tǒng)平臺，對第四章中介紹的 Dijkstra 算法和 A*啟發(fā)式算法分別進行了實現(xiàn)，通過案例研究比較兩種算法的區(qū)別，從而為 110 出警線路優(yōu)化算法的選擇提供了依據(jù)。本文所需要的道路信息主要是城市路網的矢量地圖信息，提取城市路網信息是路徑規(guī)劃的前提和基礎。通過比較各種存儲結構的不同特點，從而選取適合所選路徑算法的存儲結構，使算法的運行效率最高，是進行地圖數(shù)字化和編制算法首要工作。 地圖的存儲方法交通路網在數(shù)學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。利用簡潔的數(shù)據(jù)結構存儲道路矢量數(shù)據(jù)可以方便數(shù)據(jù)庫的維護以及優(yōu)化算法的性能。即點代表道路的交叉路口，邊代表道路。表 21 幾種圖的存儲結構名稱實現(xiàn)方法 優(yōu)點 缺點 時間復雜度鄰接矩陣二維數(shù)組系 O(n2+m*n)Adjacency Matrix 鄰接表 鏈表 的關系O(n+m)或 O(n*m)Adjacency List 入度十字鏈表 鏈表 見鄰接表Orthogonal List和入度鄰接多重表 鏈表 見鄰接表adjacency multilist系鄰 接 矩 陣 是 表 示 頂 點 之 間 相 鄰 關 系 的 矩 陣 。一般的，將路網的順序鄰接鏈表與逆向鄰接鏈表稱為 Forward 表和 Backward 表。在節(jié)點查詢中，鄰接表中的查詢時間復雜度僅為 ，在有向圖的建立算法，其時間復雜度為 。 它 可 以看 作 是 將 有 向 圖 的 鄰 接 表 和 逆 鄰 接 表 結 合 起 來 得 到 的 一 種 鏈 表 。 道路信息的存儲在對網絡拓撲關系的存儲研究方面，絕大多數(shù)研究采用了鄰接矩陣或者鄰接表等存儲方式。因此，12用一個一維數(shù)組存放圖中所有頂點數(shù)據(jù)；用一個二維數(shù)組存放頂點間關系（邊或弧）的數(shù)據(jù)，稱這個二維數(shù)組為鄰接矩陣。然后將矩陣的行和列分別定義為地圖點對象中的編號，若兩個點之間存在鄰接關系，則在對應的行列交叉處標號為 1，若不鄰接則標號 0。（2）當鄰接矩陣中的元素僅表示相應的邊是否存在時，矩陣值可定義為值為 0 和 1 的枚舉類型，1 代表相鄰，0 代表不相鄰。采用鄰接13矩陣方法來存儲網絡拓撲數(shù)據(jù)，雖然可以直接完成兩個頂點是否存在一條網絡邊的查詢，但對最短路徑算法最關鍵的關聯(lián)節(jié)點查詢，其復雜度均為 ?？紤]到本文主要研究的是兩種經典路徑最短算法，并且所采用的是基于 MapInfo 和 MapBasic 的開發(fā)環(huán)境，該環(huán)境對于數(shù)據(jù)結構復雜度的支持相對較弱，因而采用鄰接矩陣結構的存儲形式。通過比較發(fā)現(xiàn)，鄰接矩陣存儲結構更加清晰，存儲復雜度對系統(tǒng)軟件的需求更低、可操作性強、普適性好，適合于不復雜情形下的編程實現(xiàn)。其中減少道路中的時間消耗是提高工作效率的關鍵，這就涉及到最短路徑選取問題。因而可以通過對不同路段情況進行因素分析，通過綜合評價給與不同道路的阻抗系數(shù)，將阻抗系數(shù)反映到路網信息上，就可以體現(xiàn)時間最優(yōu)原則的要求。權值設定的科學與否，將會直接影響算法的適用性和優(yōu)化結果。特別是 110 警力在到達出險現(xiàn)場的過程中，需要考慮的影響因素更多，如車流量、車道數(shù)、是否有施工、行人密度、障礙物、時間段、路面狀況等等。通過加權系數(shù)的不同，能夠有效的體現(xiàn)阻抗值的變化，例如原本很短的道路由于道路條件較15差，最終加權長度將大于實際距離較長但路況較好的道路，這樣就可以體現(xiàn)時間最優(yōu)的原則。對110 出警線路最優(yōu)化的計算，是受路網交通狀況影響的路徑選擇過程?？紤]到運算的需要，可以將阻抗進行等價的變換分析，利用道路通達性來表示阻抗的大小，因而首先要對路況進行權值的設定（該權值指代根據(jù)最優(yōu)路徑選取原則設置的各種參數(shù)的加權值） 。從公安出警的實際特點出發(fā)，需要總結各種道路情況對出警效率的影響，得出在最短的時間內對各種出警狀況的有效的方案。例如道路擁堵情況越嚴重，則相應的路線阻值就應當提高，對應于系統(tǒng)中就可以對路線長度設有一定的加成系數(shù)，反之則越小。在設置加權系數(shù)時，可以認為設定系數(shù)的上下限的范圍。從目前算法研究的發(fā)展現(xiàn)狀來看，在大多數(shù)的的算法研究中，往往僅根據(jù)根據(jù)道路的長度作為最優(yōu)路徑的選取依據(jù)，雖然這種假定在算法研究中沒有負面影響，但是在現(xiàn)實情況中往往與實際不符。例如在各種城市應急系統(tǒng)（如 110 匪警、119 火警以及 120 醫(yī)療急救系統(tǒng)）等問題上，時間的因素是最重要的。在分析各種因素的權值之前，首先應該明確系統(tǒng)優(yōu)化的最終目標，即 110 出警最優(yōu)路徑規(guī)劃的指向是距離最優(yōu)還是時間最優(yōu)。但是在對時間緊迫的 110 出警環(huán)境中，顯然是不合理的。如靜態(tài)情況下選17擇平均時間作為目標取值；動態(tài)情況下以實際消耗時間作為取值，但動態(tài)情況下的數(shù)據(jù)難以獲得；借鑒交通時間與交通中其他因素之間關系來近似替代相應的阻值等等。 層次分析法層次分析法是美國運籌學家托馬斯該方法將決策進行必要的因素分析，將與決策總目標總是有關的元素分解成目標、準則、方案等層次，在此基礎之上進行定性和定量分析的決策方法 [34]。它尤其適合于人的定性判斷起重要作用、對決策結果難于直接準確計量的場合 [31]。比如當進行商店選址的決策時，抉擇者必須考慮被選地址的客流情況、交通情況、地價租金、臨近商鋪以及外圍環(huán)境等等。在社會、經濟以及科學管理領域中經常存在由相互關聯(lián)、相互制約的眾多因素構成的復雜而缺少定量數(shù)據(jù)的系統(tǒng)，層次分析法為分析解決這類問題的決策和排序提供了一種新的、簡潔而實用的建模方法。然后按照各個元素的屬性把元素進行分組，形成互不相交的層次，上一層次的元素的宏觀性較強作為準則層，對相鄰的下一層次的元素起支配作用；下層元素較為具體每一準則層里的下層元素的集合決定該準則的取值，這樣就形成了層次間自上而下的逐層支配的關系，這就是一種遞階層次關系 [29]，見圖 31。（3）最底層：該層次包括了目標決策可供選擇的各種措施、備選方案等，是較為細化的元素層，因此也稱為措施層或方案層。1?（4）屬于不相鄰的兩個層次上的任意兩個元素之間不存在支配關系，即支配關系具有不可跨越性 [35]。（二）構造成對比較陣層次結構模型建成之后，就可以對各層中的元素進行兩兩比較，構造比較判斷矩陣。判斷矩陣是層次分析法的基本信息，也是進行相對重要度計算的重要依據(jù)。根據(jù)定義可nijaA??)(AXZ?以得出，若 與 對 的影響之比為 ，則 與 對 的影響之比應為 。在層次分析法中，為了使決策判斷由定性比較轉化為定量比較，形成數(shù)值判斷矩陣，通常根據(jù)一定的比率標度將判斷定量化。使用德爾菲法的原因是，借助于專家淵博的知識和豐富的經驗對因素間的關系作出較為準確的評價，使轉化的決策信息更加符合實際。構造出判斷矩陣后，即可以對判斷矩陣進行單排列計算。而應用層次分析法，保持判斷思維的一致性是至關重要的。應用一致性檢驗可以有效的幫助決策者檢查并保持判斷矩陣的一致性 [35]。并且當矩陣 具有完[]ijnAa??1ia1ni??A全一致性時， ，其余特征根均為零；而當矩陣 不具有完全一致性時，1max?則有 ，其余特征根 有如下關系： 。可以看出，當判CI斷矩陣具有完全一致性時， ，即當 ，判斷矩陣具有完全0CI?1max0,In??一致性。 值的計算是用隨機方法構造 500 個樣本矩陣，隨機地RIRI從 1~9 及其倒數(shù)中抽取數(shù)字構造正互反矩陣，求得該矩陣的最大特征根的平均值，并定義max39。當階數(shù)大于 2 時，判斷矩陣滿足一致性要求的難度會越來越大，因而對應的 RI 值也會逐漸增大，由于 RI 是隨機狀態(tài)下的一致性數(shù)值，因而可以用來當做衡量其他判斷矩陣的參考標準，即將判斷矩陣的 值與同階CI平均隨機一致性指標 之比作為一致性檢驗的標準，稱為隨機一致性比率，記RI為 。層次單排序的結果僅僅對應為判斷矩陣建立時所在的層次，表示當前層的元素對應于上層準則的權重。1niijMa??,2n?（2） 計算 的 次方根 ， 。AWi該方法被稱作方根法，是一種求解特征根和特征向量的簡易方法，在精度要求不高的情況下使用可以降低計算的難度。即通過已經的到的權重值自上而下地將單準則下的權重進行合成。具體見表 33。10.?CR在應用層次分析法分析實際問題時，需要關注兩點問題一是跟據(jù)實際情況構造出科學而又貼近實際的層次結構；二是如何使定性的因素變量轉化為接近實際的定量數(shù)據(jù)。通過前面層次分析法的處理，就可以得到每個因素對于總目標的影響權重，然后就可以對每條路段的各個隱私進行評價打分，按照所得權重進行加權最終得到道路的阻抗系數(shù)。其中四個因素的選取依據(jù)是道路車道數(shù)和道路路況情況反映道路的硬件條件，硬件條件越好越有利于通行；人員密集度和平均車流量體現(xiàn)了交通的通行狀態(tài)，車流量和行人流量越大，對車輛的交通起到阻礙的作用。A = ?????? .429 .273. 5. . .3利用 MatLab 的矩陣處理功能，得到矩陣 A 的特征值矩陣 D 和特征向量矩陣 V。表 34 判斷矩陣及權重A B1 B2 B3 B4 重要性權重值B1 B2 B3 B4 得到阻抗評價體系的權重以后，就可以對各個路段的實際情況進行阻抗值的評定。將得分乘以層次分析法得到的權重值進行加權，得到總得分為 。其他的按比例進行調整。由于影響道路通達性的因素很多，因此需要用到 AHP 層次分析法進行各個因素的權重設置。通過進行各種因素