基于GPS的新型出租車(chē)調度系統

引言

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

本文設計和實(shí)現了一種新型的出租車(chē)調度系統，該系統通過(guò)改進(jìn)當前調度系統的叫車(chē)方式，并提出基于網(wǎng)格的出租車(chē)調度算法，該算法結合通信平臺上傳的出租車(chē)GPS位置信息和GIS系統網(wǎng)格信息把出租車(chē)分組，實(shí)現小組內及小組間出租車(chē)高效協(xié)作和調度，很大程度上提高了出租車(chē)的調度效率。

1 系統設計

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

1.1 出租車(chē)調度終端設計

出租車(chē)調度終端在硬件上包括兩部分：基于三星S3C2440的系統板和基于VK3224的設備擴展板。系統板和擴展板之間通過(guò)SPI接口進(jìn)行通信。系統板包括：

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

終端的硬件結構如圖1所示。

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


1.2 通信平臺

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

（1）M2M通信模塊實(shí)現出租車(chē)和調度中心的通信功能，具體包括：出租車(chē)位置上傳、路邊乘客位置上傳、調度中心指令下發(fā)等。M2M通信模塊使用基于GPRS網(wǎng)絡(luò )上的TCP/IP技術(shù)，服務(wù)器端采用Windows平臺的完成端口（IOCP）技術(shù)，從而保證單個(gè)服務(wù)器能同時(shí)接入大量出租車(chē)調度終端（大于5000臺）。完成端口的最大優(yōu)點(diǎn)在于其管理海量連接時(shí)的處理效率，通過(guò)操作系統內核的相關(guān)機制完成I/O處理的高效率，由于出租車(chē)調度過(guò)程中連接量巨大，且每個(gè)連接上收發(fā)的數據包比較小，通常只有幾k甚至不到1k的字節，因此很適合使用完成端口技術(shù)。

（2）短信平臺和呼叫中心模塊實(shí)現乘客和調度中心之間的通信，主要功能是乘客位置和打車(chē)請求收集。短信平臺負責接收短信調度的短信，再由調度中心分析短信內容，完成短信調度。呼叫中心負責電話(huà)鏈路，話(huà)務(wù)員和系統根據來(lái)電內容使用調度中心模塊實(shí)現電話(huà)調度。

1.3 調度中心設計

調度中心分為前臺應用程序和后臺服務(wù)程序。

前臺應用軟件采用B/S架構，主要包括：系統管理、注冊管理和調度管理三個(gè)部分，

（1）系統管理包括：部門(mén)管理、用戶(hù)管理、角色管理和權限管理等；

（2）注冊管理包括：固定電話(huà)注冊、手機注冊。固定電話(huà)注冊完成固定電話(huà)和單個(gè)固定叫車(chē)位置的關(guān)聯(lián)綁定，如酒店、公司等，通過(guò)GIS系統記錄該位置的經(jīng)緯度信息；手機短信注冊完成手機號碼和幾個(gè)固定叫車(chē)位置的綁定，每個(gè)綁定有一個(gè)標簽短信代替，同時(shí)將每個(gè)叫車(chē)位置在GIS系統中的經(jīng)緯度信息記錄下來(lái)。

（3）調度管理包括：司機互助調度、話(huà)務(wù)員調度、注冊電話(huà)調度、短信調度等模塊。

后臺服務(wù)程序采用C/S架構，將通信平臺所收集到的出租車(chē)GPS位置信息和乘客GPS位置信息聯(lián)系起來(lái)，通過(guò)下節所講的基于網(wǎng)格的調度算法完成綜合調度，調度平臺和通信平臺是一個(gè)密切聯(lián)系的模塊，具體關(guān)系如圖3所示。

圖3 調度系統整體架構（參見(jiàn)右欄）

2 系統關(guān)鍵模塊設計

2.1 叫車(chē)方式設計

