王小會(huì)， 薛延剛， 李曉青

(蘭州工業(yè)學(xué)院 電氣工程學(xué)院，甘肅 蘭州 730000)

隨著車輛的廣泛普及和交通網(wǎng)絡(luò)的不斷發(fā)展，智能交通誘導(dǎo)系統(tǒng)的作用將顯得更為突出。智能交通誘導(dǎo)系統(tǒng)是將先進(jìn)的計(jì)算機(jī)處理技術(shù)、信息技術(shù)、數(shù)據(jù)通信技術(shù)及電子自動(dòng)控制技術(shù)等有效地綜合運(yùn)用于整個(gè)系統(tǒng)當(dāng)中，建立起的一種在大范圍內(nèi)、全方位發(fā)揮作用的實(shí)時(shí)、準(zhǔn)確、高效的最優(yōu)出行路線系統(tǒng)[1-6]。

交通誘導(dǎo)系統(tǒng)可根據(jù)駕駛員的意愿為其提供最佳行駛路線來達(dá)到誘導(dǎo)出行行為，減少車輛在路上的行駛時(shí)間[7-8]。對用戶來說，除了最優(yōu)路線外，次優(yōu)、再次優(yōu)等路線[9-10]也同樣重要，這樣可以使用戶擁有更大的選擇空間。同時(shí)，為了進(jìn)一步提供更人性化的服務(wù)，誘導(dǎo)系統(tǒng)還應(yīng)設(shè)置多個(gè)必經(jīng)點(diǎn)以滿足用戶在出行途中的需要，比如要途徑超市、加油站等，故必經(jīng)點(diǎn)的考慮也必將是未來智能交通誘導(dǎo)系統(tǒng)的發(fā)展趨勢[11-16]。因此，本文在基本Dijkstra算法上提出過K個(gè)必經(jīng)點(diǎn)的N條最短路徑算法，有效擴(kuò)充了最短路徑的數(shù)量，滿足用戶選擇需求。

1 交通誘導(dǎo)系統(tǒng)的設(shè)計(jì)

1.1 系統(tǒng)設(shè)計(jì)

首先通過建立路網(wǎng)節(jié)點(diǎn)屬性數(shù)據(jù)庫保存相關(guān)節(jié)點(diǎn)信息，并將路網(wǎng)信息數(shù)據(jù)導(dǎo)入到數(shù)據(jù)庫，完善路網(wǎng)結(jié)構(gòu)信息；其次，通過Dijkstra算法查找出符合要求的最短路徑；最后在界面上顯示相關(guān)的路徑信息。具體流程如圖1所示。

圖1 系統(tǒng)設(shè)計(jì)流程

圖2 一個(gè)路網(wǎng)

圖3 子網(wǎng)集合

1.2 數(shù)據(jù)處理

為提高數(shù)據(jù)運(yùn)算效率，采用分塊式處理的方式，主要包括對路網(wǎng)的結(jié)構(gòu)、路網(wǎng)節(jié)點(diǎn)屬性信息的處理和信息輸入接口的設(shè)置。對路網(wǎng)的拓?fù)浣Y(jié)構(gòu)采用序列化的方法存入硬盤中，路網(wǎng)節(jié)點(diǎn)屬性信息存放在Access數(shù)據(jù)庫中，并通過信息輸入接口實(shí)現(xiàn)對拓?fù)浣Y(jié)構(gòu)進(jìn)行增加、刪除、修改、保存。圖3為以一個(gè)路網(wǎng)(圖2)的子網(wǎng)集合，其中路網(wǎng)的主站點(diǎn)代表道路的交叉口，輔助站點(diǎn)是相鄰交叉口之間的彎道點(diǎn)。

通過微軟基礎(chǔ)類庫(Microsoft Foundation Classes，MFC)中已有的CTypedPtrArray數(shù)組類模板實(shí)現(xiàn)路網(wǎng)的存儲(chǔ)、動(dòng)態(tài)創(chuàng)建新元素、統(tǒng)計(jì)元素個(gè)數(shù)等功能。同時(shí)，通過數(shù)組類的封裝，把整個(gè)網(wǎng)絡(luò)劃分為各個(gè)子網(wǎng)的集合，每個(gè)子網(wǎng)均是數(shù)組類的一個(gè)元素，即包含一個(gè)節(jié)點(diǎn)與其所關(guān)聯(lián)的所有連接信息，這樣的改變無疑使網(wǎng)絡(luò)結(jié)構(gòu)變得更為清晰，而且又充分利用了MFC本身所擁有的標(biāo)準(zhǔn)類。

