基于GPS的新型出租車調度系統設計
加入技術交流群
2）在GIS地圖中事先注冊乘車地點，將該地點的經緯度信息與固定電話號碼綁定，乘客用綁定的固定電話撥打調度中心，調度中心即可確定撥入用戶的叫車位置，實現電話調度。這樣，注冊的固定電話（包括：家庭固話和公用電話亭電話等）都等價于出租車應召站點，這種叫車方式，調度中心無須人工參與，系統自動完成調度。
3）短信叫車，乘客事先注冊幾個自己經常打車的地點，比如說家、公司等，然后將該地點的經緯度信息、手機號碼和位置標簽關聯，乘客需要叫車時發送事先注冊好的位置標簽短信，調度中心即可確定叫車乘客位置，從而實現短信調度。這三種叫車方式，調度中心端無須調度員人工干預，自動調度，方便乘客，節省資源。
2.2 基于網格的調度算法
現有的出租車調度中心大多設計為人工服務模式，首先調度中心不斷采集在系統中注冊的出租車的狀態，然后將為空載狀態的出租車按照先進先出原則送入一個隊列；最后對于每個在線預約的乘客請求，調度員會按照自己以往的經驗，人工確定最方便的一輛出租車，如果同時有多個出租車滿足請求，就按照先進先服務的方式前去服務，這種方式人工成本較高，且服務質量難以提高。
本系統放棄人工服務方式，采用系統自動調度方式。
本調度服務程序采用基于網格的出租車調度算法，該算法具體過程如下：
（1）劃分城市網格。在GIS地圖上根據城市大小，用適當的矩形框把城市覆蓋，獲取矩形框對角線的經緯度信息：左上角經緯度值為（a,b）、右下角經緯度值為（c,d）；結合城市出租車數量確定網格數（M×N）。
城市出租車總數為Tsum，出租車空載率為Pec，空載出租車數為Tec=Pec×Tsum。選取網格數約等于空載出租車數Tec≈M×N，為了計算方便，一般M、N選擇為2的冪次數（如：16、32、64、128、……），同時為了保證網格長寬盡量接近，所以選擇M/N比值盡量靠近
值。
?。?）劃分城市經緯度數組。確定M、N值以后，把所選城市經度范圍（a,c）均分為M份，存入經度數組citylongitude[M]中，相鄰值間隔為
；同時將城市緯度范圍（b,d）均分為N份，存入緯度數組citylatitude[N]中，相鄰值間隔為
。劃分經緯度數組是為了下面使用二分法計算出租車和請求乘客所在網格。
?。?）網格信息維護。通過劃分城市經緯度數組確定網格數組CityGrid[M][N]，網格數據結構包括網格經緯度等基本信息，同時每個網格動態維護兩個鏈表：網格空車鏈表和網格乘客鏈表。城市網格結構如圖4所示。
a.網格空車鏈表初始化。將當前系統中的所有空載出租車根據所處位置，通過二分法計算出租車所屬網格，加載到對應網格空車鏈表中，由于網格空車鏈表需要根據出租車終端上報的狀態信息實時調整，鏈表的增刪操作較為頻繁，因此本系統中網格空車鏈表采用雙鏈表結構。鏈表中的結點數據結構如表1所示。
評論