姚仲敏，龍昭鵬，李 強

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

1 引 言

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

2 系統(tǒng)結構

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

圖1 系統(tǒng)結構Fig.1 System structure

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

出租車的調度需要知道乘客所在位置，空載出租車位置以及城市道路分布.本系統(tǒng)是根據(jù)乘客所在位置，向周圍擴展尋找空載出租車.所以，源節(jié)點為乘客所屬的城市道路節(jié)點，城市道路節(jié)點代表城市交叉路口，目的節(jié)點需要調度之后才能確定.各城市道路節(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é)點的位置關系和距離.

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

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

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

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

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

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

本系統(tǒng)中，源節(jié)點即乘客所在城市道路節(jié)點.用適當?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é)點.

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

3.3 堵車信息

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

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

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

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

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

4 調度算法

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

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

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

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

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

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

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

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

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表依次調度出租車，有出租車司機同意則結束調度，否則調度失敗.

5 實驗結果

以齊齊哈爾市區(qū)龍沙區(qū)內部分主干道為基礎進行仿真，由于都是主干道，權重w都為1，且該選定區(qū)域內共有21個節(jié)點，在Visual C++6.0中采用鄰接表實現(xiàn)Dijkstra算法，采用21×21的二維數(shù)組表示選定區(qū)域內各城市道路節(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)調度結果如表2所示.表2中，S為乘客所在節(jié)點，D為出租車所在節(jié)點;J為堵車節(jié)點;t表示堵車時間;s為調度需要行駛的路程;P為調度出租車行駛的路徑.由表2知，從節(jié)點6調度出租車至節(jié)點17，當β分別為10、30、50時，系統(tǒng)分別在節(jié)點3發(fā)生堵車的第6、4、3 min后改變調度路徑，所改變的調度路徑中不再包含節(jié)點3，從而規(guī)避堵車區(qū)域，在第13 min(正常通車)恢復正常調度.而從節(jié)點6調度出租車至節(jié)點11，當β為10時，調度結果始終保持不變，沒有改變調度路徑.經(jīng)查，節(jié)點11地處較為偏僻地帶，交通道路少，改變路徑消耗很大.但是，當 β分別為30、50時，系統(tǒng)分別在第5、4 min后可以改變調度路徑，規(guī)避堵車區(qū)域，在第13 min(正常通車)恢復為正常調度.可見系統(tǒng)調度直接受β的影響，不同的β值對堵車的靈敏度不同，設置合適的β值能提高系統(tǒng)規(guī)避堵車區(qū)域的成功率，如表2中β=20的調度結果比較理想.而未考慮城市道路堵車情況的出租車調度系統(tǒng)(即，目前的調度系統(tǒng))，其調度結果與沒有發(fā)生堵車的調度結果一樣，并保持不變，不能規(guī)避堵車區(qū)域.

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

表2 調度結果Table 2 Scheduling results

6 研究結論

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

［1］俞斌，朱海清，黎美麗.基于GPS/GIS/GSM的出租車調度系統(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］周先春，石蘭芳，周杰.一種出租車調度中心系統(tǒng)的設計［J］. 電子技術應用，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的出租車呼叫與調度系統(tǒng)［J］.計算機工程與設計，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出租車調度系統(tǒng)的設計與實現(xiàn)［J］.電子技術應用，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］. 北京理工大學學報，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］董俊，黃傳河.改進Dijkstra算法在GIS導航應用中最短路徑搜索研究［J］.計算機科學，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］倪怡，邱成龍，楊皓然.面向行車誘導的最優(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］.微電子學與計算機.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.］