基于GPS的新型出租車調度系統設計

表1 出租車數據結構

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

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

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

表2 乘客數據結構

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

　　3 模擬與性能測試

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

　　4 結語

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