1 什么是LBS

基于位置的服務（Location Based Services，LBS），是利用各類型的定位技術來獲取定位設備當前的所在位置，通過移動互聯網向定位設備提供信息資源和基礎服務。首先用戶可利用定位技術確定自身的空間位置，隨后用戶便可通過移動互聯網來獲取與位置相關資源和信息。LBS服務中融合了移動通訊、互聯網絡、空間定位、位置信息、大數據等多種信息技術，利用移動互聯網絡服務平臺進行數據更新和交互，使用戶可以通過空間定位來獲取相應的服務。

2 名詞解釋

• 工程師：上門履約小哥
• 圍欄：由點組成的閉合的多邊圖形，如圖所示(就是由經緯度組成的多邊形)

  
  

3 業務簡介

轉轉上門履約業務主要依托于轉轉C2B，針對3C數碼產品進行上門回收，為用戶提供快速，精確的上門服務。簡單流程圖如下：

具體步驟:

1. 用戶打開轉轉APP回收頁，根據用戶的IP信息和GPS（用戶授權情況下）獲取所在城市(或地址)是否支持上門。
2. 當用戶所在城市支持上門，判斷用戶輸入的上門地址是否支持上門。
3. 用戶對需要回收的機器進行估價。
4. 用戶下單，系統自動將訂單分配給上門小哥。
5. 上門工程師上門回收。

4 基于圍欄的曝光下單和分配訂單

4.1 曝光下單

基于二手3C數碼場景，并不能做到全國每個城市，每個角落都支持上門小哥上門回收，所以精準地判斷用戶地址是否支持上門回收對業務來說至關重要。

簡而言之，就是根據用戶下單的地址轉換成對應的經緯度坐標，根據經緯度判斷當前點是否在圍欄中，從而判斷用戶的地址是否支持上門履約。

但是將全國的地圖切割成一個個不規則的多邊形，在成千上萬的不規則圖形中，如何快速地判斷某一個經緯度在哪一個圍欄之中？目前我們采用的是兩段匹配的方式。

4.1.1 初篩：最小覆蓋區域矩形

如下圖所示，任何一個不規則的多邊形都能用一個矩形將其框住，只需要獲取右上角的坐標，和左下角的坐標就能構建這個矩形，從而快速的判斷用戶地址經緯度是否在這個矩形里邊，快速過濾掉大部分的干擾圍欄。

4.1.2 精篩：射線法精確匹配

射線算法：從待判斷的點向某一個方向引射線，計算和多邊形交點的個數，如果個數是偶數或者0，則點在多邊形外，如果是奇數，則在多邊形內（當然，一些特殊情況需要單獨判斷，比如點剛好在頂點或者邊上）。如圖所示：

根據射線法，就可以精準判斷坐標是否在圍欄內。

目前常用的判斷點在多邊形內的方法

• 射線法：時間復雜度O(n)，適用任意多邊形。
• 轉角法：時間復雜度O(n)，適用任意多邊形，對精度要求比較高。
• 角度判斷法：時間復雜度O(n)，適用任意多邊形，和轉角法類似，對精度要求比較高。
• 叉積判斷法：時間復雜度O(n)，適用凸多邊形。
• 面積法：時間復雜度O(n)，適用凸多邊形。
• 二分法：時間復雜度O(logn)，適用凸多邊形。
• 弧長法：時間復雜度O(n)，適用任意多邊形。

當然，還有其他的算法，如果感興趣可以自行搜索相關資料。我們根據業務場景需求以及對算法的熟悉，理解程度，最終選擇射線法作為匹配算法。為了計算的速度，所有的計算過程都是基于內存運算。

4.1.3 簡單的檢索流程

大體上分為兩個階段：

• 第一階段：服務拉取DB中的圍欄信息，做初始化數據，并在內存中構建查詢索引。
• 第二階段：用戶發起查詢，系統通過內存中的數據，根據上述算法規則計算是否在圍欄中。

4.1.4 檢索索引介紹

隨著圍欄的數量越來越多，暴力遍歷的尋找方式會大大的降低檢索的速度，所以這里我們采取的是利用R樹索引的方式來加快檢索的速度，主要加速的是最小覆蓋區域矩形

最小覆蓋區域矩形進行R樹索引

主要步驟如下：

1. 首先通過R樹迅速判斷用戶所在位置（粗紅點）是否被外包矩形覆蓋（如下圖，紅色點代表用戶所在位置；R樹平均查詢復雜度為O(Log(N))，N為多邊形個數）。
2. 如果不被任何外包矩形覆蓋則返回不在地理圍欄多邊形內。
3. 如果被外包矩形覆蓋則還需要進一步判斷是否在此外包矩形的多邊形內部，采用上文提到的射線法判斷。

R樹查詢示例

4.2 分配訂單

