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