引言

　　在大多數(shù)國家，出租車都是一種十分普遍和便捷的交通工具。多數(shù)發(fā)達國家建設了完善的出租車調(diào)度系統(tǒng)，實現(xiàn)了出租車高效運營，如美國，電話預約和站點候客的出租車運營方式占98％，“路拋式”僅占2％；在倫敦、巴黎、新加坡等發(fā)達國家城市，除非電話預約，或者在指定的?？康攸c，否則很少能看到乘客在街頭打車，這大大提高了公共交通資源的運行效率。但是在我國的大多數(shù)城市，仍然以乘客街頭叫車為主，雖然部分城市已經(jīng)實現(xiàn)了出租車安裝GPS設備和實時記錄出租車位置信息，但是并沒有很好地利用這些GPS位置信息為出租車調(diào)度服務，導致很多出租車GPS系統(tǒng)成為擺設。為了進一步提高我國的出租車調(diào)度系統(tǒng)的運行效率和提高GPS系統(tǒng)的實用性，很有必要研究一種結(jié)合GPS/GIS技術(shù)的快速高效出租車調(diào)度系統(tǒng)。

　　本文設計和實現(xiàn)了一種新型的出租車調(diào)度系統(tǒng)，該系統(tǒ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)設計

　　本系統(tǒng)包括三個部分：出租車調(diào)度終端、通信平臺和調(diào)度中心。調(diào)度終端是基于三星S3C2440硬件平臺和WINCE操作系統(tǒng)的智能嵌入式設備，實現(xiàn)了與調(diào)度平臺的通信和現(xiàn)場智能控制；調(diào)度終端實現(xiàn)GPS數(shù)據(jù)的采集、上報和調(diào)度信息的顯示；通信平臺提供準確、高效的信息傳輸功能；調(diào)度中心實現(xiàn)出租車快速調(diào)度以及基于GIS的車輛實時監(jiān)控功能。

　　1.1 出租車調(diào)度終端設計

　　出租車調(diào)度終端在硬件上包括兩部分：基于三星S3C2440的系統(tǒng)板和基于VK3224的設備擴展板。系統(tǒng)板和擴展板之間通過SPI接口進行通信。系統(tǒng)板包括：

　　S3C2440 ARM9核心處理器、存儲器FLASH、SDRAM、電源管理器件、RS232、I/O口空載標識燈接口及上報乘客信息按鈕等。接口板包括：VK3224、GPS模塊、GPRS模塊和RS232等。此調(diào)度終端在設計上增加了一個出租車司機上報乘客位置的按鈕，其作用是行駛在馬路上的每個出租車司機都可以上報在路上發(fā)現(xiàn)的乘客位置信息，系統(tǒng)收到信息就會調(diào)度最近的空載出租車前來服務。

　　終端的硬件結(jié)構(gòu)如圖1所示。

　　出租車調(diào)度終端在軟件設計上采用透明通道提供可靠的數(shù)據(jù)傳輸層。透明通道是通過GPRS上面封裝TCP/IP協(xié)議和服務器進行通信，當主站控制終端上某個串口設備的時候，將主站發(fā)送的數(shù)據(jù)包中加載串口數(shù)據(jù)，數(shù)據(jù)包傳輸?shù)搅私K端后，終端將這些串口數(shù)據(jù)直接發(fā)送給對應的串口設備，當串口設備返回數(shù)據(jù)后，系統(tǒng)將這些數(shù)據(jù)加載在TCP/IP數(shù)據(jù)包上，通過GPRS發(fā)送到主站，在主站應用層看來和直接操作串口沒有區(qū)別。調(diào)度終端和服務器之間GPS位置信息上傳，上報乘客信息，調(diào)度指令下發(fā)等都是通過透明通道完成的。調(diào)度終端軟件設計圖如圖2所示。

　　1.2 通信平臺

　　為了實現(xiàn)平臺和出租車的通訊以及收集乘客叫車信息，通信平臺包括M2M通信模塊、短信平臺和呼叫中心三個模塊。

　?。?）M2M通信模塊實現(xiàn)出租車和調(diào)度中心的通信功能，具體包括：出租車位置上傳、路邊乘客位置上傳、調(diào)度中心指令下發(fā)等。M2M通信模塊使用基于GPRS網(wǎng)絡上的TCP/IP技術(shù)，服務器端采用Windows平臺的完成端口（IOCP）技術(shù)，從而保證單個服務器能同時接入大量出租車調(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)度中心之間的通信，主要功能是乘客位置和打車請求收集。短信平臺負責接收短信調(diào)度的短信，再由調(diào)度中心分析短信內(nèi)容，完成短信調(diào)度。呼叫中心負責電話鏈路，話務員和系統(tǒng)根據(jù)來電內(nèi)容使用調(diào)度中心模塊實現(xiàn)電話調(diào)度。

　　1.3 調(diào)度中心設計

　a.網(wǎng)格空車鏈表初始化。將當前系統(tǒng)中的所有空載出租車根據(jù)所處位置，通過二分法計算出租車所屬網(wǎ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)格，加載到對應網(wǎng)格乘客鏈表中，遵循“先請求先服務”

　　原則，本系統(tǒng)中網(wǎng)格乘客鏈表采用鏈表隊列結(jié)構(gòu)，鏈表中的結(jié)點數(shù)據(jù)結(jié)構(gòu)如表2所示。

表2 乘客數(shù)據(jù)結(jié)構(gòu)

　?。?）乘客請求調(diào)度。通過第（3）步將出租車和乘客按照網(wǎng)格分組，單個網(wǎng)格中如果網(wǎng)格乘客鏈表不為空，從鏈表選擇一個乘客，同時判斷該網(wǎng)格中空車鏈表是否為空，如果不為空，從該鏈表中選擇一個空車去滿足該乘客請求；如果該網(wǎng)格中空車鏈表為空，選擇相鄰網(wǎng)格中空車鏈表中的空車來滿足乘客請求，直到搜索到空車為止。搜索到空載出租車后把乘客GPS位置和乘客具體文字描述位置發(fā)送給出租車終端，發(fā)送成功后，將乘客從網(wǎng)格乘客鏈表中刪除，同時將對應的空車從網(wǎng)格空車鏈表中刪除。至此，調(diào)度過程完成。

　　3 模擬與性能測試

　　我們通過一臺服務器（DELLR710機架式服務器，XEON E5504×2JSDM/4G內(nèi)存條）作為調(diào)度服務器，模擬城市網(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)度服務器CPU使用率49%，證明此系統(tǒng)是高效可行的。

　　4 結(jié)語

　　本文基于GPS/GIS設計和實現(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)運行效率。