不同于外賣和網約車的場景，二手回收場景的訂單密度和訂單量并不是非常大，那低成本地實現快速訂單分配就極其重要。基于現狀，還是通過圍欄的匹配算法，就能找到在當前服務區域內提供服務的上門小哥。

簡單匹配流程

大體步驟：

1. 將工程師根據每個人的服務區域掛載相對應的圍欄下邊。
2. 用戶下單后，根據訂單的經緯度匹配到圍欄。
3. 找到圍欄下邊掛載的工程師，再根據相應的業務規則、特殊場景分配工程師。

5 基于定位服務的路線規劃、自主訂單調度

5.1 路線規劃

隨著訂單的數量越來越多，履約效率成為整個履約過程中極為重要的一環。而提高履約效率，最為關鍵的是要判斷訂單和人之間的距離。具體講一下整個根據距離來履約的演進過程：

• 根據兩點間的坐標點計算直線距離

這是所說的直線距離，實際為球面距離，我們的地球是一個球體，球面上的兩個點，可以通過純數學的幾何公式進行計算，感興趣的可以自行搜索公式和推導過程。

根據兩點之間計算和訂單的距離是最簡單、粗暴的方法，但是這個又會帶出另一個問題，針對一些復雜地形，只是計算直線距離會帶來極大的誤差（如遇到河流，橋梁等等，尤其像重慶這樣地形復雜的城市），如圖所示：

• 根據第三方導航服務計算距離

要計算兩點間的真實距離，由于涉及到城市的道路規劃，復雜路線，自己去實現一套智能導航系統不太現實，所以我們采用的是接入第三方的導航服務來實現人和訂單距離之間的智能導航。但是隨之也產生了問題，由于業務的特殊性，復雜性(經常需要批量調用、根據復雜業務規則計算等等)，如果用同步請求第三方的導航服務的方式來做智能規劃，這樣請求服務的耗時會明顯的增加，顯然這樣不能滿足我們性能的要求。所以針對這種場景，我們的現在的方案如下（簡圖）：

具體步驟如下：

1. 用戶下單。
2. 根據LBS服務將訂單分配到工程師身上。
3. 系統根據工程師身上的所有訂單情況（實際業務場景訂單的屬性）做訂單規劃。
4. 異步調用第三方服務，根據導航結果做計算。
5. 再根據規則，綜合計算真正的路線規劃，再將數據放入緩存中。
6. 工程師從緩存中查詢相關的信息。

5.2 自主訂單調度

隨著訂單量越來越多，實際情況也越來越復雜，后臺系統分配規則，計算再合理也有滿足不了實際情況的時候。這個時候，一線的人員自主的對訂單進行調度分配，這樣可以使得整個業務流程更加的順暢。

• 場景1：工程師A有一訂單A，但是現在工程師A臨時有事過不去，發現工程師B正好在訂單A附近，這個時候相聯系工程師B將訂單轉過去。
• 場景2：工程師A剛履約完訂單A，發現這附近剛好有一訂單B屬于工程師B，為了提高效率，工程師A可以聯系工程師B將訂單搶過來。

簡圖如下：

那如何快速地找到在某個工程師附近的訂單，或者某個訂單附近的工程師呢？顯然，暴力遍歷是可以實現的，但是明顯性能是完全不能滿足我們的要求的。基于這個場景，我們使用了ES的GEO來實現，將工程師實時的位置信息，訂單的地址信息存入ES，利用ES來快速計算。

簡單來說，就是工程師定時上報地址經緯度，存入ES。用戶下單后，將訂單地址的經緯度也存入ES，查詢的時候再直接使用ES提供的GEO查詢范圍內的數據。

"filter": [{
              "geo_distance": {
                //查詢中心點
                "location": {
                  "lat": 20.12345,
                  "lon": 100.223344
                }
                //范圍
                "distance": "3km",
                "distance_type": "arc",
              }
            }
          }]

其實很多的第三方存儲引擎都提供了GEO的服務，如MySql，Redis，ES這里就不展開講了，有興趣可以自行搜索資料。

6 總結

本文描述了轉轉上門履約業務基于LBS的幾種不同場景的簡單使用，當然除了上面描述的場景，還有更多的復雜的使用需要根據不同的業務的場景做特殊，定制化的處理。隨著數據量的不斷增加，業務的實現方式，檢索的方式也是需要不斷的優化，服務也需要不斷的升級，為業務保駕護航。

7 參考文檔

• https://www.cnblogs.com/lbser/p/4471742.html
• https://my.oschina.net/1024bits/blog/782820
• https://www.cnblogs.com/yym2013/p/3673616.html
• https://blog.csdn.net/WilliamSun0122/article/details/77994526
• https://toutiao.io/posts/4as8i9/preview

關于作者：劉山，轉轉履約業務研發工程師