表1 出租車數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

　　3 模擬與性能測(cè)試

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

　　4 結(jié)語(yǔ)

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