利用城市監(jiān)控卡口網(wǎng)絡(luò)的最優(yōu)追蹤路徑規(guī)劃

孫 鵬 董 帥 郎宇博 王大宇 單大國

（1 中國刑事警察學(xué)院聲像資料檢驗(yàn)技術(shù)系 遼寧 沈陽 110035；2 江西省經(jīng)濟(jì)犯罪偵查與防控技術(shù)協(xié)同創(chuàng)新中心 江西 南昌 330103；3 防城港市公安局物證鑒定中心 廣西 防城港 538000）

1 引言

隨著全球城市化進(jìn)程的加快，城市安全問題變得越來越嚴(yán)重[1]。為了維護(hù)社會(huì)穩(wěn)定，許多城市已經(jīng)建立了城市監(jiān)控卡口網(wǎng)絡(luò)系統(tǒng)?，F(xiàn)階段城市監(jiān)控卡口的主要任務(wù)只是簡單的對(duì)道路上機(jī)動(dòng)車輛進(jìn)行測(cè)速和了解路面狀況，在維護(hù)城市安全方面城市監(jiān)控卡口的利用效率比較低，因此，如何高效的利用城市監(jiān)控卡口網(wǎng)絡(luò)維護(hù)城市安全成為公安機(jī)關(guān)十分關(guān)注的問題。當(dāng)偵查員發(fā)現(xiàn)犯罪嫌疑人行蹤時(shí)，公安人員要制定計(jì)劃對(duì)犯罪嫌疑人進(jìn)行抓捕，對(duì)于追蹤犯罪嫌疑人的路徑基本上是偵查員憑借自己的主觀意志判斷沒有任何科學(xué)依據(jù)，這種不科學(xué)性就可能導(dǎo)致犯罪嫌疑人有充分的時(shí)間進(jìn)行逃竄或者二次作案。針對(duì)這個(gè)問題并結(jié)合視頻偵查實(shí)際工作需要，本文提出了一種利用城市監(jiān)控卡口網(wǎng)絡(luò)尋找最優(yōu)路徑追蹤犯罪嫌疑人的視頻偵查方法。

近些年國內(nèi)外學(xué)者分別從城市交通擁擠、智能交通、物流運(yùn)輸?shù)冉嵌葘?duì)如何規(guī)劃城市間最優(yōu)路徑進(jìn)行了研究。文獻(xiàn)[2]通過對(duì)傳統(tǒng)Dijkstra算法的研究與分析，在此基礎(chǔ)上加入交通因素，提出一種基于城市路網(wǎng)的最優(yōu)路徑規(guī)劃算法。文獻(xiàn)[3]提出了一種基于出行者特性的最優(yōu)路徑搜索算法思想，在MapX矢量地圖環(huán)境下對(duì)該算法進(jìn)行了實(shí)現(xiàn)。文獻(xiàn)[4]將人工智能領(lǐng)域的A*算法引入到矢量地圖的最優(yōu)路徑搜索中來，論述了應(yīng)用于矢量地圖最優(yōu)路徑搜索的A*算法是一種完備的算法。文獻(xiàn)[5]通過對(duì)公共交通路線票價(jià)和運(yùn)作模式結(jié)構(gòu)的分析，提出了一種增強(qiáng)的路由計(jì)算算法，給出了更合乎邏輯的不同結(jié)構(gòu)結(jié)果。以上這些文獻(xiàn)的主要研究是城市交通問題，沒有涉及到城市安全問題，并且方法的時(shí)間和空間復(fù)雜度相對(duì)較高。

2 本文方法

本文提出了一種利用城市監(jiān)控卡口網(wǎng)絡(luò)尋找最優(yōu)路徑追蹤犯罪嫌疑人的視頻偵查方法，主要?jiǎng)?chuàng)新點(diǎn)包括：通過對(duì)城市道路監(jiān)控卡口位置以及各卡口相對(duì)關(guān)系等參數(shù)進(jìn)行初始化，生成城市監(jiān)控卡口網(wǎng)絡(luò)模型圖G（V，E，C）；利用監(jiān)控卡口采集車輛經(jīng)過相鄰卡口的通行時(shí)間，利用數(shù)據(jù)一致性檢驗(yàn)、數(shù)據(jù)融合處理、自適應(yīng)加權(quán)融合處理得到通行時(shí)間數(shù)據(jù)，將其作為城市監(jiān)控卡口網(wǎng)絡(luò)圖中該段道路的通行能力的優(yōu)化指標(biāo)，對(duì)監(jiān)控卡口覆蓋區(qū)域內(nèi)的不同道路車輛通行時(shí)間進(jìn)行優(yōu)化處理。將各道路最優(yōu)通行時(shí)間融入到城市監(jiān)控卡口網(wǎng)絡(luò)模型圖中，并運(yùn)用Floyd算法規(guī)劃出追蹤犯罪嫌疑人的最優(yōu)路徑。

