基于GPS的新型出租車調度系統(tǒng)設計
表1 出租車數據結構
b.網格空車鏈表動態(tài)維護。根據出租車終端實時上報的狀態(tài)信息,判斷是否為空載狀態(tài),如果為空載,判斷鏈表中該出租車是否為空載狀態(tài),如果為空載判斷本次是否需要將出租車調整網格,如果鏈表中沒有該出租車,根據上報的GPS位置信息計算所屬網格,將該出租車插入該網格空車鏈表中,空載狀態(tài)計算完畢。如果上報狀態(tài)為滿載狀態(tài),判斷此前出租車是否為空載狀態(tài),如果為空載,將其從空車鏈表中刪除,滿載狀態(tài)計算完畢。具體處理流程圖如圖5所示。
未調度的乘客根據所處位置,通過二分法計算乘客所屬網格,加載到對應網格乘客鏈表中,遵循“先請求先服務”
原則,本系統(tǒng)中網格乘客鏈表采用鏈表隊列結構,鏈表中的結點數據結構如表2所示。
表2 乘客數據結構
(4)乘客請求調度。通過第(3)步將出租車和乘客按照網格分組,單個網格中如果網格乘客鏈表不為空,從鏈表選擇一個乘客,同時判斷該網格中空車鏈表是否為空,如果不為空,從該鏈表中選擇一個空車去滿足該乘客請求;如果該網格中空車鏈表為空,選擇相鄰網格中空車鏈表中的空車來滿足乘客請求,直到搜索到空車為止。搜索到空載出租車后把乘客GPS位置和乘客具體文字描述位置發(fā)送給出租車終端,發(fā)送成功后,將乘客從網格乘客鏈表中刪除,同時將對應的空車從網格空車鏈表中刪除。至此,調度過程完成。
3 模擬與性能測試
我們通過一臺服務器(DELLR710機架式服務器,XEON E5504×2JSDM/4G內存條)作為調度服務器,模擬城市網格劃分為64×64=4096的系統(tǒng)調度,一臺PC機模擬10000臺出租車數據上傳GPS位置和狀態(tài)信息,上傳間隔為10s,測試內容包括:出租車司機互助調度、電話調度、短信調度。通過模擬測試10000臺出租車運行,調度服務器CPU使用率49%,證明此系統(tǒng)是高效可行的。
4 結語
本文基于GPS/GIS設計和實現了一種新型的出租車調度系統(tǒng),該系統(tǒng)改進了現有出租車調度終端和叫車方式,并提出一種基于網格的出租車調度算法,實現出租車自動調度,最大限度地減少人工參與,通過模擬測試證明該算法高效實用。通過本系統(tǒng)可以有效降低乘客等待時間(CWT)和出租車空駛率(ECP),提高出租車系統(tǒng)運行效率。
評論