1 什么是LBS

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

2 名詞解釋

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

3 業(yè)務(wù)簡介

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

具體步驟:

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



8. 
   

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

4.1 曝光下單

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

簡而言之，就是根據(jù)用戶下單的地址轉(zhuǎn)換成對應(yīng)的經(jīng)緯度坐標，根據(jù)經(jīng)緯度判斷當(dāng)前點是否在圍欄中，從而判斷用戶的地址是否支持上門履約。

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

4.1.1 初篩：最小覆蓋區(qū)域矩形

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

4.1.2 精篩：射線法精確匹配

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

根據(jù)射線法，就可以精準判斷坐標是否在圍欄內(nèi)。

目前常用的判斷點在多邊形內(nèi)的方法

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

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

4.1.3 簡單的檢索流程

大體上分為兩個階段：

• 第一階段：服務(wù)拉取DB中的圍欄信息，做初始化數(shù)據(jù)，并在內(nèi)存中構(gòu)建查詢索引。
• 第二階段：用戶發(fā)起查詢，系統(tǒng)通過內(nèi)存中的數(shù)據(jù)，根據(jù)上述算法規(guī)則計算是否在圍欄中。

4.1.4 檢索索引介紹

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

最小覆蓋區(qū)域矩形進行R樹索引

主要步驟如下：

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

R樹查詢示例

4.2 分配訂單

不同于外賣和網(wǎng)約車的場景，二手回收場景的訂單密度和訂單量并不是非常大，那低成本地實現(xiàn)快速訂單分配就極其重要?；诂F(xiàn)狀，還是通過圍欄的匹配算法，就能找到在當(dāng)前服務(wù)區(qū)域內(nèi)提供服務(wù)的上門小哥。

簡單匹配流程

大體步驟：

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

5 基于定位服務(wù)的路線規(guī)劃、自主訂單調(diào)度

5.1 路線規(guī)劃

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

• 根據(jù)兩點間的坐標點計算直線距離

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

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

• 根據(jù)第三方導(dǎo)航服務(wù)計算距離

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

具體步驟如下：

1. 用戶下單。
2. 根據(jù)LBS服務(wù)將訂單分配到工程師身上。
3. 系統(tǒng)根據(jù)工程師身上的所有訂單情況（實際業(yè)務(wù)場景訂單的屬性）做訂單規(guī)劃。
4. 異步調(diào)用第三方服務(wù)，根據(jù)導(dǎo)航結(jié)果做計算。
5. 再根據(jù)規(guī)則，綜合計算真正的路線規(guī)劃，再將數(shù)據(jù)放入緩存中。
6. 工程師從緩存中查詢相關(guān)的信息。

5.2 自主訂單調(diào)度

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

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

簡圖如下：

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

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

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

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

6 總結(jié)

本文描述了轉(zhuǎn)轉(zhuǎn)上門履約業(yè)務(wù)基于LBS的幾種不同場景的簡單使用，當(dāng)然除了上面描述的場景，還有更多的復(fù)雜的使用需要根據(jù)不同的業(yè)務(wù)的場景做特殊，定制化的處理。隨著數(shù)據(jù)量的不斷增加，業(yè)務(wù)的實現(xiàn)方式，檢索的方式也是需要不斷的優(yōu)化，服務(wù)也需要不斷的升級，為業(yè)務(wù)保駕護航。

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??