[發明專利]空間眾包中工人可拒絕下的在線單點任務分配方法

有效

• 申請號: 202110075526.6
• 申請日: 2021-01-20
• 公開（公告）號: CN112819210B
• 公開（公告）日: 2023-01-13
• 發明（設計）人: 李玉;林薈薈;殷煜昱;李尤慧子;萬建
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/04
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

本發明涉及一種空間眾包中工人可拒絕下的在線單點任務分配方法。本發明首先定義可拒絕的空間眾包問題；其次收集工人和任務歷史信息，根據原始數據計算工人和任務屬性值；并利用主成分分析法全面分析工人對任務的興趣度，成為每個工人和任務對的權值；然后最大匹配下最高興趣度問題建模，討論在約束條件下，用貪心策略實現任務分配算法，得到局部最優解；最后使用KM算法來解決最大匹配下最高興趣度問題，得到最優解；最大匹配下最高興趣度問題變形后，使用最小費用最大流相關算法求解最優解。本發明通過問題建模轉化，討論工人可拒絕問題在貪心策略下的分配方法，采用KM算法和MaxFlow算法解決了在線分配、最大化興趣度問題。

技術領域

本發明屬于計算機技術領域，公開了一種空間眾包中工人可拒絕下的在線單點任務分配方法，是涉及經預測工人對任務的興趣度后進行在線分配的方法。

背景技術

在移動網絡快速發展和移動設備廣泛使用的背景下，結合眾包思想和時空大數據形成空間眾包這一位置感知技術，實現用戶將任務以及任務附帶的信息提交到平臺，平臺將一組與位置相關的任務以眾包的形式發給工人，待工人完成具體任務，這也被稱為任務分配。基于空間眾包機制，也產生了許多新的應用，如新聞、旅游、情報、災害響應和城市規劃等。利用互聯網上的零散勞動力和群體智慧，高質量、高效率、全方面完成任務，給人們的日常工作和生活帶來巨大變化。

空間眾包由用戶、眾包平臺、工人和各式空間任務組成，近年來涌現多家眾包商業平臺，如滴滴出行、谷歌街景地圖、waze等。空間眾包中有兩種任務發布模式，一種以移動用戶為中心的模式Worker Selected Tasks(WST)，平臺發布空間感知任務，從業者可以選擇附近的任何空間任務，可能會導致某些空間任務永遠不會被分配，而其他任務冗余分配；另外一種是以平臺為中心的模式Server Assigned Tasks(SAT)，平臺為從業者分配附近的任務。

其中平臺分配任務方法可分為在線任務分配和離線任務分配，目前已有的空間眾包任務分配算法大都以最大化整體任務分配數量為主要優化目標，但是根據使用場景的不同，又有不同的側重點。例如：Kazemi等將該問題歸納為任務和工人的匹配問題，采用貪心算法不斷地將未分配的任務分配給尚有任務容量的工人，但是該算法忽略了空間眾包中任務的時效性；Hien等人擴展了Kazemi的分配模型，為每一對任務工人二元組分配一個衡量分配重要性的權重，并以最大化總的任務分配權重為目標。在線任務分配中眾包平臺無法獲取未來平臺上工人和任務的情況，在某個時間片上可以通過貪心策略最大化當前目標，但是在整個時間線上仍然無法實現最大化任務分配數量的目標。針對該問題，Peng等人提出一種基于預測的任務分配算法，通過將整個區域劃分成固定大小的網格，然后通過采樣的方式預測每個網格上工人/任務的分布情況，最后采用貪心策略，最大化當前與未來所有可能的任務匹配數量之和，盡最大可能地最大化連續時間片上的任務分配數量。

現有的研究一般假設平臺分配任務，工人保證執行分配的任務。現實場景下，不能忽略的是工人對于空間任務的選擇具有主觀性，工人都希望空間平臺能分配符合他們意愿的任務，比如在自己位置附近、任務報酬高的任務，或者是與自己的知識、技能相匹配的任務。針對工人的主觀性的空間眾包問題，本發明基于平臺為中心的模式(SAT)，討論空間眾包中工人可拒絕下的在線任務分配問題，需要考慮兩個方面的約束：(1)工人對任務的主觀性通過興趣度衡量，目前互聯網大環境下數據量爆發，基于原有的工人執行任務的數據計算其興趣度值；(2)工人和任務都是動態出現，位于特定的位置，有各自的有效時間，工人需要在任務開始前抵達指定位置。Zheng Libin等首次定義有拒絕的空間眾包中最大化工人接受度的問題，但是采用的是靜態分配的方法得到最優分配，提出四種近似方法來提高分配的效率，并沒有做動態場景下的最優分配。

發明內容

本發明的一個目的是針對現有技術的不足，提供空間眾包中工人可拒絕下的在線單點任務分配方法，基于海量的工人和任務數據，使用主成分分析法(PCA)全面分析工人對任務的興趣度，在此興趣度的基礎上，考慮動態場景下空間任務的分配問題，最后達到最大匹配下最高興趣度匹配。