姚仲敏，龍昭鵬，李 強

(齊齊哈爾大學(xué)通信與電子工程學(xué)院，黑龍江齊齊哈爾161006)

1 引 言

目前出租車調(diào)度系統(tǒng)主要是在調(diào)度中心接收到乘客的調(diào)度請求后，選擇最合適的出租車為乘客提供乘車服務(wù).一定程度上緩解了乘客“打車難”、“人找車，車找人”的現(xiàn)象，也一定程度上降低了出租車的空載率［1-4］.但是沒有考慮實時的城市道路交通狀態(tài)，使得原本最合理的調(diào)度(路程最短)，因為調(diào)度的出租車可能需要經(jīng)過堵車區(qū)域，不能及時為乘客提供服務(wù)，甚至進(jìn)一步加重了該區(qū)域的道路擁堵.隨著城市車輛的不斷增加，堵車成為現(xiàn)今交通重大難題［5］.考慮城市道路堵車狀況的出租車調(diào)度系統(tǒng)，具有重要的意義和價值.

2 系統(tǒng)結(jié)構(gòu)

系統(tǒng)主要包括三部分:GPS手機、GPS出租車和調(diào)度中心.GPS手機用于定位乘客當(dāng)前位置經(jīng)緯度信息，向調(diào)度中心發(fā)送調(diào)度出租車請求.GPS出租車向調(diào)度中心發(fā)送堵車信息和節(jié)點更新信息.調(diào)度中心用于接收乘客的調(diào)度請求信息和出租車發(fā)送的信息，并調(diào)度最佳出租車為乘客提供乘車服務(wù).系統(tǒng)結(jié)構(gòu)如圖1所示.

圖1 系統(tǒng)結(jié)構(gòu)Fig.1 System structure

3 系統(tǒng)節(jié)點

出租車的調(diào)度需要知道乘客所在位置，空載出租車位置以及城市道路分布.本系統(tǒng)是根據(jù)乘客所在位置，向周圍擴展尋找空載出租車.所以，源節(jié)點為乘客所屬的城市道路節(jié)點，城市道路節(jié)點代表城市交叉路口，目的節(jié)點需要調(diào)度之后才能確定.各城市道路節(jié)點的分布、連通性和直接距離即可反映城市道路分布情況.

3.1 城市道路節(jié)點

本系統(tǒng)中，城市道路節(jié)點為固定節(jié)點，節(jié)點屬性如表1所示.

表1 節(jié)點屬性Table 1 Node attributes

NodeGPS:城市道路節(jié)點經(jīng)緯度信息，表示節(jié)點所在交叉路口的具體位置.

neighborNode:鄰居節(jié)點，記錄了本節(jié)點和各鄰居節(jié)點的位置關(guān)系和距離.

nodeList:一個排序的鏈表，記錄了到最大調(diào)度范圍內(nèi)各節(jié)點的最短距離，及經(jīng)過節(jié)點的數(shù)量.

hasTaxi(n):有出租車信息，表示附近正開往該節(jié)點的空載出租車數(shù)量.

tJamCounter(c):堵車計數(shù)器，用來描述該節(jié)點的堵車狀態(tài).

Weight(w):權(quán)重，值在0-1之間.表示該節(jié)點在城市交通中的重要性.越繁華的街道節(jié)點，其權(quán)重值越大.

Loss(l):出租車經(jīng)過該城市道路節(jié)點時的損耗.

3.2 源節(jié)點和目的節(jié)點

本系統(tǒng)中，源節(jié)點即乘客所在城市道路節(jié)點.用適當(dāng)?shù)木匦未砟吵鞘?，矩形左上角?jīng)緯度為［x1，y1］，右下角經(jīng)緯度為［x2，y2］.本系統(tǒng)的網(wǎng)格大小為［ptl×(x2-x1)，ptl×(y2-y1)］，其中ptl表示該城市的交叉路口密度.系統(tǒng)依據(jù)乘客所在位置，快速定位乘客所在網(wǎng)格，并確定一個距離乘客最近的城市道路節(jié)點作為源節(jié)點.

當(dāng)出租車經(jīng)過一個交叉路口(城市道路節(jié)點)時，根據(jù)GPS數(shù)據(jù)和城市道路節(jié)點屬性，分析出正在開往和離開的城市道路節(jié)點，發(fā)送這兩個城市道路節(jié)點的hasTaxi屬性更新信息至調(diào)度中心.

3.3 堵車信息

