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

有效

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

1.空間眾包中工人可拒絕下的在線單點任務分配方法，其特征在于，包括：

步驟1：定義可拒絕的空間眾包問題；

步驟2：收集工人和任務歷史信息，根據原始數據計算工人和任務屬性值；

步驟3：利用主成分分析法全面分析工人對任務的興趣度，將該興趣度作為每個工人和任務對的權值；

步驟4：最大匹配下最高興趣度問題建模；

步驟5：在約束條件下，用貪心策略實現任務分配算法，得到局部最優解；

步驟6：使用KM算法解決最大匹配下最高興趣度問題，得到最優解；

步驟7：最大匹配下最高興趣度問題變形后，使用最小費用最大流算法求解最優解；

其中步驟4中：

將原始工人可拒絕任務分配問題轉化為二分圖表示，在時間片p上給定一個工人集W_p和空間任務集T_p，每個工人、每個任務作為二分圖中的一個頂點，其中工人和任務的頂點具有不同的頂點類型；當且僅當工人頂點w_i對空間任務t_j有興趣，且在時間、空間約束條件下到達任務位置時，認為工人頂點w_i和空間任務t_j之間存在一條邊，邊上有興趣度作為權重，如此，工人-任務匹配對w_i,t_j是有效的；

其次，定義最大興趣匹配問題的效用分數；采用總體任務接受度P＝max∑p_ij衡量，其中p_ij表示工人w_i對空間任務t_j的感興趣度，p_ij(∈[0,1])；

其中步驟6中：

6-1、運用貪心算法初始化可行頂標的值；

將兩個集合中點數比較少的集合補點，使得兩邊點數相同，再將不存在的邊權重設為0；設頂點w_i的頂標為l₁[i]，頂點t_j的頂標為l₂[j]，頂點w_i與t_j之間的權為p[i][j]；

6-2、用匈牙利算法尋找完備匹配；

對于左邊集合中的每個頂點，在相等子圖中利用匈牙利算法找一條增廣路徑，如果沒有找到，則修改頂標，擴大相等子圖，繼續找增廣路徑；當每個點都找到增廣路徑時，此時意味著每個點都在匹配中，即找到了二分圖的完備匹配；

如果這個二分圖存在另外一個完備匹配，如果它不完全屬于相等子圖，即存在某條邊l₁[i]+l₂[j]p[i][j]，那么該匹配的權重和就小于所有頂標的和，即小于屬于相等子圖的完備匹配的權重和；

若未找到完備匹配則修改可行頂標的值；在相等子圖中進行增廣路徑搜索，結果是沒有找到增廣路徑，這時修改頂標值，擴大相等子圖，左邊的頂標減少d，右邊的頂標增加d；

重復本步驟直到找到相等子圖的完備匹配為止。

2.根據權利要求1所述的空間眾包中工人可拒絕下的在線單點任務分配方法，其特征在于，步驟1中：

任務通過空間眾包平臺分配，一個工人最多只能完成一個任務，一旦工人完成或拒絕了一項任務，他/她就是可用的，從而被視為一個新工人，等待新任務分配；

每個任務最多被一個工人接受并執行，工人需要在任務開始前到達任務地點；工人完成任務得到相應的報酬；

任務可能因為工人對其感興趣度低而拒絕任務，若任務被分配則表示任務被執行，從當前任務集中刪除；一旦任務未分配、被拒絕或新出現，繼續等待分配；

在任意時間片中有多個工人，多個空間任務，每個工人、空間任務都存在約束，對每一個工人-任務對，用興趣度來度量工人對該任務的興趣度；

由此可拒絕的空間眾包問題描述為：讓任務盡可能被執行的情況下，工人拒絕的可能性最低。