具體的方法流程如圖1所示：

圖1 基于城市監(jiān)控卡口網(wǎng)絡(luò)的最優(yōu)路徑規(guī)劃流程圖

2.1 城市監(jiān)控卡口網(wǎng)絡(luò)模型

2.1.1 城市監(jiān)控卡口網(wǎng)絡(luò)圖G（V，E，C）

城市監(jiān)控卡口網(wǎng)絡(luò)圖G由3部分構(gòu)成：監(jiān)控卡口節(jié)點(diǎn)集合V，監(jiān)控卡口線路集合E及時(shí)間鄰接矩市交叉路段卡口編號(hào)。監(jiān)控卡口線路E由V中節(jié)點(diǎn)為0，不相鄰卡口為∞。

2.1.2 Floyd算法

Floyd算法1962年由弗洛依德提出[6]，其基本思想是在有權(quán)無向圖中，從j任 意j2個(gè)頂點(diǎn) 到 的距離的帶權(quán)鄰接矩陣開始，每次插入一個(gè)頂點(diǎn)vk，然后將 到 間的已知最短路徑與插入頂點(diǎn)vk作為中間頂點(diǎn)時(shí)可能產(chǎn)生的路徑距離比較，取較小值以得到新的距離矩陣。如圖2所示為無向圖是V中元素構(gòu)成的無序二元組的集合，稱為邊集。

圖2 無向圖

權(quán)值也是影響最優(yōu)路徑選擇的重要因素。Floyd算法中相鄰兩頂點(diǎn)(vi,vj)中邊的權(quán)值不僅可以代表距離，在某些條件下還可以轉(zhuǎn)化為成本、流量等因素，應(yīng)按照實(shí)際抓捕工作的限定條件和任務(wù)需求進(jìn)行設(shè)定。本文將時(shí)間作為權(quán)值，研究視頻偵查工作中抓捕時(shí)間最短的最優(yōu)路徑問題。

2.2 道路通行能力估計(jì)方法

考慮到車輛經(jīng)過道路通行時(shí)間受道路通行效率的制約，結(jié)合城市監(jiān)控卡口網(wǎng)絡(luò)提出了一種利用城市監(jiān)控卡口估計(jì)車輛通行時(shí)間的方法，為城市擁堵區(qū)域追捕犯罪嫌疑目標(biāo)提供輔助決策支持。在利用監(jiān)控卡口估計(jì)車輛通行時(shí)間時(shí)，由于駕駛?cè)藛T駕駛技能高低、現(xiàn)場(chǎng)突發(fā)狀況等因素的影響，不可避免地要產(chǎn)生誤差，影響測(cè)量數(shù)據(jù)的精確性，所以要在數(shù)據(jù)融合之前進(jìn)行數(shù)據(jù)檢驗(yàn)。

2.2.1 時(shí)間數(shù)據(jù)檢驗(yàn)

設(shè)監(jiān)控卡口在某單位時(shí)間(h)獨(dú)立地進(jìn)行時(shí)間數(shù)據(jù)的測(cè)量，取n個(gè)時(shí)間數(shù)據(jù)進(jìn)行檢驗(yàn)并將數(shù)據(jù)從小到大的順序排列：T，T2…Tn。稱測(cè)量時(shí)間序列下限為T，上限為Tn。

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)對(duì)象為某城市區(qū)間監(jiān)控卡口網(wǎng)絡(luò)，對(duì)監(jiān)控卡口參數(shù)初始化，其中節(jié)點(diǎn)序列通行最優(yōu)時(shí)間為xy:t（其中x、y表示相鄰節(jié)點(diǎn)，t表示時(shí)間）。具體信息如表3所示。

表3 道路監(jiān)控卡口位置及各卡口相對(duì)關(guān)系參數(shù)

