1 什么是LBS

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

2 名詞解釋

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

  
  

3 業(yè)務(wù)簡(jiǎn)介

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

具體步驟:

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

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

4.1 曝光下單

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

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

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

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

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

4.1.2 精篩：射線法精確匹配

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

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

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

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

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

4.1.3 簡(jiǎn)單的檢索流程

大體上分為兩個(gè)階段：

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

4.1.4 檢索索引介紹

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

最小覆蓋區(qū)域矩形進(jìn)行R樹(shù)索引

主要步驟如下：

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

R樹(shù)查詢示例

4.2 分配訂單

不同于外賣和網(wǎng)約車的場(chǎng)景，二手回收?qǐng)鼍暗挠唵蚊芏群陀唵瘟坎⒉皇欠浅４?，那低成本地?shí)現(xiàn)快速訂單分配就極其重要?；诂F(xiàn)狀，還是通過(guò)圍欄的匹配算法，就能找到在當(dāng)前服務(wù)區(qū)域內(nèi)提供服務(wù)的上門小哥。

簡(jiǎn)單匹配流程

大體步驟：

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

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

5.1 路線規(guī)劃

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

• 根據(jù)兩點(diǎn)間的坐標(biāo)點(diǎn)計(jì)算直線距離

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

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

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

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

具體步驟如下：

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

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

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

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

簡(jiǎn)圖如下：

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

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

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

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

6 總結(jié)

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

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

關(guān)于作者：劉山，轉(zhuǎn)轉(zhuǎn)履約業(yè)務(wù)研發(fā)工程師