數(shù)組類CTypedPtrArraym_CtypedptrArrayRouteWeb保存了整個(gè)網(wǎng)絡(luò)的信息，其中每個(gè)子網(wǎng)結(jié)構(gòu)通過一個(gè)類CRouteWeb來實(shí)現(xiàn)存儲(chǔ)，具體存儲(chǔ)內(nèi)容如圖4所示。

圖4 子網(wǎng)的數(shù)據(jù)存儲(chǔ)方式

這里的距離默認(rèn)的是路程，行駛的速度用于衡量兩主站點(diǎn)之間路段的路況擁擠度，根據(jù)現(xiàn)實(shí)生活中各電子地圖的經(jīng)驗(yàn)，分別以0～10 km/h、10～30 km/h、30 km/h以上代表路況的擁堵、緩慢、暢通。

本系統(tǒng)是選用開放數(shù)據(jù)庫連接(Open Database Connectivity，ODBC)關(guān)系型數(shù)據(jù)庫設(shè)計(jì)的，在系統(tǒng)中設(shè)計(jì)相關(guān)的數(shù)據(jù)庫包含如下3步：

(1)建立應(yīng)用程序：通過MFC AppWizard建立MFC應(yīng)用程序。

(2)建立節(jié)點(diǎn)屬性數(shù)據(jù)庫：Access文件作為系統(tǒng)的節(jié)點(diǎn)屬性數(shù)據(jù)庫，在文件中建立兩張數(shù)據(jù)表,分別是主站點(diǎn)表、輔助站點(diǎn)表，用于存儲(chǔ)主站點(diǎn)及輔助站點(diǎn)的屬性信息。主站數(shù)據(jù)表主要包括節(jié)點(diǎn)ID、節(jié)點(diǎn)坐標(biāo)、節(jié)點(diǎn)所在街道名稱，其中ID為整型，作為主站數(shù)據(jù)表的唯一標(biāo)識符。輔助站點(diǎn)表和主站數(shù)據(jù)表結(jié)構(gòu)一致，這樣將提高對數(shù)據(jù)庫的可操作性。

(3)建立ODBC數(shù)據(jù)源：進(jìn)入Windows系統(tǒng)中的管理工具選項(xiàng)，在ODBC中添加一個(gè)基于“Microsoft Access Driver(*.mdb，*.accdb)”的驅(qū)動(dòng)程序，并在下一步操作中命名數(shù)據(jù)源名稱為“站點(diǎn)信息”，同時(shí)把第(2)步中建立的站點(diǎn)信息文件作為對象，通過以上步驟，即可完成對數(shù)據(jù)庫的建立與連接。

2 過必經(jīng)點(diǎn)的最短路徑設(shè)計(jì)

本文通過Dijkstra算法求解過K個(gè)必經(jīng)點(diǎn)的N條最短路徑算法。

2.1 基本原理

對于過K個(gè)必經(jīng)點(diǎn)的N條最短路徑算法，必須先求得過第一條K個(gè)必經(jīng)點(diǎn)的最短路徑，然后再通過斷開第一最短路徑所形成的子圖集對應(yīng)的最短路徑集合求第二最短路徑，如此循環(huán)以致求得第N條最短路徑。

設(shè)G=(V，E)是一個(gè)帶權(quán)有向或無向圖，該圖是由節(jié)點(diǎn)和相連的弧線組成，兩個(gè)節(jié)點(diǎn)之間的不同連接方式組成了兩點(diǎn)間所有的路徑，每條路徑都與其所在的子圖相關(guān)，子圖可以是原圖斷開某些節(jié)點(diǎn)之間的連接或去掉若干個(gè)節(jié)點(diǎn)以及與這些節(jié)點(diǎn)相關(guān)的連接組成。在一個(gè)子圖中求過K個(gè)必經(jīng)點(diǎn)的最短路徑，可通過分段求解每一種排列的路徑后，去路徑最小值來確定最終的最短路徑。

