基于多目標(biāo)規(guī)劃的眾包任務(wù)最優(yōu)打包數(shù)量的研究

劉美含 胡若妍

摘要：近年來，基于移動(dòng)互聯(lián)網(wǎng)的眾包平臺(tái)層出不窮，而任務(wù)的定價(jià)對(duì)眾包平臺(tái)的發(fā)展具有重要意義。針對(duì)現(xiàn)實(shí)中存在多個(gè)任務(wù)點(diǎn)位置比較集中的現(xiàn)象，建立了基于遺傳模擬退火算法的模糊C-均值聚類模型和多目標(biāo)規(guī)劃模型，解決了在任務(wù)打包發(fā)布的情況下任務(wù)定價(jià)問題，并分析打包數(shù)量不同對(duì)任務(wù)完成率的影響。

關(guān)鍵詞：任務(wù)打包；模擬退火算法；多目標(biāo)規(guī)劃；模糊C-均值聚類模型

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，眾包平臺(tái)日益流行，從根本上改變了傳統(tǒng)的市場(chǎng)調(diào)查方法的運(yùn)用，和傳統(tǒng)的市場(chǎng)調(diào)查相比，眾包平臺(tái)不僅大大節(jié)省調(diào)查成本，而且有效的保證了調(diào)查數(shù)據(jù)的真實(shí)性。但利潤(rùn)是眾包平臺(tái)長(zhǎng)期發(fā)展的基礎(chǔ)，因此任務(wù)定價(jià)是其核心要素。

對(duì)于任務(wù)定價(jià)這個(gè)問題，胡靜思建立了競(jìng)爭(zhēng)市場(chǎng)環(huán)境下不同交易模式定價(jià)模型，并且重點(diǎn)討論了網(wǎng)絡(luò)外部性和組內(nèi)網(wǎng)絡(luò)外部性、用戶歸屬等對(duì)定價(jià)的影響。劉曉鋼以服務(wù)定價(jià)理論和在線逆向拍賣理論為指導(dǎo)，研究任務(wù)金額與任務(wù)屬性及市場(chǎng)競(jìng)爭(zhēng)的關(guān)系，從而得出出價(jià)策略。而本文從用戶意愿角度出發(fā)，研究了在任務(wù)打包發(fā)布情況下的定價(jià)模型。

一、定價(jià)問題的分析

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

二、模型建立

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

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

（二）多目標(biāo)規(guī)劃模型的建立

由于一個(gè)任務(wù)包內(nèi)的任務(wù)僅由一位會(huì)員完成，且包內(nèi)的任務(wù)分布的比較密集，所以在一定程度上能夠減少不打包情況下包內(nèi)任務(wù)的總價(jià)。由于會(huì)員對(duì)任務(wù)的期望定價(jià)受到距任務(wù)點(diǎn)遠(yuǎn)近的影響，而生活服務(wù)的范圍是會(huì)員自身范圍的3km之內(nèi)。當(dāng)3km以上時(shí)開發(fā)商的定價(jià)方案內(nèi)存在一個(gè)基礎(chǔ)價(jià)格b。因此，我們以3km為界定義價(jià)格：

其中，nij代表第i項(xiàng)任務(wù)由第j個(gè)會(huì)員的完成情況，其可能的取值為0和1；yij為每位會(huì)員預(yù)定的任務(wù)數(shù)量；yman為每位會(huì)員的任務(wù)限額。采用求解目標(biāo)規(guī)劃算法中的序貫算法對(duì)上式進(jìn)行求解。

三、結(jié)果分析

本文數(shù)據(jù)均來自2017 年全國大學(xué)生數(shù)學(xué)建模競(jìng)賽，包括任務(wù)位置信息、定價(jià)信息、完成情況等。

首先，運(yùn)用K-means聚類分析將所給任務(wù)點(diǎn)聚類為廣州、深圳、東莞三類。分別在這三個(gè)類中進(jìn)行基于遺傳模擬退火算法的聚類分析，以廣州市為例，將任務(wù)重新編號(hào)，得到其中部分聚類中心的結(jié)果如表1所示。

其次，通過調(diào)整打包的個(gè)數(shù)，得到廣州市的任務(wù)完成率與任務(wù)打包個(gè)數(shù)之間的關(guān)系如圖1所示。

由圖1可得，廣州市的任務(wù)完成率隨著打包個(gè)數(shù)的增加大致呈增長(zhǎng)趨勢(shì)，并在打包個(gè)數(shù)為260個(gè)時(shí)出現(xiàn)峰值，其任務(wù)完成率約為0.74。由此可以得到，打包數(shù)量過少時(shí)任務(wù)的完成情況并不樂觀；而打包數(shù)量在200個(gè)以上時(shí)，任務(wù)完成率較高，對(duì)最終情況的影響較好，但是可能出現(xiàn)平臺(tái)的成本較高的問題。

四、結(jié)論

本文首先根據(jù)經(jīng)緯度進(jìn)行區(qū)域劃分，再根據(jù)距離對(duì)任務(wù)進(jìn)行打包，并分析了打包數(shù)量對(duì)任務(wù)完成率的影響。不僅可以大大地降低平臺(tái)的成本，還可以提高任務(wù)完成率，具有現(xiàn)實(shí)意義。

參考文獻(xiàn)：

[1]胡靜思.基于雙邊市場(chǎng)理論的眾包平臺(tái)定價(jià)策略研究[D].華中師范大學(xué)，2017.

[2]劉曉鋼.眾包中任務(wù)發(fā)布者出價(jià)行為的影響因素研究[D].重慶大學(xué)，2012.

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

[4]毛可.軟件眾包任務(wù)的定價(jià)模型與人員匹配方法研究及工具實(shí)現(xiàn)[D].中國科學(xué)院大學(xué)，2014.

（作者單位：南京郵電大學(xué)）