正常通車時，車輛即使因路口紅燈不能及時通過交叉路口，在連續(xù)兩個紅燈期間也會有一段行駛距離.所以，當(dāng)出租車引擎開啟，在一段時間tg(tg大于紅燈時間)內(nèi)出租車車速始終低于城市最低行車速度且行駛距離小于固定距離(如40 m)時，才向調(diào)度中心發(fā)送道路堵車信息，以防止出租車位于交叉口停車(停車時間不長，一般小于tg)和正常通車造成的誤報.調(diào)度中心接收到堵車信息，堵車計數(shù)器值c增加，c主要是靠出租車數(shù)量和堵車時間的積累，即使偶爾出現(xiàn)一兩輛出租車誤報的情況對系統(tǒng)的影響很小，c的計算方法如下:

式中 cm，j表示在j時間段內(nèi)m節(jié)點的堵車計數(shù)器值;nm，i表示i時間段內(nèi)被堵于m節(jié)點的出租車數(shù)量;t表示堵車時間;tg表示更新堵車信息的時間間隔.當(dāng)堵車計數(shù)器值c不為0時，出租車經(jīng)過節(jié)點所在區(qū)域會有額外損耗，額外損耗計算方法如下:

式中 lm，j表示在j時間段內(nèi)經(jīng)過m節(jié)點的額外損耗(m)，為非負(fù)數(shù)，lm，j＜ 0時，計為0;β 表示單位額外損耗(一個堵車計數(shù)器值所帶來的額外損耗)，k表示該區(qū)域堵車情況開始出現(xiàn)緩和的時刻，此時堵車數(shù)量開始減少.出租車經(jīng)過城市道路節(jié)點m時的損耗的計算方法如下:

式中 sm，j表示出租車在j時間段內(nèi)經(jīng)過節(jié)點m的損耗(m)，rm，m+1為城市道路節(jié)點m到其下一節(jié)點(m+1)的距離.而出租車與乘客之間的路程為出租車經(jīng)過的各節(jié)點的損耗之和，即

式中 sj表示j時段內(nèi)的乘客與出租車之間的路程(m)，s表示乘客所屬節(jié)點;d表示出租車所屬節(jié)點;wm，m+1表示城市道路節(jié)點m到其下一節(jié)點(m+1)所在道路的權(quán)重.

4 調(diào)度算法

本系統(tǒng)采用Dijkstra算法結(jié)合堵車信息進(jìn)程出租車調(diào)度.Dijkstra算法是求最短路徑的經(jīng)典算法，采用Dijkstra算法調(diào)度出租車，確定乘客到調(diào)度范圍內(nèi)各空載出租車的最短距離，從中選擇距離最短的出租車作為調(diào)度對象.

Dijkstra算法的基本思路是:每次新擴展一個距離最短的點，更新與其相鄰的點的距離.當(dāng)所有邊權(quán)都為正時，由于不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠(yuǎn)不會再被改變，因而保證了算法的正確性.假設(shè)每個點都有一對標(biāo)號(dn，pn)，其中dn為m到n的最短路徑;pn為m到n的最短路徑中n的前一節(jié)點.求解m到終點n的最短路徑的步驟如下［6］:

Step 1 初始化.設(shè)起點m的標(biāo)號dn=0，pn為空.其他所有節(jié)點的標(biāo)號設(shè)為dn= ，pn為空.標(biāo)記起始點m，記k=m，其他所有節(jié)點為未標(biāo)記節(jié)點.

Step 2 檢驗從所有已標(biāo)記的點k到與其直接連接的未標(biāo)記的點n的距離，設(shè)dn=min{dn，dn+lkn}，式中l(wèi)kn為點k到與其直接連接點n的距離.

Step 3 從所有dn中選取最小的點i，di=min{dn，所有未標(biāo)記的點n}.則點i被選為最短路徑中的一點，并設(shè)定為已標(biāo)記.

Step 4 考察所有點，如果都已經(jīng)標(biāo)記，則退出算法，否則記k=i，返回Step 2.

