基于多目標規劃的眾包任務最優打包數量的研究

劉美含 胡若妍

摘要：近年來，基于移動互聯網的眾包平臺層出不窮，而任務的定價對眾包平臺的發展具有重要意義。針對現實中存在多個任務點位置比較集中的現象，建立了基于遺傳模擬退火算法的模糊C-均值聚類模型和多目標規劃模型，解決了在任務打包發布的情況下任務定價問題，并分析打包數量不同對任務完成率的影響。

關鍵詞：任務打包；模擬退火算法；多目標規劃；模糊C-均值聚類模型

隨著移動互聯網的發展，眾包平臺日益流行，從根本上改變了傳統的市場調查方法的運用，和傳統的市場調查相比，眾包平臺不僅大大節省調查成本，而且有效的保證了調查數據的真實性。但利潤是眾包平臺長期發展的基礎，因此任務定價是其核心要素。

對于任務定價這個問題，胡靜思建立了競爭市場環境下不同交易模式定價模型，并且重點討論了網絡外部性和組內網絡外部性、用戶歸屬等對定價的影響。劉曉鋼以服務定價理論和在線逆向拍賣理論為指導，研究任務金額與任務屬性及市場競爭的關系，從而得出出價策略。而本文從用戶意愿角度出發，研究了在任務打包發布情況下的定價模型。

一、定價問題的分析

任務打包方式多樣，而密集區各任務距離較近，并沒有明顯的界限，考慮到該種情況，建立基于遺傳模擬退火算法的模糊 C-均值聚類模型，克服傳統聚類算法的缺點，對任務進行打包；其次，考慮用戶的預定限額、最早任務選取時間和商家的成本問題，建立多目標規劃模型，求得新的定價方案并將任務完成度進行比較。最后，通過調節打包的數量分別計算各個任務點的任務完成情況，由于此打包定價模型的總價低于不打包情況，因此確定最優打包個數時不考慮價格因素，只分析打包個數對任務完成情況的影響。

二、模型建立

（一）基于遺傳模擬退火算法的模糊 C-均值聚類模型的建立

由于任務不在一座城市，首先用K-means聚類分析對任務點進行分類。然后在各類的內部進行研究，計算其聚類中心。利用公式反復修改聚類中心、數據隸屬度和進行分類，當算法收斂時，理論上得到了各類的聚類中心以及各個樣本對于各模式類的隸屬度，從而完成聚類劃分。但是由于該算法是一種局部搜索算法，且對聚類中心的初值十分敏感，如果初值選擇不當，它會收斂到局部極小點。因此，本文建立基于遺傳模擬退火算法的模糊C-均值聚類模型，從而得到各類的聚類中心。

（二）多目標規劃模型的建立

由于一個任務包內的任務僅由一位會員完成，且包內的任務分布的比較密集，所以在一定程度上能夠減少不打包情況下包內任務的總價。由于會員對任務的期望定價受到距任務點遠近的影響，而生活服務的范圍是會員自身范圍的3km之內。當3km以上時開發商的定價方案內存在一個基礎價格b。因此，我們以3km為界定義價格：

其中，nij代表第i項任務由第j個會員的完成情況，其可能的取值為0和1；yij為每位會員預定的任務數量；yman為每位會員的任務限額。采用求解目標規劃算法中的序貫算法對上式進行求解。

三、結果分析

本文數據均來自2017 年全國大學生數學建模競賽，包括任務位置信息、定價信息、完成情況等。

首先，運用K-means聚類分析將所給任務點聚類為廣州、深圳、東莞三類。分別在這三個類中進行基于遺傳模擬退火算法的聚類分析，以廣州市為例，將任務重新編號，得到其中部分聚類中心的結果如表1所示。

其次，通過調整打包的個數，得到廣州市的任務完成率與任務打包個數之間的關系如圖1所示。

由圖1可得，廣州市的任務完成率隨著打包個數的增加大致呈增長趨勢，并在打包個數為260個時出現峰值，其任務完成率約為0.74。由此可以得到，打包數量過少時任務的完成情況并不樂觀；而打包數量在200個以上時，任務完成率較高，對最終情況的影響較好，但是可能出現平臺的成本較高的問題。

四、結論

本文首先根據經緯度進行區域劃分，再根據距離對任務進行打包，并分析了打包數量對任務完成率的影響。不僅可以大大地降低平臺的成本，還可以提高任務完成率，具有現實意義。

參考文獻：

[1]胡靜思.基于雙邊市場理論的眾包平臺定價策略研究[D].華中師范大學，2017.

[2]劉曉鋼.眾包中任務發布者出價行為的影響因素研究[D].重慶大學，2012.

[3]何云斌，張曉瑞，萬靜，李松.基于改進遺傳模擬退火K-means的心電波形的分類研究[J].計算機應用研究，2014（11）.

[4]毛可.軟件眾包任務的定價模型與人員匹配方法研究及工具實現[D].中國科學院大學，2014.

（作者單位：南京郵電大學）