國內外現有出租車(chē)調度系統的叫車(chē)方式主要分為兩種類(lèi)型：一是乘客打電話(huà)報告自己的位置，調度員或話(huà)務(wù)員在GIS地圖上標注乘客位置；二是乘客觸發(fā)TAXI站點(diǎn)應招按鈕叫車(chē)。

本系統在原有方式的基礎上增加和改進(jìn)了叫車(chē)方式。

1）在調度終端上增加一個(gè)報告乘客位置按鈕，當出租車(chē)滿(mǎn)載期間在路上行駛時(shí)如若遇到路邊等車(chē)乘客就觸發(fā)此按鈕，實(shí)現出租車(chē)司機實(shí)時(shí)上報乘客位置，此方式體現了一種“我為人人，人人為我”的思想，這種互助協(xié)作的搜索，擴大了搜索乘客的空間范圍。

2）在GIS地圖中事先注冊乘車(chē)地點(diǎn)，將該地點(diǎn)的經(jīng)緯度信息與固定電話(huà)號碼綁定，乘客用綁定的固定電話(huà)撥打調度中心，調度中心即可確定撥入用戶(hù)的叫車(chē)位置，實(shí)現電話(huà)調度。這樣，注冊的固定電話(huà)（包括：家庭固話(huà)和公用電話(huà)亭電話(huà)等）都等價(jià)于出租車(chē)應召站點(diǎn)，這種叫車(chē)方式，調度中心無(wú)須人工參與，系統自動(dòng)完成調度。

3）短信叫車(chē)，乘客事先注冊幾個(gè)自己經(jīng)常打車(chē)的地點(diǎn)，比如說(shuō)家、公司等，然后將該地點(diǎn)的經(jīng)緯度信息、手機號碼和位置標簽關(guān)聯(lián)，乘客需要叫車(chē)時(shí)發(fā)送事先注冊好的位置標簽短信，調度中心即可確定叫車(chē)乘客位置，從而實(shí)現短信調度。這三種叫車(chē)方式，調度中心端無(wú)須調度員人工干預，自動(dòng)調度，方便乘客，節省資源。

2.2 基于網(wǎng)格的調度算法

現有的出租車(chē)調度中心大多設計為人工服務(wù)模式，首先調度中心不斷采集在系統中注冊的出租車(chē)的狀態(tài)，然后將為空載狀態(tài)的出租車(chē)按照先進(jìn)先出原則送入一個(gè)隊列；最后對于每個(gè)在線(xiàn)預約的乘客請求，調度員會(huì )按照自己以往的經(jīng)驗，人工確定最方便的一輛出租車(chē)，如果同時(shí)有多個(gè)出租車(chē)滿(mǎn)足請求，就按照先進(jìn)先服務(wù)的方式前去服務(wù)，這種方式人工成本較高，且服務(wù)質(zhì)量難以提高。

本系統放棄人工服務(wù)方式，采用系統自動(dòng)調度方式。

本調度服務(wù)程序采用基于網(wǎng)格的出租車(chē)調度算法，該算法具體過(guò)程如下：

（1）劃分城市網(wǎng)格。在GIS地圖上根據城市大小，用適當的矩形框把城市覆蓋，獲取矩形框對角線(xiàn)的經(jīng)緯度信息：左上角經(jīng)緯度值為（a,b）、右下角經(jīng)緯度值為（c,d）；結合城市出租車(chē)數量確定網(wǎng)格數（M×N）。

城市出租車(chē)總數為T(mén)sum，出租車(chē)空載率為Pec，空載出租車(chē)數為T(mén)ec=Pec×Tsum。選取網(wǎng)格數約等于空載出租車(chē)數Tec≈M×N，為了計算方便，一般M、N選擇為2的冪次數（如：16、32、64、128、……），同時(shí)為了保證網(wǎng)格長(cháng)寬盡量接近，所以選擇M/N比值盡量靠近值。