其中相鄰卡口最優(yōu)通行時(shí)間是由加權(quán)融合處理得到的，所構(gòu)成的時(shí)間鄰接矩陣C如下所示：

矩陣C中的元素dij（=2，3，…7）為頂點(diǎn)vi到頂點(diǎn)vj的時(shí)間權(quán)值即道路最優(yōu)通行時(shí)間。其中dij=0為同一頂點(diǎn)，dij=∞為兩頂點(diǎn)間vj不相鄰。結(jié)合以上數(shù)據(jù)得到的某城市區(qū)間監(jiān)控卡口網(wǎng)絡(luò)模型圖G（V，E，C），如圖3所示。

圖3 監(jiān)控卡口網(wǎng)絡(luò)模型圖

同時(shí)，按照深度優(yōu)先搜索原理，得到現(xiàn)場(chǎng)至犯罪嫌疑人隱身地點(diǎn)所有追蹤路徑時(shí)間及頻數(shù)，并根據(jù)用時(shí)長短和頻數(shù)的多少進(jìn)行分組，如表4所示。

表4 路徑用時(shí)頻數(shù)表

取第1組追蹤路徑繪制折線圖，如圖4所示。由于監(jiān)控卡口位置設(shè)定具有連續(xù)性而追蹤路徑卡口選擇具有隨機(jī)性，所以折線圖會(huì)出現(xiàn)水平線段和線段左高右低的現(xiàn)象。例如，最優(yōu)路徑1：A B C F H J，該路徑不經(jīng)過D、E、G監(jiān)控卡口，因此DEF段路徑、FG段路徑為水平線段；路徑11：A D G F H J，由于卡口F順序在卡口G之后，所以路徑有左高右低現(xiàn)象。

圖4 第1組路徑圖

由表4和圖4可以看出，根據(jù)該城市區(qū)間監(jiān)控卡口網(wǎng)絡(luò)規(guī)劃出的追蹤路徑共有83條（不考慮路徑順逆方向），路徑較多、復(fù)雜度相對(duì)較高；其中追蹤時(shí)間小于16min的路徑共12條，公安人員很難準(zhǔn)確的規(guī)劃出耗時(shí)最短的追蹤路徑。為了驗(yàn)證本文方法的有效性，采用Matlab2016b進(jìn)行仿真實(shí)驗(yàn)，針對(duì)如圖3所示的監(jiān)控卡口網(wǎng)絡(luò)圖規(guī)劃出的最優(yōu)路徑如圖5所示。仿真實(shí)驗(yàn)表明，本文提出的方法可以快速、高效的規(guī)劃出現(xiàn)場(chǎng)與犯罪嫌疑人隱身地點(diǎn)的最優(yōu)路徑。最優(yōu)追蹤路徑為：A B C F H J，用時(shí)為12min，相比其他路徑該路徑追蹤用時(shí)最短；在Matlab2016b中運(yùn)行本文算法規(guī)劃最優(yōu)路徑用時(shí)僅為8.417676秒。

圖5 基于監(jiān)控卡口網(wǎng)絡(luò)模型的最優(yōu)路徑

4 結(jié)束語

本文提出了一種利用城市監(jiān)控卡口網(wǎng)絡(luò)尋找最優(yōu)路徑追蹤犯罪嫌疑人的視頻偵查方法，并給出了詳細(xì)的技術(shù)原理與實(shí)現(xiàn)步驟。仿真實(shí)驗(yàn)表明，本文提出的方法有效的將城市監(jiān)控卡口網(wǎng)絡(luò)和視頻偵查技術(shù)結(jié)合起來，能夠快速的規(guī)劃出追蹤犯罪嫌疑人的最優(yōu)路徑，豐富了現(xiàn)有視頻偵查的技術(shù)手段，提高了視頻偵查工作效率。

