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