基于GeoHash和B+樹的環衛車調度算法

許鎮堯，余偉豪

（南華大學計算機學院，衡陽 421200）

0 引言

隨著社會的快速發展，垃圾存量急劇上升，“垃圾圍城”“垃圾圍村”正日益成為困擾中國各個城市、鄉村的難解之題。垃圾的處理主要依賴環衛部門調度環衛車去進行垃圾的收集和轉運，在垃圾存量急劇上升的現狀下，環衛的壓力逐漸增大，環衛車容易出現混裝混運、調度困難等問題。而垃圾運輸關聯著垃圾源頭和垃圾處理點，當垃圾運輸環節出現問題，極其容易讓垃圾源頭和垃圾處理點出現二次污染［1］。

程賜勝等［2］提出可以把環衛車清運系統看成是一個整體，通過利用改進編碼設計、交叉和編譯操作的遺傳算法更好、更方便地獲取問題的最優解；潘旺洋［3］提出將設施選址和路徑優化進行結合，利用串行運行禁忌搜索算法和遺傳算法進行求解；李鑫等［4］通過引入垃圾元去量化垃圾存量，利用Dijkstra算法實現帶反饋機制的環衛車系統調度算法，提高了運輸效率和垃圾的管理；龔達欣［5］通過分析垃圾收集點的分布情況和垃圾清運的情況，提出了利用密度峰聚類改進的二代非支配排序遺傳算法建立帶動態時間窗的多目標環衛車調度模型,并利用加入區域破壞重建算子的蟻群算法的帶動態時間窗的單目標環衛車調度模型。

在以上對環衛車調度的相關問題研究基礎上，本文以現實情況為背景，為了幫助解決環衛車的調度問題，盡量避免出現垃圾的二次污染，提出了基于GeoHash編碼［6］和B+樹的環衛車調度算法。

1 GeoHash編碼

GeoHash算法由Niemeyer［7］提出，核心是將經緯度（二維數據）轉為可比較式的字符串（一維數據）。

眾所周知，經度范圍從東經180°到西經180°，緯度范圍從南緯90°到北緯90°。在此設區間范圍分別為［-180，180］和［-90，90］。假設取緯度區間范圍為［-90，0）的區域用0表示（0，90］的區域用1表示，則可以得到圖1。

同理，對經度進行劃分，即［-180，0）、（0，180］分別用0、1表示，其放在第1位上，即得到圖2。

假設對緯度進行GeoHash最初始的01編碼，流程如圖3所示。

于是可以利用上述流程將一個數值為26.898043的緯度進行01編碼，結果見表1。

表1 編碼結果表

這樣就得到其編碼為1010011001。經度的01編碼方式同理，區間初始為［-180，80］，對一個數值為112.608634的經度進行編碼，結果為1101000000。將兩種編碼合并，按先經度、后維度的次序依次放，結果如圖4所示。

最后進行Base32編碼，先將合并后的01串以五個一組進行劃分，劃分后為11100 11000 01010 00001，轉為十進制后為28 24 10 1，再根據圖5編碼對應得到其Base32編碼為wsb1。

如此，便得到長度為4的GeoHash碼，若不斷地繼續往下分，其精度誤差則不斷減小，從表2可以看出，當GeoHash長度達到10時，其精度誤差不到6 m。

表2 GeoHash編碼性能對比結果

當獲取所有環衛車和垃圾點的實時位置以及對應的實時垃圾存量，在需要調度環衛車時，使用GeoHash編碼將其地理位置的經緯進行編碼［8］，然后根據B+樹索引檢索其擁有最長共同前綴的地點即可找到符合條件的環衛車進行調度。

2 環衛車調度算法設計

需要獲取到城市各垃圾點和垃圾處理點的位置信息，即經緯度，通過GeoHash編碼的過程將所有位置信息進行編碼處理［9］，方便對環衛車進行調度的同時，對相關的位置進行隱私保護［10-11］。將垃圾點的GeoHash編碼和該站的所有垃圾存量信息進行輸入（見算法01行），設定搜尋的精度（見算法02行），即可為其調度合適的環衛車進行垃圾運輸。通過遍歷輸入垃圾點的所有垃圾存量信息（見算法04行），當某個類別的垃圾存量達到了垃圾點設定的閾值，通過B+樹檢索適合的環衛車進行記錄（見算法06行至24行）。最后返回該站點所有類別超過閾值的垃圾所找到的環衛車信息。對于傳統垃圾清運模式下的環衛車調度，只需將垃圾類別設置為一個類別，同樣可以使用如下算法。

輸入：輸入垃圾點的數據信息，包括該站點的Geo-Hash編碼和所有的垃圾存量信息

輸出：所有類別超過閾值的垃圾所找到的環衛車信息

01 GeoHashCode←該站點經緯度的GeoHash編碼

02 length←GeoHashCode長度

03 carMap←NULL//環衛車數據信息，Map類型

04 for category∈所有類別的垃圾do

05 percentage←該垃圾站中對應的category垃圾的存量百分比

06 if percentage＞=垃圾點設置的閾值then

07 minDistance←＋∞//最小距離

08 searchCap←percentage*該站點的可用存量

09 carInfo←NULL//可調度的環衛車信息

10 for i∈［0,length］do

11 code← 取geoHashCode的前length-i的子串

12 carList←通過B+Tree進行搜索與code有完全相同前綴的環衛車集合

13 for car∈carList do

14 distance←car與該站點的距離

15 if distance＜minDistance then

16 minDistance←distance

17 carInfo←car

18 end if

19 if carInfo!=NULL then

20 carMap←添加一個該category垃圾的所對應找到的環衛車信息

21 break

22 end if

23 end for

24 end if

25 end for

26 return所有類別垃圾所找到的carInfo

3 結語

為了解決環衛壓力、避免垃圾的二次污染、緩解調度壓力等問題，本文提出了基于GeoHash編碼和B+樹的環衛車調度算法，能讓使用者根據自己的意愿對垃圾存量的閾值和環衛車搜尋精度進行設置，幫助環衛部門更好地解決環衛車調度問題。而且該算法能適用于傳統的垃圾清運模式下的環衛車調度和垃圾分類下的垃圾清運模式的環衛車調度［12］。