追蹤路徑 用時(shí)/min A B C F H J 0 0 0 0 12 A D G H J 0 0 0 0 0 13 A B F H J 0 0 0 0 0 14 A B E H J 0 0 0 0 0 14 A B E F H J 0 0 0： 0 14 A D G I J 0 0 0 0 0 15 A D C F H J 0 0 0 0 15 A B C F H I J 0 0 0 15 A B C F G H J 0 0 0 15 A D G H I J 0 0 0 0 16 A D G F H J 0 0 0 0 16 A B C F E H J 0 0 0 16 A B F H I J 0 0 0 0 17 A B F G H J 0 0 0 0 17 A B E F H I J 0 0 0 17 A B E F G H J 0 0 0 17 A B C F G I J 0 0 0 17 A B E H I J 0 0 0 0 17 A D C F G H J 0 0 0 18 A B F E H J 0 0 0 0 18 A B C D G H J 0 0 0 18 A B C F G H I J 0 0 18 A B C F H G I J 0 0 18 A B F G I J 0 0 0 0 19 A D C F E H J 0 0 0 19 A D G F H I J 0 0 0 19 A B E F G I J 0 0 0 19 A B C F E H I J 0 0 19 A B E H G I J 0 0 0 20 A B F G H I J 0 0 0 20 A B F H G I J 0 0 0 20 A D C F G I J 0 0 0 20 A D G F E H J 0 0 0 20 A B E F G H I J 0 0 20 A B E F H G I J 0 0 20 A B C D G I J 0 0 0 20

追蹤路徑 用時(shí)/min A B F E H I J 0 0 0 21 A D C F G H I J 0 0 21 A D C F H G I J 0 0 21 A B C D G H I J 0 0 21 A B C D G F H J 0 0 21 A D C B E F H J 0 0 22 A D C B F H J 0 0 0 22 A D C F E H I J 0 0 22 A D C B E H J 0 0 0 22 A B C F E H G I J 0 22 A B E H F G I J 0 0 23 A D G F E H I J 0 0 23 A B F E H G I J 0 0 24 A B C D G F H I J 0 24 A D C F E H G I J 0 25 A D C B F G H J 0 0 25 A D C B F H I J 0 0 25 A D C B E H I J 0 0 25 A D C B E F G H J 0 25 A D C B E F H I J 0 25 A B C D G F E H J 0 25 A D C B F E H J 0 0 26 A B F C D G H J 0 0 26 A B E F C D G H J 0 26 A D C B F G I J 0 0 27 A D C B E F G I J 0 27 A D C B F G H I J 0 28 A D C B F H G I J 0 28 A D C B E H G I J 0 28 A B F C D G I J 0 0 28 A D C B E F G H I J 28 A D C B E F H G I J 28 A B C D G F E H I J 28 A B E F C D G I J 0 28 A D G F C B E H J 0 29 A D C F B E H J 0 0 29 A D C B F E H I J 0 29 A B F C D G H I J 0 29 A B E F C D G H I J 29 A D G F B E H J 0 0 30 A D C B E H F G I J 31 A B E H F C D G I J 32 A D C B F E H G I J 32 A D C F B E H I J 0 32 A D G F C B E H I J 32 A D G F B E H I J 0 33 A D C F B E H G I J 35

[1]王安,魏建.城市化質(zhì)量與刑事犯罪[J].山東大學(xué)學(xué)報(bào)(哲學(xué)社會(huì)科學(xué)版),2013(3):78-89.

[2]邱洋洋.基于城市路網(wǎng)的最優(yōu)路徑規(guī)劃算法研究[D].北京:燕山大學(xué),2015:5-6.

[3]楊春曉.基于MapX的最優(yōu)路徑搜索理論與實(shí)施技術(shù)研究[D].長春:吉林大學(xué),2004:7-8.

[4]劉浩,鮑遠(yuǎn)律.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J].計(jì)算機(jī)仿真,2008(4):253-257.

[5]Pun-Cheng L S C, Chan A W F. Optimal route computation for circular public transport routes with differential fare structure [J].Travel Behaviour & Society,2016(4):71-77.

[6]曾方俊.Floyd算法求解最短路徑的簡明方法[J].價(jià)值工程,2012(19):167-168.

[7]曹潔,徐微.基于加權(quán)平均方法的交通流檢測(cè)技術(shù)的研究[C]//中國通信學(xué)會(huì)青年工作委員會(huì).2007通信理論與技術(shù)新發(fā)展——第十二屆全國青年通信學(xué)術(shù)會(huì)議論文集(下冊(cè)).北京:電子工業(yè)出版社,2007:1059-1063.

[8]唐亞鵬.基于自適應(yīng)加權(quán)數(shù)據(jù)融合算法的數(shù)據(jù)處理[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015(4):53-56.