對于一個(gè)沒有孤立節(jié)點(diǎn)的子圖，每兩個(gè)節(jié)點(diǎn)間存在最短路徑。假設(shè)圖中無孤立節(jié)點(diǎn)，那么從起始節(jié)點(diǎn)到目的節(jié)點(diǎn)之間存在若干條路徑。對于每一條路徑，該路徑有多少段(不同節(jié)點(diǎn)之間的連接)就可以通過斷開每一段形成多少個(gè)子圖，這些子圖中從起始節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑集合相并再并上原圖中被斷開的這條路徑所形成的集合，就等于原圖中起始節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的路徑集合[3]。根據(jù)以上原理可知，只要在子圖中，起始節(jié)點(diǎn)和目的節(jié)點(diǎn)之間存在路徑即是存在最短路徑。故保持子圖所有節(jié)點(diǎn)和原圖一致，只是斷開路徑的不同，在原圖找到兩點(diǎn)之間的最短路徑后，斷開這條第一最短路徑后形成的眾子圖都分別存在起始節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的最短路徑，倘若兩節(jié)點(diǎn)之間還存在連接。對于原圖來說第二最短路徑便是這些形成子圖的最短路徑中最短的，如果所有子圖中都不存在這兩點(diǎn)間的路徑時(shí)，表明只有第一最短路徑這一條。

因此，求過K個(gè)必經(jīng)節(jié)點(diǎn)的N條最短路徑就是對每次找到的過K個(gè)必經(jīng)點(diǎn)最短路徑的子圖進(jìn)行再次分割，并且和已有子圖存在的過K個(gè)必經(jīng)點(diǎn)的最短路徑進(jìn)行一一比較，找出最短的，這樣不斷地重復(fù)執(zhí)行，并在執(zhí)行過程中去除重復(fù)的路徑，直到路徑條數(shù)達(dá)到滿足或者已無路徑為止。

2.2 算法步驟

過K個(gè)必經(jīng)點(diǎn)的N條最短路徑步驟如下：

(1)求出第1條過K個(gè)必經(jīng)點(diǎn)的最短路徑。

(2)創(chuàng)建一個(gè)數(shù)組類arrWebShortestPaths，對第一條過K個(gè)必經(jīng)點(diǎn)的最短路徑進(jìn)行添加；在該過K個(gè)必經(jīng)點(diǎn)的最短路徑對應(yīng)的子圖中(第1條對應(yīng)的子圖為原圖)，保持所有節(jié)點(diǎn)不變，按照該條路徑進(jìn)行分段斷開，從而形成若干個(gè)對應(yīng)的子圖，計(jì)算每個(gè)子圖對應(yīng)的過K個(gè)必經(jīng)點(diǎn)的最短路徑；創(chuàng)建arrFormSubnetInfo數(shù)組類，用于把每個(gè)子圖對應(yīng)的最短路徑的長度和從原圖形成該子圖所斷開的某兩個(gè)節(jié)點(diǎn)之間路段進(jìn)行保存。

(3)刪除arrFormSubnetInfo此次中形成新子圖的母圖記錄，比較arrFormSubnetInfo每個(gè)元素對應(yīng)最短路徑的長度，求最小長度，找出該元素，并從記錄中可知其最短路徑對應(yīng)的子圖是通過原圖斷開哪幾段路段后形成的。創(chuàng)建一個(gè)數(shù)組比較類arrWebShortestPaths，用于新找出這條過K個(gè)必經(jīng)點(diǎn)最短路徑，和已存儲(chǔ)的所有最短路徑比較，若存在相同的，則不進(jìn)行添加，反之，則添加。

(4)判斷數(shù)組類arrWebShortestPaths中已有的最短路徑是否有存在重復(fù)路段，把沒有重復(fù)路段的用整型變量作一標(biāo)記，返回執(zhí)行第2步，直到該標(biāo)記值和所需的最短路徑條數(shù)N相等或者已無最短路徑為止。

3 數(shù)值實(shí)驗(yàn)

圖5為模擬道路情況的數(shù)據(jù)集，對其進(jìn)行最短路徑求解。

圖5 26節(jié)點(diǎn)數(shù)據(jù)集

3.1 無必經(jīng)點(diǎn)的前N(N=20)條最短路徑

以節(jié)點(diǎn)2為起點(diǎn)，22為終點(diǎn)的無必經(jīng)點(diǎn)的前N(N=20)條最短路徑，求解結(jié)果如表1所示。

