基于經緯度范圍的多點任務打包算法

朱亞強

摘 要：本文以拍照賺錢任務為例，研究了一種基于經緯度范圍的多點任務打包算法。在解決“拍照賺錢”任務的定價問題時，只要給該算法提供任務的位置信息、任務包中的任務數和任務包篩選范圍，便能自動生成滿足限定條件的打包方案，其中包含有任務包內各個任務的具體位置，具有執行速度快、計算結果準確的優點。該算法的思想可以作為解決與大量詳細位置信息有關問題的雛形，推廣至外賣配送、快遞員送件等行業。

關鍵詞：數據處理 算法 打包 位置 經緯度

中圖分類號：TP319 文獻標識碼：A 文章編號：1672-3791（2018）04（a）-0022-02

1 問題背景

“拍照賺錢”是一種基于Internet的自助勞務眾包平臺，能夠滿足公司對信息收集的需求。該平臺的用戶通過拍取公司需要的照片獲取報酬。平臺中的任務定價是核心因素。而將一定區域內的任務打包發布，在一定程度上能提升用戶接受任務的積極性以及降低任務的執行難度。

2 模型的建立

實際生活中，若多個任務的位置相對集中，可以考慮將這些任務聯合在一起打包發布。

眾包平臺將任務進行打包，首先對會員的任務限額有一定要求，新會員起初只具有一次任務限額，隨著會員完成任務的增多，信譽值會提高，任務預定限額也有所增加，且任務可預定時間提前。只有任務限額大于等于任務包中任務數量的會員才有可能接受任務包。同時，考慮到會員若在領取任務包后沒有完成任務，會對眾包平臺造成巨大經濟損失與時間浪費，故眾包平臺基于各會員信譽值必然會設定一定的門檻，規避相對不講信譽的會員，以減少任務未完成的可能性。

3 會員與任務點的平均距離的確定

由于任務打包的前提是各任務的位置相對集中，以此作為任務包。我們可以以一個任務點為中心劃定邊長為3.22km的正方形區域來研究任務包的所在位置。若該正方形區域內存在至少5個任務，則可以認為該區域任務的位置相對集中，可以作為任務包。將上述條件作為標準，使用Matlab對附件一中每一個任務點進行篩選，從第一個任務點開始進行方形區域的劃分，如果滿足在方形區域內包括中心任務點有不少于5個任務點，則根據緯度與中心任務點相差的大小進行打包，如果打包成功，那么算法到達任務包內其余任務的數據時會自動跳過，繼續尋找下一個符合條件的任務包。

對于已結束任務，通過長度換算與地圖比例尺轉換，在誤差允許范圍內，認為可以在一個任務位置緯度值加減0.015°、經度值加減0.015°的近似方形區域內來研究任務包的所在位置。利用任務包算法打包后用歐幾里得距離公式求出具有領取任務包資格的會員中5個任務的平均位置與任務包中心任務位置的平均距離，作為打包模式下會員與任務的平均距離 。

4 任務包定價的確定

眾包平臺提供打包任務，不僅僅為了方便會員的任務接受，同時也為提高自身的利潤。由于對于會員而言，完成任務包所付出的勞動成本比一個個完成任務所付出的勞動成本降低，所以眾包平臺設定的任務包定價會略小于各任務單價之和，即犧牲一定的任務單價，來提高任務完成數，從而獲得更高的利潤。任務包的定價，可以由各任務單價之和，經過任務數目修正系數修正而得到。

5 任務包算法

根據運算原理寫出了一個Matlab算法。算法的具體實現思路如下：每個任務數據有兩個默認為0標志位A和B，A表征該任務是否被選中（包含在某個打包組中或無法打包自成一組），在某任務選擇打包對象時依靠這個指標判斷是否可以將該對象納入打包組，程序完成后所有任務該標志位都應為1；B表征該任務是否被打包，若被打包則將該任務折疊，不參與后續計算。算法采用兩層嵌套循環，第一層循環根據A判斷是否進行第二層循環來形成打包組，若A位為0則進行第二層循環，A位為1則跳過該任務，繼續判斷后面的任務是否滿足條件。在生成以某個任務為隊頭的打包組時，隊頭任務的A位置1，循環該任務之后所有任務，A位為0且滿足范圍條件的任務即被選入該打包組，被選中的任務A、B位置1，一旦該打包組中的任務數達到規定數量，跳出循環，繼續生成下一個打包組。若循環完成后打包組內的任務數沒有達到規定的數目，則將被選中的任務A、B位置0。無論是否形成打包組，該隊頭任務A位置回0。算法生成的最終結果中，所有任務的A位均為1，B位為1表示該任務參與以其他任務為隊頭的打包組，將被折疊，不參與后續計算，B位為0的數據為打包隊頭任務（即代表一個打包組）或不參與任何打包組的任務。

6 考慮打包模式后的任務完成情況

已知任務完成情況可以通過任務定價和會員與任務點之間的距離利用Logistic回歸模型進行估計分析。不考慮任務打包時，任務定價指的是各個任務的單價，各個任務的對于會員也沒有門檻要求，每個會員可以任意接各個任務。但是，當我們考慮到任務打包發布時，首先就對任務進行了分類：可打包的任務以及不可打包的任務。不可打包的任務依舊按照原本的單價進行發布，而可以打包的任務將進行處理后以任務包定價發布。

除了打包后任務的定價發生了變化，任務也提高了對會員的要求，打包發布的任務包任務限額小于5的會員將沒有領取資格，相應數據舍棄，假定信譽值50為眾包平臺對低信譽會員設定的門檻，則信譽值在50以下的會員也沒有資格領取任務包，相應數據舍棄。

在綜合考慮任務（包）定價、會員能否接受任務包和打包模式下會員與任務的平均距離后，通過Logistic回歸模型的預測，我們發現優化定價模型下的任務完成度達到了91.86%，高于原本定價下以及優化定價但不打包時的任務完成度。

7 結語

當實施任務打包策略時，由于任務包所包含的各個任務之間的距離很近，并且多個任務合并發布具有更高的任務定價，所以，這兩點可以對會員接受任務產生正向激勵，會員會更愿意去接受高回報的打包任務，這樣就提高了任務的完成度。任務包的對會員設定的門檻使得只有那些信譽良好的會員能夠申請任務包，同樣會得到更好的任務完成情況。由此看來，任務打包發布后的估測結果與實際情況是相符合的。

參考文獻

[1] 司守奎，孫璽菁，數學建模算法與應用[M].北京：國防工業出版社，2008.

[2] K-means聚類算法[EB/OL]，https：//wenku.baidu.com/view/cdfc8e84a8114431b80dd88a.html？qq-pf-to=pcqq.group，2017.9.16.

[3] 王千，王成，馮振元，等.K-means聚類算法研究綜述[J].電子設計工程，2012，20（7）：21-24.

[4] 根據兩點經緯度計算距離[EB/OL]，http：//blog.csdn.net/yl2isoft/article/details/16367901，2017.9.16.

[5] 黎珍惜，黎家勛.基于經緯度快速計算兩點間距離及測量誤差[J].測繪與空間地理信息，2013，36（11）：235-237.

[6] 黃興柱.基于多元logistic回歸模型的房地產預警研究[D].濟南大學，2012.

[7] Logistic回歸原理及公式推導[EB/OL]，http：//blog.csdn.net/ariessurfer/article/details/41310525，2017.9.16.

[8] 模糊綜合評價模型[EB/OL]，http：//www.doc88.com/p-99853 6159065.html，2017.9.17.