【正文】 間取值上述值的倒數(shù) 兩個因素相比，前者比后者的不重要性，其等級為相應重要性等級的倒數(shù)在對較復雜問題進行決策時，其判斷矩陣是往往要通過咨詢多位專家進行評價判斷，也稱之為德爾菲法。設要比較的 個元素為 ，要得出對這 個元素對上層元素 的n},{1nxX??nZ影響相對大小，可以采取對因子進行兩兩比較建立成對比較矩陣的辦法。每一層次中各元素所支配的元素一般不要超過 9 個。這些層次可以劃分為三種類型：（1）最高層：該層次中只有一個元素，它是所需解決問題的預定目標和決19策的最終依據(jù)，因此也稱為目標層。在很多決策系統(tǒng)中因素之間的重要性比較往往無法用定量的方式描述（例如交通與租金因素的比較） ，此時就需要將半定性、半定量的問題轉化為定量計算問題，這正是層次分析法所要解決的問題。具體的說，它是指將決策問題的有關元素分解成目標、準則、方案等層次，用一定的尺度標準對人的主觀判斷（應用如頭腦風暴、德爾菲法、群決策方法等）進行客觀量化，在此基礎上進行定性分析和定量分析的一種決策方法。根據(jù)前文的論述選取平均車流量、道路車道數(shù)、道路路況情況、人員密集度四個指標建立影響道路通達性的靜態(tài)阻抗評價指標體系，實際中涉及的因素還有很多，本文主要是進行方法研究，因此僅以靜態(tài)條件的影響因素進行研究。雖然該方案較為直觀和簡單，但實用性較差（在具體的算法研究和比較中可以當做基礎數(shù)據(jù)進行算法驗證） 。阻礙強度不僅僅指一般意義上的距離最短，還可以引申到其它的度量，如時間、費用、線路容量等。隨著信息技術的不斷發(fā)展，道路實時監(jiān)控也逐漸達到普及。在城市交通網(wǎng)絡中，道路長度最短的路徑不一定是耗時最短的 [28~31]。 道路阻抗值110 控制臺接到報警后，從安排出警到抵達案發(fā)地點往往時間緊迫，稍有延誤后果可能是非常嚴重的。該體系要求能夠基本包括實際工作中能夠影響出警時間的影響變量。選取阻抗作為度量的主要考慮是 110 出警狀況與普通的物流需求不同，減少時間的消耗是 110 出警的首要目標。 本章小結本章首先介紹了圖形學的基本理論，根據(jù)路網(wǎng)圖形理論介紹了 4 種路網(wǎng)存儲結構的相關內容。（4）鄰接矩陣表示法的空間復雜度為 [27]。鄰接矩陣的定義還可以繼續(xù)加以擴展，可以包括點的鄰接、邊的鄰接以及區(qū)域的鄰接。 鄰接 多 重 鏈 表 類 似 于 有 向 圖 表 示 法 中 的 十 字 鏈 表 ， 將 無 向 圖 中 表 示 同 一 條 邊 的 兩個 節(jié) 點 合 在 一 起 ， 將 得 到 無 向 圖 的 鄰 接 多 重 表 。二ivjvj是鏈域。道路的權值可以作為道路的內部屬性存儲。由于矢量地圖存儲數(shù)據(jù)量大，地圖數(shù)據(jù)關系復雜，不同的數(shù)據(jù)存儲結構對路徑規(guī)劃算法性能也有不同的影響。目前圖的存儲結構主要有四種分別是鄰接矩陣、鄰接表、鄰接多重表和十字鏈表。主要研究了盲目搜索和啟發(fā)式搜索兩種算法的特點，并以 Dijkstra 算法和 A*啟發(fā)式算法作為代表進行研究，對二者的優(yōu)缺點進行了比較，對算法的特點進行了分析。 論文的章節(jié)安排本文通過對現(xiàn)有最優(yōu)路徑搜索算法進行研究，選擇適合城市道路條件下 110出警工作的最優(yōu)算法，并利用地理信息系統(tǒng)軟件平臺進行實現(xiàn)，構造城市公安調度系統(tǒng)的路徑優(yōu)化選擇應用模塊，從而達到提高 110 出警效率的目的。本論文將信息技術、運籌學和地理學等理論知識相結合，應用到 110 公安調度系統(tǒng)，通過對濰坊市 110 出警現(xiàn)狀的調查和分析，研究一套適合城市最優(yōu)出警路線的選擇方法，并利用地理信息系統(tǒng)專用軟件（MapInfo、MapBasic）開發(fā)出可以應用于公安調度系統(tǒng)的算法模塊，實現(xiàn)出警路線的自動化優(yōu)化選擇。MapBasic 具有五個方面的特點，它是一種類 Basic 語言，幫助用戶開發(fā) MapInfo 應用軟件；支持 OLE Automation 和 DDE 技術使之易于與其他應用軟件相連接；包含嵌入的 SQL 語句以具有更強大的數(shù)據(jù)查詢功能；地理操作和功能幫助能擴展應用軟件的功能。MapBasic 是理想的在 MapInfo 平6臺上開發(fā)用戶定制的應用程序的編程語言。它依據(jù)地圖及其應用的概念、采用辦公自動化的操作、集成多種數(shù)據(jù)庫數(shù)據(jù)、融合計算機地圖方法、使用地理數(shù)據(jù)庫技術、加入了地理信息系統(tǒng)分析功能，形成了極具實用價值的、可以為各行各業(yè)所用的大眾化小型軟件系統(tǒng)。目前，地圖處理工具種類繁多，如 MAPGIS，ArcGIS ，MapInfo 等。陳湘州等引入一種進化逆轉算子，改進了遺傳算法求解VRP 時的局部搜索能力 [19]。1974 年，Wren Gillett 等人提出 Sweep 算法（掃描法） 。Hall等人證明了標準的求最短路徑的規(guī)劃算法（如 Dijkstra 算法）在動態(tài)路網(wǎng)中規(guī)劃的路徑不是最優(yōu)的 [10]。在經典 VRP（ Vehicle Routing Problem， 車輛路徑問題） 的基礎上，車輛路徑問題在學術研究和實際應用上產生了許多不同的延伸和變化形態(tài) [5]。 本 文 所 研 究 的 公 安 最 優(yōu) 路 徑 系 統(tǒng) 屬 于 交 通 路 網(wǎng) 的 交 通 事 故 應 急 救 援 系 統(tǒng)3的 一 個 部 分 ， 交 通 路 網(wǎng) 優(yōu) 化 研 究 是 該 系 統(tǒng) 的 主 要 內 容 之 一 。受當時的數(shù)據(jù)和技術條件的限制，該系統(tǒng)僅僅在少數(shù)幾個試點城市應用，但是從此之后，其它各城市便開始研制和開發(fā)各自的治安管理系統(tǒng)。110 出警線路優(yōu)化系統(tǒng)針對于城市公安部門的工作需要具有城市路網(wǎng)的空間內涵，同時具有集成化的優(yōu)化分析功能，實現(xiàn)最優(yōu)的調配。2022 年，110 報警服務平臺共出警 511 萬人次，平均每分鐘出警 10 次，各類案件的偵破率也相應得到提高，由此可見 110 報警服務平臺正發(fā)揮著越來越重要的作用 [1]。當 110 指 揮 中 心 接 到 群 眾 報 警 后 ， 部 署 警 力 能 夠 在 盡 可 能 短 的 時 間 內到 達 現(xiàn) 場 ， 不 僅 可 以 更 大 概 率 的 捕 獲 疑 犯 ， 控 制 現(xiàn) 場 秩 序 ， 還 能 盡 早 的 控 制 現(xiàn)場 獲 取 第 一 手 現(xiàn) 場 資 料 。它能夠提供業(yè)2務上的數(shù)據(jù)處理、統(tǒng)計、指揮調度以及實時處理、控制顯示等功能，提高 110 公安部門的指揮決策水平和整體作業(yè)能力及反應速度。1995 年公安部以鄭州、南寧、大連和廈門作為試點城市，建立了以城市公安 GIS 為中心的 110 接處警系統(tǒng) [4,5]。 路徑規(guī)劃算法發(fā)展現(xiàn)狀最短路徑問題是路線設計及分析等優(yōu)化問題的基礎，其算法是交通網(wǎng)絡分析的核心。110 出警線路優(yōu)化信息系統(tǒng)中的最優(yōu)路徑規(guī)劃問題就是搜索網(wǎng)絡中兩點之間通行能力最強的路徑，其核心是最短路徑算法問題。Pearl 等人成功采用 A*算法用于路網(wǎng)的路徑規(guī)劃，并分析了算法的復雜性。1981 年，Christofields 等人提出了 度中心樹和相關算法。顧志康等針對染色體中某些需求點編號可能重復出現(xiàn)的情況，設計新的染色體結構，并通過基因的混合交叉方法進行基因重組，有效提高了搜索到最優(yōu)配送路徑的概率 [20]。特別的MapInfo 軟件自帶二次開發(fā)軟件 MapBasic，具有優(yōu)良的兼容性和匹配性，并接語言簡單，適合普通地信人員使用。MapInfo 含義是“Mapping + Information（地圖+信息） ”即：地圖對象+ 屬性數(shù)據(jù)。通過使用 MapBasic 進行二次開發(fā)，能夠擴展 MapInfo 功能，實現(xiàn)程序的自動重復操作并使 MapInfo 與其他應用軟件集成。已有上千種使用 MapBasic 開發(fā)出的、能夠解決商務問題的應用軟件。從而達到提高 110 警務系統(tǒng)的工作效率，更好的滿足社會治安工作的需要。針對以上研究目的和研究內容，全文共分為六章，具體如下：第一章引言。第五章 110 出警路徑最優(yōu)化算法的實現(xiàn)。這些存儲結構有各自的應用范圍和不同的結構特點。因此如何選擇路徑規(guī)劃算法和相對應的存儲結構，使整體的效率最高，也是一個需要解決的問題 [24]。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表表示，其優(yōu)缺點的比較見表 21[25]。將鄰接表的所有表節(jié)點鏈在一起。 這 兩 種 網(wǎng) 絡 存 儲 方 式 結 構 較 為復 雜 ， 實 現(xiàn) 的 運 算 量 很 大 ， 因 此 只 有 在 特 殊 情 況 下 才 會 使 用 [26]。具體思想是，首先提取路網(wǎng)中的所有節(jié)點，并在圖層上創(chuàng)建點對象，對每個點進行編號。2()SnO?在實際操作中，鄰接矩陣還可以添加其他的相關信息，例如當采用點的鄰接矩陣作為路網(wǎng)存儲結構時，可以將鄰接關系 1 用距離關系來代替，如 與 相鄰iVj接，可以將 與 之間的距離值作為矩陣中 與 行列點的數(shù)值，如此在路徑優(yōu)iVj iVj化算法中可以直接獲得路網(wǎng)中各個弧邊的距離信息，方便算法的計算。并比較了鄰接矩陣、鄰接表、鄰接多重表和十字鏈表等存儲結構的特點和適用范圍。交通阻抗衡量的主要因素是交通時間，它受到交通路網(wǎng)多方面條件的制約，例如道路距離長度，道路暢通性、車流量的密集度以及路況條件等。因為在實際城市交通網(wǎng)絡中，道路長度最短的路徑不一定是耗時最短的。為了將損失降低到最低程度，公安部門需要解決的問題是如何迅速調動警力趕赴案發(fā)現(xiàn)場，這就涉及到路徑選取的目標取向問題。如何設定最優(yōu)路徑阻抗權值的評價指標體系也是設計權值的重要前提，影響 110 出警時間的因素很多，如道路通達性、道路車道數(shù)、道路擁擠度、不同時段流量、路況等等。從技術上來說，已經達到可以根據(jù)實時路況的信息對不同路段的擁擠度進行動態(tài)的跟蹤，從而根據(jù)車輛接受的交通路況信息來動態(tài)的確定加權系數(shù)的大小。根據(jù)實際情況的不同，選取的標準也不盡相同。因為以實際距離最短作為目標只適用于暢通度極好的路網(wǎng)的情況，或者路網(wǎng)非常簡單并且路段差異度較大的情況。下面將利用 AHP 層次分析法建立各個指標的權重并進行評價。它把人的判斷思維過程層次化、數(shù)量化，并用數(shù)學為分析、決策、預報或控制提供定量的依據(jù)。層次分析法將復雜的決策系統(tǒng)層次化，通過逐層比較各種關聯(lián)因素的重要性來為分析、決策提供定量的依據(jù) [32]。（2）中間層：該層次中包含了為目標決策所涉及的中間環(huán)節(jié)，一般通過對目標層按一定的劃分準則進行分解，它可以由若干個層次組成，包括所需考慮的準則、子準則，因此也稱為準則層。這是因為支配的元素過多會給兩兩20比較判斷帶來困難 [35]。即分別對兩個元素 和 進行比較，以 表示 和 對 的影響大小之比，將比較結ixj ijaijZ果用矩陣 表示，稱 為 之間的成對比較判斷矩陣。特爾斐法是一個使專家集體在各個成員互不見面的情況下對某一項指標的重要性程度達成一致看法的方法。對于根據(jù)實際問題建立的判斷矩陣往往由于各種原因會出現(xiàn)判斷不一致的情況，特別是在判斷因素比較多的時候，判斷矩陣的一致性往往無法滿足。根據(jù)矩陣理論，如果 是滿足式 的數(shù)，也就是矩陣12,n?? Ax??的特征根，并且對于所有的 ，有 。一般的通過引入平均隨機一致性指標值，作為衡量參數(shù)。具體方法是求得判斷矩陣 中最大特征向量 所對應的特征向量 ，對 進行歸一化后，Amax?W所得到的結果即為相應因素對于上一層次因素相對重要性的排序權值，也被稱為層次單排序。1iinjj??12[,]Tn?24（4） 計算判斷矩陣的最大特征根 ，其中， 表示向量max1()niiAW???()iA的第 個元素。jAnjjb,1? ij 0?ijb則 層中各因素關于總目標的權重，即 層各因素的層次總排序權重 ，B n,1?可由公式 ， 得到。對于本文要決策的問題，因為所涉及的因素并不是非常復雜，并且對精度的要求也有限，因而層次分析法具有較好的適用性。阻抗系數(shù)平均車流量 道路車道數(shù) 道路路況情況 人員密集度B1 B2 B3 B4A圖 32 道路阻抗評價的層次結構模型首先，對第一步層次模型中的 4 個變量兩兩進行比較，應用 9 標度法進行標記，得到判斷矩陣 A。因而可以給與 8，1，1，7 的得分。28 本章小結本章首先從 110 公安出警的實際特點出發(fā)，選取車輛的道路耗費時間最短作為衡量線路優(yōu)劣的選擇標準，因而設置道路阻抗值作為評價道路通達性的指標。文中給出了層次分析法的具體應用過程，選取平均車流量、道路車道數(shù)、道路路況、人員密集度 4 個指標作為阻抗值的影響因子。將各個道路分別根據(jù)這四個因素進行打分，就得到初步的阻抗值系數(shù)。27D = ??????? 0 . .247i .851 V = ?????? ?? .91i .91i .719 724245 .8 .7 .7 .86 由此矩陣計算得： ，所以，該判,6max ???RICI?斷矩陣的一致性可以接受。 層次分析法在阻值設置上的應用在路徑優(yōu)化算法中，應用層次分析法主要是為了設置道路阻抗，前面說過影響道路阻抗的因素有很多，因而如何建立層次結構模型是十分關鍵的一步。??mjjiiab1n,?表 33 層次總排序的方法A1 A2 … Am B 層總排序權重指標 a1 a2 … amB1 b11 b12 … b1m 1mjja??B2 b21 b22 … b2m 21jj… … … … …Bn bn1 b2n … bnm 1mjja?因為層次總排序是根據(jù)前面層次單排序所得結果的分解和加權，因此一致性25一般可以滿足，但是由于各層次的非一致性誤差仍有可能積累起來，引起最終分析結果可能存在著非一致性。當然還有其他一些建議算法解決該類問題，在此不做贅述，在計算軟件較為發(fā)達的今天，可以應用 MatLab 等矩陣處