基于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］。