Dijkstra算法中每一個節(jié)點需要計算到其它所有節(jié)點的距離，搜索具有盲目性，算法時間復(fù)雜度較高為O(n2)，其與城市道路節(jié)點數(shù)n成指數(shù)增長，所以減少搜索節(jié)點數(shù)量是降低算法時間復(fù)雜度的重要方法，目前研究的熱點是通過限制搜索區(qū)域，如方向夾角［7］、直線加速法［8］、矩形區(qū)域算法［9］等.這些算法在導(dǎo)航(即知道目的節(jié)點情況下的搜索)中性能突出.而本系統(tǒng)中目的節(jié)點(空載出租車)在發(fā)起調(diào)度時不確定，上述算法不適用.為減少搜索節(jié)點數(shù)，本文提出在最大調(diào)度范圍內(nèi)進(jìn)行出租車調(diào)度，從出租車司機的經(jīng)濟利益考慮，司機不會接受距離太遠(yuǎn)的調(diào)度請求，而且，這種過遠(yuǎn)距離的調(diào)度會浪費能源，調(diào)度失去意義.

本系統(tǒng)發(fā)起調(diào)度時，以乘客所屬節(jié)點S為源節(jié)點，將S周圍處于調(diào)度范圍(r)內(nèi)的所有節(jié)點加入集合H，同時將有空載出租車的節(jié)點加入集合D.只需在集合H中采用Dijkstra算法計算到集合D中所有節(jié)點的距離.其時間復(fù)雜度為O［card(H)×card(D)］，其 中 card(D)＜ card(H)＜ ＜ n，card(D)、card(H)分別表示集合D和集合H中元素個數(shù).此方案很大程度上降低了原Dijkstra算法的時間復(fù)雜度.系統(tǒng)具體調(diào)度步驟如下:

Step 1 H=?;

Step 2 確定乘客所屬城市道路節(jié)點(S)，H:={S}，將S作為指定元素;

Step 3 依次查看指定元素的各鄰居節(jié)點，根據(jù)式(4)計算S到鄰居節(jié)點的路程(s)，若s＜r，H:={指定元素鄰居節(jié)點}，若指定元素鄰居節(jié)點的hasTaxi屬性值(v)大于零，D:={指定元素鄰居節(jié)點};

Step 4 若非集合H中的最后一個元素，則將下一個元素作為指定元素，返回Step 3;

Step 5 根據(jù)集合H中的元素，采用Dijkstra算法計算S到集合D中各元素的最短距離;

Step 6 將得到的最短距離排序后放入到節(jié)點的nodeList屬性表中;

Step 7 按nodeList表依次調(diào)度出租車，有出租車司機同意則結(jié)束調(diào)度，否則調(diào)度失敗.

5 實驗結(jié)果

以齊齊哈爾市區(qū)龍沙區(qū)內(nèi)部分主干道為基礎(chǔ)進(jìn)行仿真，由于都是主干道，權(quán)重w都為1，且該選定區(qū)域內(nèi)共有21個節(jié)點，在Visual C++6.0中采用鄰接表實現(xiàn)Dijkstra算法，采用21×21的二維數(shù)組表示選定區(qū)域內(nèi)各城市道路節(jié)點之間的距離.鄰接矩陣如圖2所示.

圖2 鄰接矩陣圖Fig.2 Adjacency matrix

實驗仿真時，堵車情況和堵車節(jié)點隨機出現(xiàn)，在一次具體的仿真中，節(jié)點3出現(xiàn)堵車，具體的堵車情況和經(jīng)過節(jié)點3的額外損耗如圖3所示.圖3中給出了堵車數(shù)量n和β分別為10，30，50時額外損耗(l)的變化曲線，其中，所堵出租車數(shù)量n的變化情況為

節(jié)點3處堵車時系統(tǒng)調(diào)度結(jié)果如表2所示.表2中，S為乘客所在節(jié)點，D為出租車所在節(jié)點;J為堵車節(jié)點;t表示堵車時間;s為調(diào)度需要行駛的路程;P為調(diào)度出租車行駛的路徑.由表2知，從節(jié)點6調(diào)度出租車至節(jié)點17，當(dāng)β分別為10、30、50時，系統(tǒng)分別在節(jié)點3發(fā)生堵車的第6、4、3 min后改變調(diào)度路徑，所改變的調(diào)度路徑中不再包含節(jié)點3，從而規(guī)避堵車區(qū)域，在第13 min(正常通車)恢復(fù)正常調(diào)度.而從節(jié)點6調(diào)度出租車至節(jié)點11，當(dāng)β為10時，調(diào)度結(jié)果始終保持不變，沒有改變調(diào)度路徑.經(jīng)查，節(jié)點11地處較為偏僻地帶，交通道路少，改變路徑消耗很大.但是，當(dāng) β分別為30、50時，系統(tǒng)分別在第5、4 min后可以改變調(diào)度路徑，規(guī)避堵車區(qū)域，在第13 min(正常通車)恢復(fù)為正常調(diào)度.可見系統(tǒng)調(diào)度直接受β的影響，不同的β值對堵車的靈敏度不同，設(shè)置合適的β值能提高系統(tǒng)規(guī)避堵車區(qū)域的成功率，如表2中β=20的調(diào)度結(jié)果比較理想.而未考慮城市道路堵車情況的出租車調(diào)度系統(tǒng)(即，目前的調(diào)度系統(tǒng))，其調(diào)度結(jié)果與沒有發(fā)生堵車的調(diào)度結(jié)果一樣，并保持不變，不能規(guī)避堵車區(qū)域.

