我國交通安全基礎(chǔ)脆弱,隱患量大面廣,對道路的例行巡邏是交警提高路面管控能力、更好的維護(hù)交通秩序和保障人民生命財產(chǎn)安全的重要舉措。在交警巡邏工作中,巡邏路徑的規(guī)劃是關(guān)鍵,巡邏路徑的好壞會直接影響巡邏的效果。目前,交警基本依靠自身經(jīng)驗規(guī)劃巡邏路徑,這種方式下規(guī)劃出的巡邏路徑往往會在非目標(biāo)道路上多耗費行駛時間,嚴(yán)重影響了交警的巡邏效率。對于巡邏路徑的不斷優(yōu)化是提高巡邏效率的重要措施。此外,在交警巡邏工作中缺乏規(guī)劃巡邏路徑的輔助工具。在此背景下,本文提出了以目標(biāo)道路為研究對象的交警巡邏路徑優(yōu)化問題,并開發(fā)出了一個巡邏路徑規(guī)劃輔助工具,以此來減輕交警的工作強(qiáng)度,提高巡邏效率和節(jié)約巡邏成本。交警巡邏路徑優(yōu)化問題可以描述為:交警從起始點出發(fā),巡邏完所有的目標(biāo)道路,最后返回起始點,要求規(guī)劃出一條最優(yōu)的巡邏路徑�；卩l(xiāng)村郵遞員問題（Rural Postman Problem,RPP）,本文構(gòu)建了交警巡邏路徑優(yōu)化問題的圖論模型。RPP問題中郵遞員的起始點在目標(biāo)送信道路上,而在交警巡邏路徑優(yōu)化問題中,起始點不一定在目標(biāo)巡邏道路上,本文分起始點在目標(biāo)道路上和起始點不在目標(biāo)道路上兩種情況分析。本文基于CE2啟發(fā)... 

【文章來源】：華東師范大學(xué)上海市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：77 頁

【學(xué)位級別】：碩士

【部分圖文】：

道路交通問題圖（百度圖片）

華東師范大學(xué)碩士學(xué)位論文8起始點在有郵件分送任務(wù)的道路上，而本文交警巡邏路徑優(yōu)化問題中巡邏的起始點不一定在目標(biāo)巡邏道路上，問題求解更復(fù)雜，所以根據(jù)巡邏起始點分兩種情況討論，一種是起始點在目標(biāo)巡邏道路上，另一種是起始點不在目標(biāo)巡邏道路上。根據(jù)RPP問題，目標(biāo)巡邏道路圖不一定是連通圖，若為非連通圖，非連通圖中連通子圖的個數(shù)越多，模型求解難度越大。本文基于Holmberg（2010）提出的求解RPP問題的CE2啟發(fā)式算法，來設(shè)計算法求解交警巡邏路徑優(yōu)化問題模型。考慮到交警的現(xiàn)有工作系統(tǒng)缺乏巡邏路徑規(guī)劃功能的問題，本文在開源QGIS平臺的基礎(chǔ)上，基于QGISPythonAPI庫、PyQt庫和Networkx庫，實現(xiàn)了巡邏路徑規(guī)劃輔助工具，該工具以插件的形式運行在QGIS軟件中。本文的研究框架如圖1-2所示。圖1-2研究框架1.3.2論文創(chuàng)新點本文的創(chuàng)新點表現(xiàn)為以下三方面：（1）本文借助RPP問題研究了交警巡邏路徑優(yōu)化問題，考慮了起始點在目標(biāo)道路外的情況，設(shè)計了有效的問題求解算法。

華東師范大學(xué)碩士學(xué)位論文9（2）模擬了交警經(jīng)驗巡邏過程，將交警經(jīng)驗巡邏結(jié)果與本文提出的算法求解結(jié)果進(jìn)行了對比分析。（3）提出了路徑分解算法，使得路徑導(dǎo)航更加清楚直觀，不產(chǎn)生二義性。1.3.3論文結(jié)構(gòu)安排本文共分為五章，第三章和第四章為本文的重點部分，各章節(jié)安排如下：第一章介紹了論文寫作的研究背景與意義，分析了國內(nèi)外對于CPP問題和RPP問題的求解算法和應(yīng)用的研究現(xiàn)狀，闡述了本文的研究內(nèi)容、研究框架、研究創(chuàng)新點和論文結(jié)構(gòu)。第二章介紹了交警巡邏路徑優(yōu)化問題研究中涉及的一些基本概念、問題和求解方法，主要包括圖的基本概念、歐拉圖、最大權(quán)匹配、最小生成樹、CPP問題和RPP問題，相關(guān)概念之間的關(guān)系如圖1-3所示。圖1-3關(guān)系圖第三章介紹了交警巡邏路徑優(yōu)化問題的圖論模型，討論了巡邏起始點在目標(biāo)道路上和巡邏起始點不在目標(biāo)道路上兩種情況，對兩種情況分別設(shè)計啟發(fā)式算法

【參考文獻(xiàn)】：
期刊論文
[1]復(fù)雜路網(wǎng)下靈活接駁公交路徑優(yōu)化研究[J]. 盧小林,潘述亮,鄒難.  交通運輸系統(tǒng)工程與信息. 2016(06)
[2]基于GIS的公安視頻監(jiān)控指揮管理系統(tǒng)[J]. 吳建華,羅鑫,蘇瑾.  測繪通報. 2011(11)
[3]一種改進(jìn)的量子進(jìn)化算法及其在鄉(xiāng)村郵路問題的應(yīng)用[J]. 包得海,李躍光,華慶一,買桂英.  計算機(jī)應(yīng)用與軟件. 2011(02)
[4]基于Prim算法最小生成樹優(yōu)化的研究[J]. 丁國強(qiáng),呂治國.  甘肅聯(lián)合大學(xué)學(xué)報(自然科學(xué)版). 2009(05)
[5]最大權(quán)匹配算法的改進(jìn)與實現(xiàn)[J]. 徐志才.  電子科學(xué)學(xué)刊. 1988(04)
[6]奇偶點圖上作業(yè)法[J]. 管梅谷.  數(shù)學(xué)學(xué)報. 1960(03)

碩士論文
[1]基于無人機(jī)的網(wǎng)絡(luò)巡線問題研究[D]. 侯雨涵.華中科技大學(xué) 2018
[2]基于自主GIS的警務(wù)車輛管理系統(tǒng)的設(shè)計與實現(xiàn)[D]. 趙一冰.天津大學(xué) 2016
[3]公安盜搶情報信息管理系統(tǒng)的設(shè)計與實現(xiàn)[D]. 高湛.福州大學(xué) 2014
[4]時變網(wǎng)絡(luò)鄉(xiāng)村郵路問題割平面及蟻群算法研究[D]. 曲宏磊.大連理工大學(xué) 2011



本文編號：3147276