本文設(shè)計和實現(xiàn)了一種新型的出租車調(diào)度系統(tǒng)，該系統(tǒng)通過改進當(dāng)前調(diào)度系統(tǒng)的叫車方式,，并提出基于網(wǎng)格的出租車調(diào)度算法，該算法結(jié)合通信平臺上傳的出租車GPS位置信息和GIS系統(tǒng)網(wǎng)格信息把出租車分組,，實現(xiàn)小組內(nèi)及小組間出租車高效協(xié)作和調(diào)度,，很大程度上提高了出租車的調(diào)度效率。
1 系統(tǒng)設(shè)計
本系統(tǒng)包括三個部分：出租車調(diào)度終端,、通信平臺和調(diào)度中心,。調(diào)度終端是基于三星S3C2440硬件平臺和WINCE操作系統(tǒng)的智能嵌入式設(shè)備，實現(xiàn)了與調(diào)度平臺的通信和現(xiàn)場智能控制,；調(diào)度終端實現(xiàn)GPS數(shù)據(jù)的采集,、上報和調(diào)度信息的顯示；通信平臺提供準(zhǔn)確,、高效的信息傳輸功能,；調(diào)度中心實現(xiàn)出租車快速調(diào)度以及基于GIS的車輛實時監(jiān)控功能。
1.1 出租車調(diào)度終端設(shè)計
出租車調(diào)度終端在硬件上包括兩部分：基于三星S3C2440的系統(tǒng)板和基于VK3224的設(shè)備擴展板,。系統(tǒng)板和擴展板之間通過SPI接口進行通信,。系統(tǒng)板包括：
S3C2440 ARM9核心處理器、存儲器FLASH,、SDRAM,、電源管理器件、RS232,、I/O口空載標(biāo)識燈接口及上報乘客信息按鈕等,。接口板包括：VK3224,、GPS模塊、GPRS模塊和RS232等,。此調(diào)度終端在設(shè)計上增加了一個出租車司機上報乘客位置的按鈕,，其作用是行駛在馬路上的每個出租車司機都可以上報在路上發(fā)現(xiàn)的乘客位置信息，系統(tǒng)收到信息就會調(diào)度最近的空載出租車前來服務(wù),。
終端的硬件結(jié)構(gòu)如圖1所示,。
出租車調(diào)度終端在軟件設(shè)計上采用透明通道提供可靠的數(shù)據(jù)傳輸層。透明通道是通過GPRS上面封裝TCP/IP協(xié)議和服務(wù)器進行通信,，當(dāng)主站控制終端上某個串口設(shè)備的時候,，將主站發(fā)送的數(shù)據(jù)包中加載串口數(shù)據(jù)，數(shù)據(jù)包傳輸?shù)搅私K端后,，終端將這些串口數(shù)據(jù)直接發(fā)送給對應(yīng)的串口設(shè)備,，當(dāng)串口設(shè)備返回數(shù)據(jù)后，系統(tǒng)將這些數(shù)據(jù)加載在TCP/IP數(shù)據(jù)包上,，通過GPRS發(fā)送到主站,，在主站應(yīng)用層看來和直接操作串口沒有區(qū)別。調(diào)度終端和服務(wù)器之間GPS位置信息上傳,，上報乘客信息,，調(diào)度指令下發(fā)等都是通過透明通道完成的。調(diào)度終端軟件設(shè)計圖如圖2所示,。
1.2 通信平臺
為了實現(xiàn)平臺和出租車的通訊以及收集乘客叫車信息,，通信平臺包括M2M通信模塊、短信平臺和呼叫中心三個模塊,。
?。?）M2M通信模塊實現(xiàn)出租車和調(diào)度中心的通信功能，具體包括：出租車位置上傳,、路邊乘客位置上傳,、調(diào)度中心指令下發(fā)等。M2M通信模塊使用基于GPRS網(wǎng)絡(luò)上的TCP/IP技術(shù),，服務(wù)器端采用Windows平臺的完成端口（IOCP）技術(shù),，從而保證單個服務(wù)器能同時接入大量出租車調(diào)度終端（大于5000臺）。完成端口的最大優(yōu)點在于其管理海量連接時的處理效率,，通過操作系統(tǒng)內(nèi)核的相關(guān)機制完成I/O處理的高效率,，由于出租車調(diào)度過程中連接量巨大，且每個連接上收發(fā)的數(shù)據(jù)包比較小,，通常只有幾k甚至不到1k的字節(jié),，因此很適合使用完成端口技術(shù)。
?。?）短信平臺和呼叫中心模塊實現(xiàn)乘客和調(diào)度中心之間的通信,，主要功能是乘客位置和打車請求收集,。短信平臺負責(zé)接收短信調(diào)度的短信，再由調(diào)度中心分析短信內(nèi)容,，完成短信調(diào)度,。呼叫中心負責(zé)電話鏈路，話務(wù)員和系統(tǒng)根據(jù)來電內(nèi)容使用調(diào)度中心模塊實現(xiàn)電話調(diào)度,。
1.3 調(diào)度中心設(shè)計
調(diào)度中心分為前臺應(yīng)用程序和后臺服務(wù)程序,。
前臺應(yīng)用軟件采用B/S架構(gòu)，主要包括：系統(tǒng)管理,、注冊管理和調(diào)度管理三個部分,，
（1）系統(tǒng)管理包括：部門管理,、用戶管理,、角色管理和權(quán)限管理等；
?。?）注冊管理包括：固定電話注冊,、手機注冊。固定電話注冊完成固定電話和單個固定叫車位置的關(guān)聯(lián)綁定,，如酒店,、公司等，通過GIS系統(tǒng)記錄該位置的經(jīng)緯度信息,；手機短信注冊完成手機號碼和幾個固定叫車位置的綁定,，每個綁定有一個標(biāo)簽短信代替，同時將每個叫車位置在GIS系統(tǒng)中的經(jīng)緯度信息記錄下來,。
（3）調(diào)度管理包括：司機互助調(diào)度,、話務(wù)員調(diào)度,、注冊電話調(diào)度、短信調(diào)度等模塊,。
后臺服務(wù)程序采用C/S架構(gòu),，將通信平臺所收集到的出租車GPS位置信息和乘客GPS位置信息聯(lián)系起來，通過下節(jié)所講的基于網(wǎng)格的調(diào)度算法完成綜合調(diào)度,，調(diào)度平臺和通信平臺是一個密切聯(lián)系的模塊,，具體關(guān)系如圖3所示。
圖3 調(diào)度系統(tǒng)整體架構(gòu)（參見右欄）
2 系統(tǒng)關(guān)鍵模塊設(shè)計
2.1 叫車方式設(shè)計
國內(nèi)外現(xiàn)有出租車調(diào)度系統(tǒng)的叫車方式主要分為兩種類型：一是乘客打電話報告自己的位置,，調(diào)度員或話務(wù)員在GIS地圖上標(biāo)注乘客位置,；二是乘客觸發(fā)TAXI站點應(yīng)招按鈕叫車。
本系統(tǒng)在原有方式的基礎(chǔ)上增加和改進了叫車方式,。
1）在調(diào)度終端上增加一個報告乘客位置按鈕,，當(dāng)出租車滿載期間在路上行駛時如若遇到路邊等車乘客就觸發(fā)此按鈕,，實現(xiàn)出租車司機實時上報乘客位置，此方式體現(xiàn)了一種“我為人人,，人人為我”的思想,，這種互助協(xié)作的搜索，擴大了搜索乘客的空間范圍,。
2）在GIS地圖中事先注冊乘車地點,，將該地點的經(jīng)緯度信息與固定電話號碼綁定，乘客用綁定的固定電話撥打調(diào)度中心,，調(diào)度中心即可確定撥入用戶的叫車位置,，實現(xiàn)電話調(diào)度。這樣,，注冊的固定電話（包括：家庭固話和公用電話亭電話等）都等價于出租車應(yīng)召站點,，這種叫車方式，調(diào)度中心無須人工參與,，系統(tǒng)自動完成調(diào)度,。
3）短信叫車，乘客事先注冊幾個自己經(jīng)常打車的地點,，比如說家,、公司等，然后將該地點的經(jīng)緯度信息,、手機號碼和位置標(biāo)簽關(guān)聯(lián),，乘客需要叫車時發(fā)送事先注冊好的位置標(biāo)簽短信，調(diào)度中心即可確定叫車乘客位置,，從而實現(xiàn)短信調(diào)度,。這三種叫車方式，調(diào)度中心端無須調(diào)度員人工干預(yù),，自動調(diào)度,，方便乘客，節(jié)省資源,。
2.2 基于網(wǎng)格的調(diào)度算法
現(xiàn)有的出租車調(diào)度中心大多設(shè)計為人工服務(wù)模式,，首先調(diào)度中心不斷采集在系統(tǒng)中注冊的出租車的狀態(tài)，然后將為空載狀態(tài)的出租車按照先進先出原則送入一個隊列,；最后對于每個在線預(yù)約的乘客請求,，調(diào)度員會按照自己以往的經(jīng)驗，人工確定最方便的一輛出租車,，如果同時有多個出租車滿足請求,，就按照先進先服務(wù)的方式前去服務(wù)，這種方式人工成本較高，且服務(wù)質(zhì)量難以提高,。
本系統(tǒng)放棄人工服務(wù)方式,，采用系統(tǒng)自動調(diào)度方式。
本調(diào)度服務(wù)程序采用基于網(wǎng)格的出租車調(diào)度算法,，該算法具體過程如下：
?。?）劃分城市網(wǎng)格。在GIS地圖上根據(jù)城市大小,，用適當(dāng)?shù)木匦慰虬殉鞘懈采w,，獲取矩形框?qū)蔷€的經(jīng)緯度信息：左上角經(jīng)緯度值為（a,b）、右下角經(jīng)緯度值為（c,d）,；結(jié)合城市出租車數(shù)量確定網(wǎng)格數(shù)（M×N）,。
城市出租車總數(shù)為Tsum，出租車空載率為Pec,，空載出租車數(shù)為Tec=Pec×Tsum,。選取網(wǎng)格數(shù)約等于空載出租車數(shù)Tec≈M×N\，為了計算方便,，一般M,、N選擇為2的冪次數(shù)（如：16、32,、64,、128、……）,，同時為了保證網(wǎng)格長寬盡量接近,，所以選擇M/N比值盡量靠近
值。
?。?）劃分城市經(jīng)緯度數(shù)組,。確定M、N值以后,，把所選城市經(jīng)度范圍（a,c）均分為M份,，存入經(jīng)度數(shù)組citylongitude[M]中，相鄰值間隔為
,；同時將城市緯度范圍（b,d）均分為N份，存入緯度數(shù)組citylatitude[N]中,，相鄰值間隔為
,。劃分經(jīng)緯度數(shù)組是為了下面使用二分法計算出租車和請求乘客所在網(wǎng)格。
?。?）網(wǎng)格信息維護,。通過劃分城市經(jīng)緯度數(shù)組確定網(wǎng)格數(shù)組CityGrid[M][N]，網(wǎng)格數(shù)據(jù)結(jié)構(gòu)包括網(wǎng)格經(jīng)緯度等基本信息，同時每個網(wǎng)格動態(tài)維護兩個鏈表：網(wǎng)格空車鏈表和網(wǎng)格乘客鏈表,。城市網(wǎng)格結(jié)構(gòu)如圖4所示,。
a.網(wǎng)格空車鏈表初始化。將當(dāng)前系統(tǒng)中的所有空載出租車根據(jù)所處位置,，通過二分法計算出租車所屬網(wǎng)格,，加載到對應(yīng)網(wǎng)格空車鏈表中，由于網(wǎng)格空車鏈表需要根據(jù)出租車終端上報的狀態(tài)信息實時調(diào)整,，鏈表的增刪操作較為頻繁,，因此本系統(tǒng)中網(wǎng)格空車鏈表采用雙鏈表結(jié)構(gòu)。鏈表中的結(jié)點數(shù)據(jù)結(jié)構(gòu)如表1所示,。
表1 出租車數(shù)據(jù)結(jié)構(gòu)
b.網(wǎng)格空車鏈表動態(tài)維護,。根據(jù)出租車終端實時上報的狀態(tài)信息，判斷是否為空載狀態(tài),，如果為空載,，判斷鏈表中該出租車是否為空載狀態(tài)，如果為空載判斷本次是否需要將出租車調(diào)整網(wǎng)格,，如果鏈表中沒有該出租車,，根據(jù)上報的GPS位置信息計算所屬網(wǎng)格，將該出租車插入該網(wǎng)格空車鏈表中,，空載狀態(tài)計算完畢,。如果上報狀態(tài)為滿載狀態(tài)，判斷此前出租車是否為空載狀態(tài),，如果為空載,，將其從空車鏈表中刪除，滿載狀態(tài)計算完畢,。具體處理流程圖如圖5所示,。
未調(diào)度的乘客根據(jù)所處位置，通過二分法計算乘客所屬網(wǎng)格,，加載到對應(yīng)網(wǎng)格乘客鏈表中,，遵循“先請求先服務(wù)”
原則，本系統(tǒng)中網(wǎng)格乘客鏈表采用鏈表隊列結(jié)構(gòu),，鏈表中的結(jié)點數(shù)據(jù)結(jié)構(gòu)如表2所示,。
表2 乘客數(shù)據(jù)結(jié)構(gòu)
（4）乘客請求調(diào)度,。通過第（3）步將出租車和乘客按照網(wǎng)格分組,，單個網(wǎng)格中如果網(wǎng)格乘客鏈表不為空，從鏈表選擇一個乘客,，同時判斷該網(wǎng)格中空車鏈表是否為空,，如果不為空，從該鏈表中選擇一個空車去滿足該乘客請求；如果該網(wǎng)格中空車鏈表為空,，選擇相鄰網(wǎng)格中空車鏈表中的空車來滿足乘客請求,，直到搜索到空車為止。搜索到空載出租車后把乘客GPS位置和乘客具體文字描述位置發(fā)送給出租車終端,，發(fā)送成功后,，將乘客從網(wǎng)格乘客鏈表中刪除，同時將對應(yīng)的空車從網(wǎng)格空車鏈表中刪除,。至此,，調(diào)度過程完成。
3 模擬與性能測試
我們通過一臺服務(wù)器（DELLR710機架式服務(wù)器,，XEON E5504×2JSDM/4G內(nèi)存條）作為調(diào)度服務(wù)器,，模擬城市網(wǎng)格劃分為64×64=4096的系統(tǒng)調(diào)度，一臺PC機模擬10000臺出租車數(shù)據(jù)上傳GPS位置和狀態(tài)信息,，上傳間隔為10s,，測試內(nèi)容包括：出租車司機互助調(diào)度、電話調(diào)度,、短信調(diào)度,。通過模擬測試10000臺出租車運行，調(diào)度服務(wù)器CPU使用率49%,，證明此系統(tǒng)是高效可行的,。
4 結(jié)語
本文基于GPS/GIS設(shè)計和實現(xiàn)了一種新型的出租車調(diào)度系統(tǒng)，該系統(tǒng)改進了現(xiàn)有出租車調(diào)度終端和叫車方式,，并提出一種基于網(wǎng)格的出租車調(diào)度算法,，實現(xiàn)出租車自動調(diào)度，最大限度地減少人工參與,，通過模擬測試證明該算法高效實用,。通過本系統(tǒng)可以有效降低乘客等待時間（CWT）和出租車空駛率（ECP），提高出租車系統(tǒng)運行效率,。