為實(shí)現(xiàn)取消全國(guó)高速公路省界收費(fèi)站,車輛通過(guò)省界不停車收費(fèi)的工作目標(biāo),交通部提出以電子快捷收費(fèi)為主、以車牌圖像識(shí)別為輔、多種識(shí)別和支付手段融合應(yīng)用的技術(shù)路徑,對(duì)高速公路上所有車輛（包括ETC車輛和MTC車輛）實(shí)施分段計(jì)費(fèi)。然而,各類型設(shè)備識(shí)別精度不夠、惡意屏蔽通信、偷逃費(fèi)行為增多及網(wǎng)絡(luò)安全風(fēng)險(xiǎn)等種種原因?qū)е虏糠周囕v仍然存在路徑信息缺失的情況�，F(xiàn)行的查詢對(duì)比方法環(huán)節(jié)較多耗時(shí)過(guò)長(zhǎng),難以達(dá)成車輛通過(guò)收費(fèi)站不停車收費(fèi)的目標(biāo)。目前在路徑信息缺失情況下使用的實(shí)時(shí)計(jì)算方案主要為費(fèi)率表查詢法,在省界收費(fèi)站拆除后路網(wǎng)結(jié)構(gòu)的疊加導(dǎo)致費(fèi)率表計(jì)算復(fù)雜度呈幾何級(jí)增長(zhǎng),同時(shí)高速公路仍在不斷建設(shè)聯(lián)網(wǎng)接入系統(tǒng),費(fèi)率表更新頻繁,采用費(fèi)率表法枚舉的全部路徑會(huì)有十分龐大的數(shù)據(jù)量,參數(shù)的生成、存儲(chǔ)、傳輸、運(yùn)算和特殊情況處理都將成為問(wèn)題。本文通過(guò)分析對(duì)比現(xiàn)行各種方案的技術(shù)路線、適用范圍及存在不足后,提出將基于異構(gòu)并行計(jì)算的最短路徑算法應(yīng)用到高速公路多義性路徑收費(fèi)中,使車道收費(fèi)站利用商品化的桌面級(jí)計(jì)算機(jī)即可具備實(shí)時(shí)計(jì)算大規(guī)模路網(wǎng)中任意兩個(gè)節(jié)點(diǎn)間最短路徑的能力。論文主要工作如下:（1）按照?qǐng)D論建立高速公路的路網(wǎng)模型,提出取消省界收費(fèi)... 

【文章來(lái)源】：華南理工大學(xué)廣東省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：88 頁(yè)

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

【部分圖文】：

取消省界收費(fèi)站收費(fèi)方案總體技術(shù)路線

華南理工大學(xué)碩士學(xué)位論文32圖2-5有向圖在GPU上的表達(dá)方式本文是研究基于異構(gòu)計(jì)算的圖算法，在異構(gòu)計(jì)算中存儲(chǔ)圖數(shù)據(jù)需要考慮主機(jī)端和設(shè)備端的計(jì)算任務(wù)區(qū)別和協(xié)同，主要有以下三個(gè)因素：一是設(shè)備段的顯存容量與主機(jī)端的系統(tǒng)內(nèi)存容量比較相對(duì)有限；二是主機(jī)端和設(shè)備端需要來(lái)回傳輸數(shù)據(jù)；三是主機(jī)端和設(shè)備端使用不同的內(nèi)存空間，造成不易操作圖形中的指針數(shù)據(jù)，因此一般采用存取效率最高的圖形數(shù)組形式數(shù)據(jù)結(jié)構(gòu)。2.3.2路網(wǎng)數(shù)據(jù)結(jié)構(gòu)本文主要使用英偉達(dá)公司的開源平臺(tái)CUDA實(shí)現(xiàn)最短路徑的通行費(fèi)率實(shí)時(shí)計(jì)算。CUDA的圖函數(shù)nvGRAPH將圖的拓?fù)?連接)從值中分離出來(lái)。為了簡(jiǎn)化拓?fù)涞闹付�，CUDA的圖函數(shù)支持三種拓?fù)漕愋�，每種拓?fù)漕愋投级x了自己的存儲(chǔ)格式，每種格式都各有優(yōu)劣，分別為NVGRAPH_CSR_32、NVGRAPH_CSC_32、NVGRAPH_COO_32。表2-3CUDA圖函數(shù)的三種拓?fù)漕愋蚇VGRAPH_CSR_32壓縮稀疏行格式(行主格式)。用于SrSPMV算法。對(duì)于這種格式使用nvgraphCSRTopology32I_t拓?fù)浣Y(jié)構(gòu)。NVGRAPH_CSC_32壓縮稀疏列格式(列主格式)。用于SSSP,WidestPath和Pagerank算法。對(duì)于這種格式使用nvgraphCSCTopology32I_t拓?fù)浣Y(jié)構(gòu)。NVGRAPH_COO_32與源或目標(biāo)專業(yè)協(xié)調(diào)列表格式。不用于任何算法，只提供數(shù)據(jù)存儲(chǔ)。此格式使用nvgraphCOOTopology32I_t拓?fù)浣Y(jié)構(gòu)。

第三章基于異構(gòu)并行計(jì)算的最短路徑算法研究37組合屬性是Dijkstra算法及其變種的基礎(chǔ)，用于弧上包含正值和空值權(quán)重的圖。算法維護(hù)數(shù)組dist來(lái)保存從源點(diǎn)s到目標(biāo)頂點(diǎn)v的距離；對(duì)于沒(méi)有找到任何s-v路徑的目組合屬性是Dijkstra算法及其變種的基礎(chǔ)，用于弧上包含正值和空值權(quán)重的圖。算法維護(hù)數(shù)組dist來(lái)保存從源點(diǎn)s到目標(biāo)頂點(diǎn)v的距離；對(duì)于沒(méi)有找到任何s-v路徑的目標(biāo)頂點(diǎn)v，保存+∞。因此，圖的頂點(diǎn)被分成三組。黑色頂點(diǎn)是從源點(diǎn)出發(fā)的已知最短路徑頂點(diǎn)，灰色頂點(diǎn)是黑色頂點(diǎn)的直接相鄰頂點(diǎn)，白色頂點(diǎn)是還沒(méi)有找到任何路徑的頂點(diǎn)。圖3-1最短路徑網(wǎng)絡(luò)圖剛開始，只有源點(diǎn)s是黑色的，其dist[s]=0。s的直接相鄰頂點(diǎn)都是灰色的，dist[v]是弧(s,v)的權(quán)重。其他頂點(diǎn)都是白色的。然后，算法循環(huán)標(biāo)注一個(gè)頂點(diǎn)的顏色為黑色或灰色，并把其相鄰白色頂點(diǎn)標(biāo)注為灰色，其他維持不變。最終，所有從源點(diǎn)可到達(dá)的頂點(diǎn)都會(huì)被標(biāo)注為黑色，而其他頂點(diǎn)會(huì)是白色。在每次遍歷過(guò)程中，我們都要尋找一個(gè)灰色頂點(diǎn)v使得dist[v]最小，所以使用一個(gè)優(yōu)先級(jí)序列來(lái)存儲(chǔ)頂點(diǎn)v的候選者是合理的，dist的值成了優(yōu)先級(jí)的值。這就是Dijkstra算法選擇的實(shí)現(xiàn)方式，其時(shí)間復(fù)雜度為O(V2)。


本文編號(hào)：3604845