（2）劃分城市經(jīng)緯度數組。確定M、N值以后，把所選城市經(jīng)度范圍（a,c）均分為M份，存入經(jīng)度數組citylongitude[M]中，相鄰值間隔為；同時(shí)將城市緯度范圍（b,d）均分為N份，存入緯度數組citylatitude[N]中，相鄰值間隔為。劃分經(jīng)緯度數組是為了下面使用二分法計算出租車(chē)和請求乘客所在網(wǎng)格。

（3）網(wǎng)格信息維護。通過(guò)劃分城市經(jīng)緯度數組確定網(wǎng)格數組CityGrid[M][N]，網(wǎng)格數據結構包括網(wǎng)格經(jīng)緯度等基本信息，同時(shí)每個(gè)網(wǎng)格動(dòng)態(tài)維護兩個(gè)鏈表：網(wǎng)格空車(chē)鏈表和網(wǎng)格乘客鏈表。城市網(wǎng)格結構如圖4所示。

a.網(wǎng)格空車(chē)鏈表初始化。將當前系統中的所有空載出租車(chē)根據所處位置，通過(guò)二分法計算出租車(chē)所屬網(wǎng)格，加載到對應網(wǎng)格空車(chē)鏈表中，由于網(wǎng)格空車(chē)鏈表需要根據出租車(chē)終端上報的狀態(tài)信息實(shí)時(shí)調整，鏈表的增刪操作較為頻繁，因此本系統中網(wǎng)格空車(chē)鏈表采用雙鏈表結構。鏈表中的結點(diǎn)數據結構如表1所示。

表1 出租車(chē)數據結構

b.網(wǎng)格空車(chē)鏈表動(dòng)態(tài)維護。根據出租車(chē)終端實(shí)時(shí)上報的狀態(tài)信息，判斷是否為空載狀態(tài)，如果為空載，判斷鏈表中該出租車(chē)是否為空載狀態(tài)，如果為空載判斷本次是否需要將出租車(chē)調整網(wǎng)格，如果鏈表中沒(méi)有該出租車(chē)，根據上報的GPS位置信息計算所屬網(wǎng)格，將該出租車(chē)插入該網(wǎng)格空車(chē)鏈表中，空載狀態(tài)計算完畢。如果上報狀態(tài)為滿(mǎn)載狀態(tài)，判斷此前出租車(chē)是否為空載狀態(tài)，如果為空載，將其從空車(chē)鏈表中刪除，滿(mǎn)載狀態(tài)計算完畢。具體處理流程圖如圖5所示。

未調度的乘客根據所處位置，通過(guò)二分法計算乘客所屬網(wǎng)格，加載到對應網(wǎng)格乘客鏈表中，遵循“先請求先服務(wù)”

原則，本系統中網(wǎng)格乘客鏈表采用鏈表隊列結構，鏈表中的結點(diǎn)數據結構如表2所示。

表2 乘客數據結構

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

3 模擬與性能測試

我們通過(guò)一臺服務(wù)器（DELLR710機架式服務(wù)器，XEON E5504×2JSDM/4G內存條）作為調度服務(wù)器，模擬城市網(wǎng)格劃分為64×64=4096的系統調度，一臺PC機模擬10000臺出租車(chē)數據上傳GPS位置和狀態(tài)信息，上傳間隔為10s，測試內容包括：出租車(chē)司機互助調度、電話(huà)調度、短信調度。通過(guò)模擬測試10000臺出租車(chē)運行，調度服務(wù)器CPU使用率49%，證明此系統是高效可行的。

4 結語(yǔ)

本文基于GPS/GIS設計和實(shí)現了一種新型的出租車(chē)調度系統，該系統改進(jìn)了現有出租車(chē)調度終端和叫車(chē)方式，并提出一種基于網(wǎng)格的出租車(chē)調度算法，實(shí)現出租車(chē)自動(dòng)調度，最大限度地減少人工參與，通過(guò)模擬測試證明該算法高效實(shí)用。通過(guò)本系統可以有效降低乘客等待時(shí)間（CWT）和出租車(chē)空駛率（ECP），提高出租車(chē)系統運行效率。