【正文】 ............................................................................................................28 最短路徑算法 ........................................................................................................28 DIJKSTRA 算法 .......................................................................................................31 A*算法 ...................................................................................................................33 本章小結(jié) ................................................................................................................38第五章 110 出警路徑最優(yōu)化算法的實(shí)現(xiàn) ....................................................................40 引言 ........................................................................................................................40 地圖數(shù)字化 ............................................................................................................40 數(shù)字化平臺(tái) ....................................................................................................41 路網(wǎng)信息的提取 ............................................................................................42 算法實(shí)例研究 ........................................................................................................47 Dijkstra 算法 ...................................................................................................47 A*算法 ............................................................................................................50 結(jié)果分析 ........................................................................................................52 本章小結(jié) ................................................................................................................53第六章 總結(jié)和展望 .......................................................................................................54致謝 .................................................................................................................................56參考文獻(xiàn) .........................................................................................................................571第一章 引言 研究背景及意義 研究背景社 會(huì) 治 安 狀 況 關(guān) 系 到 每 個(gè) 公 民 的 生 命 和 財(cái) 產(chǎn) 安 全 ， 建 設(shè) 高 效 率 的 公 安 系 統(tǒng)是 關(guān) 系 到 人 民 能 否 安 居 樂(lè) 業(yè) 的 重 要 問(wèn) 題 。 隨 著 信 息 化 的 普 及 和 發(fā) 展 ， 為 了 適 應(yīng) 公 安 現(xiàn)代 化 建 設(shè) 的 需 要 ， 應(yīng) 當(dāng) 充 分 利 用 先 進(jìn) 的 通 訊 手 段 和 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 技 術(shù) 并 結(jié) 合 各 種科 學(xué) 發(fā) 展 的 高 新 技 術(shù) 成 果 為 公 安 系 統(tǒng) 服 務(wù) 。之后到 90 年代，挪威主持開(kāi)發(fā)的 POS 系統(tǒng)是將 GIS 真正應(yīng)用于治安管理并取得成功的系統(tǒng) [4]。城 市 應(yīng) 急 聯(lián) 動(dòng) 系 統(tǒng) 一 般 包 括 城 市 生 活 中 各 種 緊 急 事 件 的 應(yīng) 急 服 務(wù) ， 例 如 ：110 報(bào) 警 服 務(wù) 臺(tái) 、 火 警 、 急 救 、 交 警 、 消 費(fèi) 者 投 訴 電 話 、 法 律 援 助 電 話 等 指 揮平 臺(tái) ， 這 樣 通 過(guò) 將 各 個(gè) 社 會(huì) 保 障 部 門(mén) 的 信 息 進(jìn) 行 集 成 能 夠 使 各 個(gè) 部 門(mén) 共 享 各 種資 源 ， 實(shí) 現(xiàn) 跨 部 門(mén) 、 跨 地 區(qū) 的 統(tǒng) 一 指 揮 協(xié) 調(diào) ， 對(duì) 于 提 高 各 部 門(mén) 對(duì) 突 發(fā) 事 件 的 反應(yīng) 能 力 提 供 了 必 要 的 條 件 [6]。經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)，各具特色。Dijkstra 算法建立在抽象的網(wǎng)絡(luò)模型上，把道路抽象為網(wǎng)絡(luò)中的邊，以邊的權(quán)值來(lái)表示與道路相關(guān)的參數(shù)，算法確定了賦權(quán)網(wǎng)絡(luò)中從某點(diǎn)到所有其它節(jié)點(diǎn)的具有最小權(quán)的路徑。MillerHooks 和 Mashmassani 提出了在離散時(shí)間不穩(wěn)定隨機(jī)情況下，最小期望代價(jià)路徑的搜索算法，證明了算法的存在性，并和其他算法進(jìn)行了比較 [13,14]。鑒于傳統(tǒng)的遺傳算法是個(gè)大范圍、粗粒度的尋優(yōu)算法，Barnier 將其與約束滿足問(wèn)題（CSP）的技術(shù)相結(jié)合，通過(guò)遺傳算法來(lái)處理CSP 參數(shù)的子域，從而減小搜索空間，降低 CSP 問(wèn)題目標(biāo)函數(shù)和遺傳算法約束的復(fù)雜度 [17]。華中科技大學(xué)李寧等人將粒子群算法運(yùn)用于車(chē)輛路徑優(yōu)化問(wèn)題，并進(jìn)行了實(shí)驗(yàn)研究，證明了粒子算法在求解車(chē)輛路徑問(wèn)題的有較好的性能 [22]。ArcGIS 產(chǎn)品線為用戶提供一個(gè)可伸縮的，全面的 GIS 平臺(tái)。通過(guò) MapInfo Professional 可連接本地及服務(wù)器端的數(shù)據(jù)庫(kù)，創(chuàng)建地圖和圖表以揭示數(shù)據(jù)行列背后的真正含義。MapBasic 已經(jīng)被世界上數(shù)百個(gè)第三方廠商認(rèn)可。作為現(xiàn)代經(jīng)濟(jì)社會(huì)不可或缺的公安保障體系，同樣應(yīng)當(dāng)吸取現(xiàn)代科學(xué)帶來(lái)的技術(shù)成果，與時(shí)俱進(jìn)、提高效率。 在 信息 化 愈 加 發(fā) 達(dá) 的 今 天 ， 將 信 息 化 技 術(shù) 和 智 能 優(yōu) 化 算 法 融 入 到 公 安 系 統(tǒng) 的 日 常 工作 ， 可 以 最 大 程 度 的 減 少 人 的 工 作 強(qiáng) 度 ， 并 且 能 夠 得 到 最 優(yōu) 處 理 結(jié) 果 。介紹了各種城市路網(wǎng)矢量地圖存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，最終選取鄰接矩陣對(duì)城市道路信息進(jìn)行儲(chǔ)存。對(duì)全文進(jìn)行總結(jié)，并提出了有待深入研究的問(wèn)題。考慮到不同的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)對(duì)路徑規(guī)劃算法性能影響是很大的，因此本文從經(jīng)典的路網(wǎng)結(jié)構(gòu)中進(jìn)行選取，使之滿足案例研究中要實(shí)現(xiàn)的算法功能。網(wǎng)絡(luò)在數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域中被抽象為圖，所以其基礎(chǔ)是圖的存儲(chǔ)表示 [25]。鄰接矩陣是唯一一種可用矩陣表示的數(shù)據(jù)結(jié)構(gòu)，因此在軟件實(shí)現(xiàn)中具有較大的優(yōu)勢(shì)，在 Dijkstra 算法中較為廣泛，是 Dijkstra 算法的基礎(chǔ)存儲(chǔ)結(jié)構(gòu) [25]。鄰接表數(shù)據(jù)結(jié)構(gòu)是網(wǎng)絡(luò)表達(dá)中效率較高的一種數(shù)據(jù)結(jié)構(gòu)，在最短路徑算法中已經(jīng)得到了廣泛應(yīng)用 [25]。鄰接矩陣方法最為直觀，雖然其空間復(fù)雜程度較高，但是可以利用矩陣結(jié)構(gòu)進(jìn)行網(wǎng)絡(luò)的存儲(chǔ)，因而該結(jié)構(gòu)的算法適宜度高，可以應(yīng)用到多種算法之中。例如圖 21 中無(wú)向圖 G5 和有向圖 G6 的鄰接矩陣可以分別表示為 Al 和 A2。但由于鄰接矩陣具有較2()On好的直觀性的普適性，因而在最短路徑算法中得到了廣泛應(yīng)用 [27,28]。14第三章 城市道路阻抗權(quán)重的確定 引言110 公安報(bào)警服務(wù)平臺(tái)已經(jīng)成為城市居民生活中必不可少的保障因素，基本上所有的急發(fā)事故都會(huì)涉及到 110 工作的范疇。因而在對(duì)最優(yōu)路徑算法的實(shí)踐中往往通過(guò)分析路徑的阻抗權(quán)值來(lái)決定。道路阻抗權(quán)值在理想的情況下應(yīng)以實(shí)際的行程時(shí)間作為路段的路阻。為了更加方便最優(yōu)路徑運(yùn)算的需要，在這里引入阻抗的概念，阻抗是借用物理學(xué)中的概念，主要以交通時(shí)間作為度量單位，表示在行程上所占用的時(shí)間?？紤]本文主要是進(jìn)行算法研究，以及所采用數(shù)據(jù)因素的限制，本文通過(guò)阻抗權(quán)值的加權(quán)系數(shù)來(lái)反映道路網(wǎng)絡(luò)的通達(dá)性信息，設(shè)定路段的阻值等于路段的實(shí)際長(zhǎng)度與加權(quán)系數(shù)的乘積。由于修路或其他原因?qū)е侣范螣o(wú)法通行的，則設(shè)置其權(quán)值為無(wú)窮大，其他情況可以根據(jù)交通主管部門(mén)觀測(cè)到的實(shí)時(shí)路況的平均車(chē)速將路段的加權(quán)系數(shù)設(shè)為 1 和 9 之間的某個(gè)值。由于影響出警車(chē)輛到達(dá)時(shí)間的因素很多，實(shí)際長(zhǎng)度最短的路徑不一定耗時(shí)最短，僅考慮道路長(zhǎng)度得出的優(yōu)化結(jié)果往往與真實(shí)情況差異很大，因而有關(guān)研究文獻(xiàn)中將車(chē)流量、車(chē)道數(shù)、道路等級(jí)、路面狀況、時(shí)間段等因素都納入到道路網(wǎng)的信息中。很明顯出警時(shí)間最短應(yīng)當(dāng)作為阻值權(quán)重的首要目標(biāo)。層次分析法（Analytic Hierarchy Process 簡(jiǎn)稱(chēng) AHP）是將決策總是有關(guān)的元素分解成目標(biāo)、準(zhǔn)則、方案等層次，在此基礎(chǔ)之上進(jìn)行定性和定量分析的決策方法。 層次分析法的基本原理在現(xiàn)實(shí)生活中，難免會(huì)遇到多屬性決策的問(wèn)題，比如高考志愿填報(bào)、商店選址、投資計(jì)劃等等。（一）建立層次結(jié)構(gòu)模型應(yīng)用層次分析法分析決策問(wèn)題時(shí)，首先要對(duì)該決策問(wèn)題有清晰的了解，把問(wèn)題條理化、層次化，構(gòu)造出一個(gè)層次清晰的結(jié)構(gòu)模型。（2）同一個(gè)層次中的任兩個(gè)元素之間不存在從屬或支配的關(guān)系，即層次的劃分具有一致性。層次分析法主要是對(duì)每一層次中各因素的相對(duì)重要性做出判斷，這些判斷通過(guò)引入合適的標(biāo)度用數(shù)值表示出來(lái)，寫(xiě)成判斷矩陣。進(jìn)一步講若正互反矩陣 中的元素滿足：nij?)( A， ，ikjiaj,??則稱(chēng) A 為一致矩陣。若只作 個(gè)比較有可能會(huì)使任何一個(gè)判斷的失2)1(?n 1?n誤導(dǎo)致不合理的排序，而個(gè)別判斷的失誤對(duì)于難以定量的系統(tǒng)往往是難以避免的。但是要求判斷矩陣具有相對(duì)的一致性是可以達(dá)到的。綜上所述，可以引入判斷矩陣最大特征根以外的其余特征根的負(fù)平均值作為層次分析法中度量判斷矩陣偏離一致性的指標(biāo)，即用 1max??nCI?（）度量決策者判斷思維的一致性。max??nI?值的取值如表 32 所示 [35]。因而可以用一種近似但較為簡(jiǎn)單的方法進(jìn)行計(jì)算。（四）層次總排序及一致性檢驗(yàn)層次單排序中得到的是一組元素對(duì)其上一層中某元素的權(quán)重向量。因此對(duì)層次總排序也需作一致性檢驗(yàn)，檢驗(yàn)仍像層次總排序那樣由高層到低層逐層進(jìn)行。根據(jù)前文的分析，在本文中選取平均車(chē)流量、道路車(chē)道數(shù)、道路路況情況、人員密集26度四個(gè)指標(biāo)建立影響道路通達(dá)性的靜態(tài)阻抗評(píng)價(jià)指標(biāo)體系，下面將利用 AHP 層次分析法建立各個(gè)指標(biāo)的權(quán)重并進(jìn)行評(píng)價(jià)打分，得到路段的阻抗系數(shù)。因而對(duì)最大特征值所對(duì)應(yīng)的特征向量進(jìn)行歸一化，即得到各種因素的權(quán)重值。一般的道路阻抗系數(shù)對(duì)于 110 出警車(chē)輛的影響是有限的，因而我們?cè)O(shè)定阻抗系數(shù)的上限為 2，下限為 1。利用 AHP 法對(duì)這四個(gè)因子進(jìn)行了權(quán)重設(shè)置，得到了最終的權(quán)重結(jié)果。在進(jìn)行路徑尋優(yōu)時(shí)，體現(xiàn)時(shí)間代價(jià)的最小原則。以東風(fēng)街為例，東風(fēng)街為 4 車(chē)道，車(chē)流量偏多，路況情況良好，行人密集度較大。具體結(jié)構(gòu)見(jiàn)圖 32。二是層次分析法只能屬于較為粗略的量化辦法，不能用于精度要求較高的決策問(wèn)題。最底層（ 層）包含 個(gè)因素 ，ma,1? BnnB,1?它們關(guān)于 的層次單排序權(quán)重分別為 （當(dāng) 與 無(wú)關(guān)聯(lián)時(shí)， ） 。12[,]T?，則 即為所求的特征向量。經(jīng)過(guò)對(duì)判斷矩陣的一致性檢驗(yàn)，就可以得到各個(gè)因素的權(quán)重值。因此為了比較不同階的判斷矩陣是否具有滿意一致性，需引入一種衡量機(jī)制。若檢驗(yàn)通過(guò)，則將歸一化的特征向量做為權(quán)向量；若不通過(guò)，則需重新構(gòu)追成對(duì)比較陣。建立判斷矩陣以后需要對(duì)判斷矩陣的一致性進(jìn)行判斷，進(jìn)行一致性檢驗(yàn)的原因是專(zhuān)家在判斷指標(biāo)重要性時(shí)，各個(gè)判斷之間可能存在不一致的情況。下表 31 列出了 9 標(biāo)度的含義：表 31 9 標(biāo)度法的含義標(biāo)度 定義說(shuō)明1 兩個(gè)因素相比，具有相同重要性213 兩個(gè)因素相比，前者比后者稍重要5 兩個(gè)因素相比，前者比后者明顯重要7 兩個(gè)因素相比，前者比后者強(qiáng)烈重要9 兩個(gè)因素相比，前者比后者極端重要2，4，6，8 分別代表上述相鄰判斷的中