從實(shí)驗(yàn)結(jié)果可以看出，在這20條路徑中，結(jié)果均不存在重復(fù)路徑，更不會(huì)在同一路徑中重復(fù)出現(xiàn)同一路段，這表明算法的思想和設(shè)計(jì)的程序是完全正確的。

3.2 過K個(gè)必經(jīng)點(diǎn)的N條最短路徑

以節(jié)點(diǎn)2為起點(diǎn)，22為終點(diǎn)，隨機(jī)選擇K(K=1，2，3，4)個(gè)必經(jīng)點(diǎn)的前N(N=1，2，3，4)條最短路徑，求解結(jié)果如表2所示。

通過表2可以確認(rèn)，本文算法實(shí)現(xiàn)的過K個(gè)必經(jīng)點(diǎn)的前N條最短路徑，在K、N分別為不同值時(shí)，對應(yīng)的N條路徑均是表1中已得到驗(yàn)證的前20條最短路徑中最短的前N條；同時(shí)，對比過必經(jīng)點(diǎn)17和過必經(jīng)點(diǎn)13、17的第一最短路徑可知：如果增加的必經(jīng)點(diǎn)不是過原必經(jīng)點(diǎn)路徑上的點(diǎn)的話，必然會(huì)隨著必經(jīng)點(diǎn)的增加，而使路徑總長度變長。由此可見，該算法完全可以保證理論上的過K(K小于5)個(gè)必經(jīng)點(diǎn)的前N(N小于5)條最短路徑的實(shí)現(xiàn)。

本文使用的過必經(jīng)點(diǎn)的最短路徑算法，實(shí)質(zhì)上是通過反復(fù)迭代基本Dijkstra算法改造而來的。因此，在時(shí)耗上受基本Dijkstra算法時(shí)間復(fù)雜度的影響，即受賦權(quán)圖規(guī)模的影響，賦權(quán)圖的結(jié)點(diǎn)越少，邊數(shù)越少，時(shí)間耗費(fèi)越少，反之，則越多；而且隨著路徑條數(shù)和必經(jīng)點(diǎn)個(gè)數(shù)的增加，時(shí)耗會(huì)成倍地增長。本文采用的算法在包含必經(jīng)點(diǎn)的情況下幾乎可以完全保證理論上的前N條最短路徑的精確性，但是，在求解時(shí)也會(huì)由于起始點(diǎn)、必經(jīng)點(diǎn)及終止點(diǎn)之間的連接關(guān)系不同而產(chǎn)生時(shí)耗上的差異。在有必經(jīng)點(diǎn)的情況下，由于必經(jīng)點(diǎn)在起始點(diǎn)和終止點(diǎn)的相對位置上的差異，可能會(huì)引起算法路徑搜索上較大的區(qū)別，從而在時(shí)耗上也會(huì)相差很大，而且這種差別會(huì)隨著必經(jīng)點(diǎn)或路徑條數(shù)的增加而變得更明顯。

表1 無必經(jīng)點(diǎn)的前20條最短路徑

表2 過K個(gè)必經(jīng)點(diǎn)的N條最短路徑

4 結(jié)論

本文基于Dijkstra算法，設(shè)計(jì)了過K個(gè)必經(jīng)點(diǎn)的前N條最短路徑算法，通過數(shù)值實(shí)驗(yàn)分析，驗(yàn)證了該條件下理論上過必經(jīng)點(diǎn)的前N條最短路徑的正確性，為過K個(gè)必經(jīng)點(diǎn)的前N條最短路徑問題的算法切實(shí)可行提供了基礎(chǔ)，有效擴(kuò)充了可行路徑的數(shù)量，解決了實(shí)際中交通誘導(dǎo)系統(tǒng)存在的問題，可以滿足用戶選擇需求。但是智能交通誘導(dǎo)系統(tǒng)是一個(gè)非常龐大的系統(tǒng)，本文所涉及到的研究僅是其中的一小部分，建立一個(gè)完善的智能交通誘導(dǎo)系統(tǒng)是一個(gè)相對復(fù)雜的過程，需要投入較多的資源進(jìn)行開發(fā)。在城市交通線路日益增加的今天，智能交通誘導(dǎo)系統(tǒng)的發(fā)展擁有非常廣闊的前景。