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

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

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

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

　　（1）劃分城市網(wǎng)格。在GIS地圖上根據(jù)城市大小，用適當(dāng)?shù)木匦慰虬殉鞘懈采w，獲取矩形框?qū)蔷€的經(jīng)緯度信息：左上角經(jīng)緯度值為（a,b）、右下角經(jīng)緯度值為（c,d）；結(jié)合城市出租車數(shù)量確定網(wǎng)格數(shù)（M×N）。

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

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

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