圖3 β為10，30，50時l的變化曲線圖Fig.3 Curves of l when β is 10，30，50

表2 調(diào)度結(jié)果Table 2 Scheduling results

6 研究結(jié)論

在城市堵車越來越嚴(yán)重的情況下，目前的出租車調(diào)度系統(tǒng)沒有考慮城市堵車狀況，調(diào)度的出租車可能需要經(jīng)過堵車區(qū)域，不能及時解決乘客需求.本文提出了一種考慮城市堵車信息的出租車調(diào)度系統(tǒng)，當(dāng)發(fā)生堵車時，通過增加車輛經(jīng)過該區(qū)域損耗的方法，實現(xiàn)出租車避開堵車區(qū)域.不同的β值，對應(yīng)系統(tǒng)對堵車的不同靈敏度，通過實驗仿真，設(shè)置合理的β值，系統(tǒng)可根據(jù)堵車情況的嚴(yán)重程度，合理規(guī)劃調(diào)度出租車的行駛路徑，避開城市堵車較嚴(yán)重區(qū)域.

［1］俞斌，朱海清，黎美麗.基于GPS/GIS/GSM的出租車調(diào)度系統(tǒng)［J］. 城市公共交通，2010，4:41-44.［YU B，ZHU H Q，LI M I.Taxi dispatch system based on GPS/GIS/GSM［J］.Urban Public Transport，2010，4:41-44.］

［2］周先春，石蘭芳，周杰.一種出租車調(diào)度中心系統(tǒng)的設(shè)計［J］. 電子技術(shù)應(yīng)用，2012，38:136-138.［ZHOU X C，SHI L F，ZHOU J.A design of taxi dispatch center system［J］.Application of Electronic Technique，2012，38:136-138.］

［3］周曉敏，趙紅玉，俞建新.基于GPS的出租車呼叫與調(diào)度系統(tǒng)［J］.計算機工程與設(shè)計，2009，30(21):4995-4997.［ZHOU X M，ZHAO H Y，YU J X.Taxi calling and scheduling system based on GPS［J］.Computer Engineering and Design，2009，30(21):4995-4997.］

［4］楊宏業(yè)，張躍.一種新的GPS出租車調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)［J］.電子技術(shù)應(yīng)用，2002(6):44-46.［YANG H Y，ZHANG Y.Design and implementation of a new GPS taxi dispatch system［J］.Application of Electronic Technique，2002(6):44-46.］

［5］魏卓新.城市道路何時不再擁堵［J］.江淮，2012(7):47-48.［WEI Z X.When the city road is not jam traffic ［J］.Jiang Huai，2012(7):47-48.］

［6］馮欣欣.Dijkstra算法在嵌入式GIS中的優(yōu)化實現(xiàn)［J］. 北京理工大學(xué)學(xué)報，2009，29(10):873-876.［FENG X X. Efficient implementation ofdijkstra algorithm in embedded GIS［J］.Transactions of Beijing Institute of Technology，2009，29(10):873-876.］

［7］董俊，黃傳河.改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究［J］.計算機科學(xué)，2012，39(10):245-247.［DONG J，HUANG C H.Research on shortest path search of improved dijkstra algorithm in GIS navigation application［J］.Computer Science，2012，39(10):245-247.］

［8］倪怡，邱成龍，楊皓然.面向行車誘導(dǎo)的最優(yōu)路徑算法研究［J］.自動化與儀器儀表，2012(3):145-149.［NI Y，QIU C L，YANG H R.The study of the optimal path algorithm for driving induction［J］.Automation ＆Instrumentation，2012(3):145-149.］

［9］周影，曹菡，李軍霞.一種限制區(qū)域的最短路徑查找算法［J］.微電子學(xué)與計算機.2007，24(8):110-112.［ZHOU Y，CAO H，LI J X.A Shortest route-planning algorithm within a restricted area［J］.Microelectronics＆ Computer，2007，24(8):110-112.］