基于GeoHash和B+樹的環(huán)衛(wèi)車調(diào)度算法

許鎮(zhèn)堯，余偉豪

（南華大學(xué)計算機學(xué)院，衡陽 421200）

0 引言

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

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

在以上對環(huán)衛(wèi)車調(diào)度的相關(guān)問題研究基礎(chǔ)上，本文以現(xiàn)實情況為背景，為了幫助解決環(huán)衛(wèi)車的調(diào)度問題，盡量避免出現(xiàn)垃圾的二次污染，提出了基于GeoHash編碼［6］和B+樹的環(huán)衛(wèi)車調(diào)度算法。

1 GeoHash編碼

GeoHash算法由Niemeyer［7］提出，核心是將經(jīng)緯度（二維數(shù)據(jù)）轉(zhuǎn)為可比較式的字符串（一維數(shù)據(jù)）。

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

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

假設(shè)對緯度進(jìn)行GeoHash最初始的01編碼，流程如圖3所示。

于是可以利用上述流程將一個數(shù)值為26.898043的緯度進(jìn)行01編碼，結(jié)果見表1。

表1 編碼結(jié)果表

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

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

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

表2 GeoHash編碼性能對比結(jié)果

當(dāng)獲取所有環(huán)衛(wèi)車和垃圾點的實時位置以及對應(yīng)的實時垃圾存量，在需要調(diào)度環(huán)衛(wèi)車時，使用GeoHash編碼將其地理位置的經(jīng)緯進(jìn)行編碼［8］，然后根據(jù)B+樹索引檢索其擁有最長共同前綴的地點即可找到符合條件的環(huán)衛(wèi)車進(jìn)行調(diào)度。

2 環(huán)衛(wèi)車調(diào)度算法設(shè)計

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

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

輸出：所有類別超過閾值的垃圾所找到的環(huán)衛(wèi)車信息

01 GeoHashCode←該站點經(jīng)緯度的GeoHash編碼

02 length←GeoHashCode長度

03 carMap←NULL//環(huán)衛(wèi)車數(shù)據(jù)信息，Map類型

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

05 percentage←該垃圾站中對應(yīng)的category垃圾的存量百分比

06 if percentage＞=垃圾點設(shè)置的閾值then

07 minDistance←＋∞//最小距離

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

09 carInfo←NULL//可調(diào)度的環(huán)衛(wèi)車信息

10 for i∈［0,length］do

11 code← 取geoHashCode的前l(fā)ength-i的子串

12 carList←通過B+Tree進(jìn)行搜索與code有完全相同前綴的環(huán)衛(wèi)車集合

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垃圾的所對應(yīng)找到的環(huán)衛(wèi)車信息

21 break

22 end if

23 end for

24 end if

25 end for

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

3 結(jié)語

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