基于用戶滿意效用的空間眾包任務(wù)分配方法

彭鵬，倪志偉，朱旭輝

（1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009；2.北方民族大學(xué)，銀川 750021；3.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室（合肥工業(yè)大學(xué)），合肥 230009）

0 引言

隨著“互聯(lián)網(wǎng)+”發(fā)展和智能客戶端的普及應(yīng)用，出現(xiàn)了很多需要供需雙方到達(dá)特定時(shí)空位置才能完成的任務(wù)，稱為空間眾包（Spatial Crowdsourcing，SC）。空間眾包指以時(shí)空數(shù)據(jù)管理平臺(tái)為基礎(chǔ)，將具有時(shí)空特性的眾包任務(wù)分配給非特定的眾包參與者，要求眾包參與者在一定約束條件下完成任務(wù)的一種新型眾包計(jì)算模式［1］。共享經(jīng)濟(jì)和互聯(lián)網(wǎng)的廣泛應(yīng)用使近年來(lái)各類O2O（Online To Offline）應(yīng)用都采用了空間眾包技術(shù)來(lái)提高其服務(wù)質(zhì)量，如交通運(yùn)輸、電商平臺(tái)、各類社交平臺(tái)和自然災(zāi)害防控等?？臻g眾包應(yīng)用廣泛，遍及衣食住行等各領(lǐng)域，如滴滴打車、美團(tuán)外賣、餓了么等平臺(tái)。隨著終端硬件、數(shù)據(jù)分析技術(shù)和優(yōu)化算法的不斷發(fā)展和升級(jí)，空間眾包應(yīng)用將會(huì)扮演著越來(lái)越重要的角色［2］。如新冠肺炎此類傳染疫情防控期間，人們可以通過(guò)空間眾包平臺(tái)實(shí)現(xiàn)多項(xiàng)社會(huì)服務(wù)，避免人員聚集，對(duì)疫情防控具有積極作用。

任務(wù)分配是空間眾包研究領(lǐng)域核心問(wèn)題之一，近年來(lái)，國(guó)內(nèi)外學(xué)者圍繞這一剛興起的問(wèn)題做了積極研究?？臻g眾包任務(wù)分配基礎(chǔ)研究包括空間眾包任務(wù)和空間眾包工作者兩個(gè)角色，任務(wù)包含空間位置、發(fā)布時(shí)間、截止時(shí)間、任務(wù)回報(bào)等屬性，工作者包括空間位置、是否在線、服務(wù)范圍等屬性［1-2］，研究目標(biāo)主要是如何將任務(wù)分配給較近的工作者，使得差旅總成本最小、總效用最大或者總時(shí)間最小［3-5］。隨著空間眾包任務(wù)分配研究的進(jìn)一步深入，更多不同的約束條件和研究目標(biāo)被考慮。文獻(xiàn)［6］中研究用戶、工作者和工作點(diǎn)三種角色，提出自適應(yīng)閾值算法并用于3 類對(duì)象的動(dòng)態(tài)分配，并提出用競(jìng)爭(zhēng)比指標(biāo)來(lái)進(jìn)行算法評(píng)價(jià)。文獻(xiàn)［7］在文獻(xiàn)［6］基礎(chǔ)上，從離線預(yù)測(cè)和在線匹配角度提供一種在線三位穩(wěn)定匹配，用不同匹配對(duì)應(yīng)的工作者總收益來(lái)進(jìn)行評(píng)價(jià)；文獻(xiàn)［8］在同時(shí)滿足眾包參與者的距離、技能和截止時(shí)間等多個(gè)條件約束下進(jìn)行任務(wù)分配，提出了基于貪心、分治和成本模型的啟發(fā)式算法，并以最大化總收益為研究目標(biāo)，以總收益函數(shù)為評(píng)價(jià)函數(shù)。文獻(xiàn)［9］中研究了空間眾包分配中給定時(shí)段的可選擇人數(shù)上限和給定全部時(shí)段可選人數(shù)上限，討論任務(wù)分配時(shí)工作者的及時(shí)覆蓋率和最大化任務(wù)分配數(shù)，用覆蓋率作為評(píng)價(jià)函數(shù)。文獻(xiàn)［10］中提出以眾包任務(wù)為核心的K近鄰查詢方法進(jìn)行眾包工作者候選，并基于動(dòng)態(tài)效用閾值來(lái)過(guò)濾選擇，盡量提高服務(wù)質(zhì)量較高工作者的服務(wù)率?，F(xiàn)有研究主要以總差旅成本、總覆蓋率或工作者總收益為研究目標(biāo)，考慮了距離、時(shí)間窗和技能匹配等約束，但是未考慮到用戶存在各類偏好和用戶滿意等因素，然而生活中用戶是否滿意對(duì)各類空間眾包平臺(tái)的最終使用和普及有重要影響。

空間眾包任務(wù)分配算法主要為貪婪算法。如文獻(xiàn)［6-7］中均使用貪婪算法計(jì)算3 類對(duì)象的動(dòng)態(tài)效用。文獻(xiàn)［11］中將在線最大加權(quán)二部匹配問(wèn)題的最新算法擴(kuò)展到全局在線微任務(wù)分配，并提出二階段框架，使用貪婪算法計(jì)算。文獻(xiàn)［12］中以實(shí)時(shí)專車類服務(wù)為例，令所有乘客在訂單被分配后至專車抵達(dá)期間的等待時(shí)間之和最小，研究了動(dòng)態(tài)在線最小化二分圖權(quán)值和匹配模型，通過(guò)實(shí)驗(yàn)說(shuō)明貪心算法求解該模型具有很好效果。除貪婪算法外，文獻(xiàn)［3］中用禁忌算法計(jì)算任務(wù)分配的總移動(dòng)成本。文獻(xiàn)［13］中嘗試應(yīng)用隨機(jī)優(yōu)化強(qiáng)化學(xué)習(xí)方法，并將司機(jī)接受任務(wù)的起始位置作為馬爾可夫模型，研究多任務(wù)分配方法。文獻(xiàn)［14］中提出多輪線性權(quán)值優(yōu)化和粒子群優(yōu)化算法，用于解決異構(gòu)空間內(nèi)任務(wù)分配覆蓋率最大化。貪婪算法更適用于在線即時(shí)分配，強(qiáng)化學(xué)習(xí)適合復(fù)雜多變環(huán)境下的交互場(chǎng)景，上述算法能在不同場(chǎng)景中使用，但貪婪算法效率較低，強(qiáng)化學(xué)習(xí)訓(xùn)練模型需要較長(zhǎng)時(shí)間。群智能算法更適合較多任務(wù)和工作者匹配組合求解，計(jì)算效率高，且不需要訓(xùn)練模型。

群智能優(yōu)化算法是受生物群體間智能協(xié)作啟發(fā)的算法，近年來(lái)不少學(xué)者利用群智能優(yōu)化算法作為各類優(yōu)化問(wèn)題特別是調(diào)度、旅行商問(wèn)題（Traveling Salesman Problem，TSP）等組合問(wèn)題求最優(yōu)解的方法。群智能優(yōu)化算法主要包括粒子群算法［14-15］、遺傳算法［16］、人工魚群算法［17］和螢火蟲(chóng)群優(yōu)化（Glowworm Swarm Optimization，GSO）算法［18-19］等。各類群智能優(yōu)化算法都有各自優(yōu)缺點(diǎn)。遺傳算法應(yīng)用廣泛，具有較強(qiáng)魯棒性，但是收斂容易過(guò)早且效率通常較低；粒子群算法搜索效率高，但是對(duì)于較高維數(shù)據(jù)尋優(yōu)，非常容易陷入局部最優(yōu)；人工魚群算法魯棒性強(qiáng)，初始條件和參數(shù)設(shè)定對(duì)它影響不大，所以適用范圍大，但是收斂速度較慢；GSO 算法運(yùn)算速度較快，在多維空間有較好尋優(yōu)能力。雖然國(guó)內(nèi)外學(xué)者通過(guò)從初始化、變步長(zhǎng)、離散化、改變移動(dòng)策略等方式［20-25］進(jìn)一步優(yōu)化算法性能，但是也存在一些不足：一方面，目前很少有基于改進(jìn)GSO 算法來(lái)解決空間眾包任務(wù)分配的研究；另一方面，改進(jìn)算法的收斂速度和全局尋優(yōu)能力有待進(jìn)一步提升。本文算法將應(yīng)用多種改進(jìn)策略，并結(jié)合空間眾包任務(wù)分配實(shí)際應(yīng)用進(jìn)行適合的有效編碼，從而快速有效解決任務(wù)分配問(wèn)題。

本文主要工作如下：1）定義了由用戶偏好效用、延時(shí)等待效用和任務(wù)完成期望組成的用戶滿意效用概念，構(gòu)建了基于用戶滿意效用的空間眾包的任務(wù)分配（Spatial Crowdsourcing Task Allocation based on user Satisfaction utility，SSCTA）模型；2）提出了一種適用分配模型的改進(jìn)離散螢火蟲(chóng)群優(yōu)化（Improved discrete Glowworm Swarm Optimization，IGSO）算法；3）提出了使用IGSO 算法計(jì)算的任務(wù)分配方法IGSO-SSCTA（SSCTA based on IGSO）。與其他算法對(duì)比的實(shí)驗(yàn)結(jié)果表明，所提算法有更優(yōu)的性能和適用性；對(duì)比其他任務(wù)分配策略，IGSO-SSCTA 具有更高的用戶滿意效用。

1 SSCTA模型

空間眾包分配模型主要考慮空間眾包任務(wù)和空間眾包工作者兩個(gè)主要概念。本文研究O2O 應(yīng)用的“實(shí)時(shí)叫車”專車類空間眾包任務(wù)分配。根據(jù)本文研究場(chǎng)景與模型的實(shí)際需要，創(chuàng)建并引入時(shí)空單位、用戶偏好效用、延時(shí)等待效用和用戶滿意效用等四個(gè)概念，對(duì)任務(wù)與工作者兩個(gè)概念的內(nèi)涵進(jìn)行了擴(kuò)充。

1.1 SSCTA模型定義

研究場(chǎng)景假設(shè)模型符合以下前提條件：1）在線空間眾包工作者才有可能接收到任務(wù)；2）空間眾包工作者正在完成任務(wù)過(guò)程中無(wú)法接收新任務(wù)；3）服務(wù)器在分配任務(wù)時(shí)，除了考慮用戶延時(shí)等待的時(shí)間（越短越好），還需考慮工作者（包含車輛，以下統(tǒng)一用工作者表示）和用戶偏好的匹配程度（越大越好）；4）用戶發(fā)布任務(wù)后，截止時(shí)間為用戶自主取消任務(wù)時(shí)，服務(wù)器只考慮當(dāng)前線上存在的任務(wù)。

模型相關(guān)概念定義如下：

定義1空間眾包任務(wù)［1］。用戶偏好空間眾包任務(wù)u=其中l(wèi)u為任務(wù)u的初始位置，tu為用戶發(fā)布任務(wù)的時(shí)間標(biāo)簽，su為任務(wù)u當(dāng)前是否正在發(fā)布，pu為用戶的各項(xiàng)偏好情況。

定義2空間眾包工作者［1］。空間眾包工作者w=其中l(wèi)w為工作者w的當(dāng)前位置，tw為工作者不同位置的時(shí)間標(biāo)簽，sw為工作者的當(dāng)前狀態(tài)（是否在線、是否正在完成任務(wù)等），qw為工作者在用戶偏好各項(xiàng)指標(biāo)下得分，zw為工作者歷史任務(wù)完成的成功率。

定義3時(shí)空單位。將研究區(qū)域等分成N個(gè)面積為R的正方形，某一時(shí)間戳T內(nèi)的每一個(gè)正方形組成一個(gè)時(shí)空單位K，K=R×T。

定義4用戶偏好效用。指工作者和用戶在用戶偏好下的匹配程度。設(shè)用戶偏好權(quán)重系數(shù)為pu，工作者在該用戶偏好對(duì)應(yīng)的得分為qw，用戶偏好效用為huw，用戶有K個(gè)偏好，用戶u和工作者w匹配的用戶偏好效用定義為huw=

定義5延時(shí)等待效用。延時(shí)等待時(shí)間是用戶從發(fā)出任務(wù)申請(qǐng)到工作者到達(dá)用戶任務(wù)位置等待的總時(shí)間，延時(shí)等待時(shí)間越大，效用越小。等待總時(shí)間由系統(tǒng)分配任務(wù)時(shí)間ts和工作者實(shí)際旅行時(shí)間tuw兩部分組成。設(shè)用戶和工作者距離為luw，工作者速度為vw，則tuw=luw/vw。等待時(shí)間為0 時(shí)效用最高，將此時(shí)的等待效用設(shè)為d0，假設(shè)系統(tǒng)分配時(shí)間為常數(shù)t0，用戶的延時(shí)等待效用為duw，滿足函數(shù)duw(t)=f(tuw+t0)。

定義6用戶滿意效用。用來(lái)描述用戶滿意程度的高低，用suw表示，由用戶偏好效用和延時(shí)等待效用、任務(wù)完成期望組成。任務(wù)完成期望由對(duì)應(yīng)的工作者歷史任務(wù)成功率zw決定，故suw=zw× (r1×huw+r2×duw)，r1、r2為用戶偏好效用和延時(shí)等待效用系數(shù)，是兩部分效用在用戶滿意效用中重要度。

1.2 SSCTA模型設(shè)計(jì)和構(gòu)建

1.2.1 用戶偏好指標(biāo)調(diào)查和設(shè)計(jì)

通過(guò)隨機(jī)抽樣共發(fā)放500 份問(wèn)卷（收回問(wèn)卷495份，其中有效問(wèn)卷490 份），問(wèn)卷主要內(nèi)容是調(diào)研用戶偏好的指標(biāo)及用戶對(duì)延時(shí)等待的閾值接受程度，通過(guò)與20 位調(diào)查對(duì)象深度訪談與頭腦風(fēng)暴產(chǎn)生。調(diào)查過(guò)程是對(duì)合肥市商業(yè)區(qū)和住宅區(qū)等人員密集的地區(qū)隨機(jī)采樣，人群年齡分布為20 歲以下占26.8%，20～50 歲占70.3%，50 歲以上占2.9%。用戶偏好設(shè)置為多選。統(tǒng)計(jì)發(fā)現(xiàn)用戶對(duì)遵守交通規(guī)則、車內(nèi)衛(wèi)生、駕駛平穩(wěn)、文明禮儀、路況熟悉度、車輛品質(zhì)等六個(gè)方面最為重視，其次還有用戶對(duì)工作者性別、車內(nèi)是否有煙味等方面提出偏好要求，具體如表1 所示。

表1 用戶偏好指標(biāo)Tab.1 Indicators of user preferences

每一項(xiàng)指標(biāo)得分均為百分制。其中，A、B、C、D 一般由系統(tǒng)根據(jù)工作者的實(shí)時(shí)數(shù)據(jù)和歷史數(shù)據(jù)系統(tǒng)給予綜合評(píng)價(jià)，取值范圍是［0，100］；E、F、G 由各用戶在任務(wù)完成后對(duì)該工作者評(píng)價(jià)，取值范圍也是［0，100］；工作者性別指標(biāo)主要從安全角度考慮，如女性用戶在夜晚出行時(shí)，傾向女性工作者，取值為0 或者100，性別符合為100，否則為0。

1.2.2 用戶延時(shí)等待效用函數(shù)

問(wèn)卷還針對(duì)用戶等待時(shí)間，以0 s～100 s、100 s～300 s、大于300 s 分段進(jìn)行了調(diào)查。調(diào)查發(fā)現(xiàn)82%以上用戶對(duì)從發(fā)出任務(wù)申請(qǐng)到系統(tǒng)指派工作者到達(dá)任務(wù)地點(diǎn)的理想等待時(shí)間在100 s 內(nèi)（含系統(tǒng)分配任務(wù)時(shí)間，分配任務(wù)理想時(shí)間為20 s），75%以上用戶認(rèn)為可接受最長(zhǎng)等待時(shí)間為300 s，超過(guò)300 s 較難接受。100 s 是用戶體驗(yàn)重要界限，100 s 內(nèi)用戶延時(shí)等待效用逐漸緩慢降低，100 s 到300 s 之間用戶延時(shí)等待效用較快下降。300 s 后延時(shí)等待效用較小，降低也較慢。綜上，將用戶的延時(shí)等待效用函數(shù)設(shè)計(jì)為分段函數(shù)，取值范圍是（0，100），具體如下，其中，tuw=luw/vw，詳見(jiàn)定義5。

1.2.3 SSCTA模型構(gòu)建

假設(shè)某時(shí)空單位下，有n個(gè)用戶和m個(gè)工作者，每個(gè)用戶都有K種偏好，m≤n，則一次任務(wù)分配中共有種工作者和用戶會(huì)匹配，每種匹配又分別有m！種 組合，這種組合匹配方式和計(jì)算量的復(fù)雜度，與經(jīng)典旅行商問(wèn)題相當(dāng)［26-27］，屬于NP（Non-deterministic Polynomial）-Hard 問(wèn)題。構(gòu)建模型和對(duì)應(yīng)約束規(guī)劃條件具體如下：

在上述模型中，式（2）表示求一次任務(wù)分配中所有用戶和工作者匹配組合的用戶滿意效用總和的最大值；式（3）～（9）分別表示總用戶滿意效用、每一對(duì)工作者與用戶的用戶偏好效用、延時(shí)等待效用、等待時(shí)間、工作者集合、工作者匹配對(duì)應(yīng)的用戶集合、用戶偏好的集合等。

2 IGSO-SSCTA任務(wù)分配方法

螢火蟲(chóng)算法共有GSO 算法［18］和FA（Firefly Algorithm）［19］兩種，原理相似，都是受螢火蟲(chóng)群個(gè)體間移動(dòng)的仿生過(guò)程啟發(fā)而設(shè)計(jì)，本文選擇螢火蟲(chóng)群優(yōu)化（GSO）算法［18］進(jìn)行改進(jìn)。

2.1 GSO算法原理

螢火蟲(chóng)的熒光素對(duì)應(yīng)目標(biāo)函數(shù)，熒光素越大螢火蟲(chóng)越亮，吸引力更強(qiáng)，吸引能力隨距離增加而較小。GSO 共有熒光素更新、選擇移動(dòng)方向、位置更新、決策域更新等階段，具體步驟如下：

其中：li(t) 是螢火蟲(chóng)的熒光素值；ρ是螢火素?fù)]發(fā)系數(shù)；γ、J(xi(t))分別指熒光素的增強(qiáng)系數(shù)和第t次迭代時(shí)的目標(biāo)函數(shù)值；Ni(t)是螢火蟲(chóng)xi在決策域內(nèi)第t次迭代時(shí)比它更亮的螢火蟲(chóng)個(gè)體組成的集合；ρij(t)指當(dāng)前螢火蟲(chóng)xi移向更亮螢火蟲(chóng)xj的概率；s是步長(zhǎng)，β為感知半徑的系數(shù)；nt為鄰域螢火蟲(chóng)數(shù)量閾值；rs為鄰閾感知半徑。

螢火蟲(chóng)群算法面向連續(xù)空間，在解決組合問(wèn)題實(shí)際應(yīng)用時(shí)，需要離散化處理。離散化通常有兩種方法：一種是通過(guò)初始離散值構(gòu)建、離散編碼和編碼更新規(guī)則［18-19］，讓算法能按照原始尋優(yōu)方式始終運(yùn)行在離散空間；另一種是將連續(xù)空間的解按概率映射到指定離散解空間。第一種方法更適合本文模型求解。

2.2 IGSO-SSCTA方法整體方案

2.2.1 目標(biāo)函數(shù)

根據(jù)SSCTA 模型，通過(guò)構(gòu)建懲罰函數(shù)的方式，用加權(quán)線性函數(shù)將多目標(biāo)轉(zhuǎn)化為單目標(biāo)問(wèn)題，再使用算法求解。目標(biāo)函數(shù)構(gòu)建如下，其中c1、c2為用戶偏好效用和延時(shí)等待效用的量綱調(diào)節(jié)系數(shù)，確保兩類數(shù)據(jù)在同一量綱級(jí)別，r1、r2參看定義6。

2.2.2 改進(jìn)離散螢火蟲(chóng)群優(yōu)化算法

為解決本文場(chǎng)景下空間眾包任務(wù)分配中的組合匹配尋優(yōu)問(wèn)題，根據(jù)應(yīng)用實(shí)際和需求，對(duì)螢火蟲(chóng)算法進(jìn)行對(duì)應(yīng)改進(jìn)，求解實(shí)際問(wèn)題。

1）編碼和解碼。

初始解按照編碼規(guī)則隨機(jī)生成，每一維度的下標(biāo)表示工作者編號(hào)，每一維度上數(shù)字表示用戶編號(hào)，第a位上的數(shù)字b代表用戶b與工作者a組合。如第2 維度上是5，就代表用戶5 與工作者2 組合。下標(biāo)順序固定不變，即工作者順序不變，用戶排序不斷變化，從而實(shí)現(xiàn)用戶和工作者各種組合匹配。

2）反向?qū)W習(xí)協(xié)同初始化。

反向?qū)W習(xí)［28］主要是檢測(cè)種群某時(shí)刻算法下的歷史較差解，根據(jù)反向數(shù)生成反向解將其代替，優(yōu)化種群整體位置［29］。設(shè)R上存在d維空間離散點(diǎn)xi=[m，n]，i∈{1，2，…，d}，則x在i維的反向數(shù)定義為：

反向?qū)W習(xí)協(xié)同初始化種群，指初始化種群時(shí)，種群按照目標(biāo)函數(shù)排序，排序在前一半的種群保持不變，排序在后一半的種群采用反向?qū)W習(xí)策略，最后兩部分種群組成新的種群，相較于隨機(jī)生成的初始種群有更好的解空間。

3）距離計(jì)算。

螢火蟲(chóng)i與螢火蟲(chóng)j使用海明距離，如果第g維上數(shù)值相同，則記為0；否則記為1。每條螢火蟲(chóng)各維上的距離總和即為兩條螢火蟲(chóng)的實(shí)際距離，詳見(jiàn)式（17）～（18）：

其中：g∈[1，m]。

4）四種改進(jìn)的移動(dòng)策略。

根據(jù)移動(dòng)規(guī)則，螢火蟲(chóng)之間尋優(yōu)移動(dòng)會(huì)導(dǎo)致一只螢火蟲(chóng)上不同維度上的值相同，即產(chǎn)生不可行解。為了保證解有應(yīng)用價(jià)值，離散螢火蟲(chóng)群算法步長(zhǎng)應(yīng)為當(dāng)前離散螢火蟲(chóng)每一維度編碼向移動(dòng)螢火蟲(chóng)同一維度編碼趨同的變化概率，且始終要保證不同維度上的解不能重復(fù)。在算法迭代中，以變異因子R引入四種移動(dòng)策略，這四種移動(dòng)策略可以保證移動(dòng)后的解仍然是可行解，包括互交換變異［30］、反演變異［30］、左相鄰交換、右相鄰交換。

以上四種移動(dòng)策略在確保解有應(yīng)用價(jià)值的前提下，能有效增加螢火蟲(chóng)移動(dòng)，避免螢火蟲(chóng)陷入局部最優(yōu)。四種改進(jìn)移動(dòng)策略均假設(shè)第2 維和第5 維的（4，1）發(fā)生移動(dòng)，具體移動(dòng)過(guò)程詳見(jiàn)表2?；ソ粨Q移動(dòng)指兩個(gè)維度上的值進(jìn)行交換，如第2 維和第5 維的（4，1）變?yōu)椋?，4）；反演指第2 維和第5 維之間的（4，6，8，1）均和對(duì)稱位置上的值發(fā)生交換，變?yōu)椋?，8，6，4）；左相鄰交換即和左邊相鄰的維度上的值發(fā)生交換，如4和3 交換、1 和2 交換；右相鄰交換以此類推，和右邊相鄰的維度上的值發(fā)生交換。

表2 四種移動(dòng)策略Tab.2 Four mobile strategies

5）移動(dòng)策略的自適應(yīng)選擇。

為針對(duì)不同迭代階段，更好地從四種不同移動(dòng)策略中選擇最適宜的移動(dòng)策略，提高收斂速度和尋優(yōu)質(zhì)量，引入自適應(yīng)選擇方法［31］，具體如下：其中：qg(t+1)表示第g種移動(dòng)策略的近期表現(xiàn)；h為適應(yīng)率，h∈(0，1)；rg(t)表示第g種移動(dòng)方式在t代的貢獻(xiàn)。G表示四種移動(dòng)策略集合，pg(t)表示第g種移動(dòng)方式在t代的選擇概率。pmin表示移動(dòng)策略的最小選擇概率，為常數(shù)。為了不降低算法的收斂速度，每迭代20 次更新1 次選擇概率，移動(dòng)方式g對(duì)應(yīng)的采用概率如下式：

6）不可行解處理。

螢火蟲(chóng)i為xi(t)={1，3，4，9，2}，鄰域更亮螢火蟲(chóng)c為xc(t)={3，4，5，7，6}，假設(shè)移動(dòng)后螢火蟲(chóng)i的第1、3 維和螢火蟲(chóng)中心位置趨同，此時(shí)xi(t+1)={3，3，5，9，2}。該解表示1號(hào)和2 號(hào)工作者同時(shí)為3 號(hào)用戶服務(wù)，這不符合場(chǎng)景應(yīng)用的前提條件，為不可行解。用以下方式處理：向螢火蟲(chóng)中心c趨同的位置集合（1，3），這兩個(gè)維度作為尋優(yōu)移動(dòng)后變化得到的位置應(yīng)保留，更新后螢火蟲(chóng)i編碼重復(fù)的位置為（1，2）。將第2 維上隨機(jī)生成不重復(fù)且在有效解空間內(nèi)的編碼。經(jīng)以上處理可能產(chǎn)生的一個(gè)解是xi(t+1)={3，7，5，9，2}，具備應(yīng)用價(jià)值。由于編碼規(guī)則和解空間的限制，按照此種方法和規(guī)則產(chǎn)生的其他解也均會(huì)是可行解。

2.2.3 IGSO-SSCTA方法流程和步驟

IGSO-SSCTA 方法步驟由SSCTA 模型和IGSO 算法兩部分組成，具體步驟如下：

步驟1 將交通數(shù)據(jù)預(yù)處理，通過(guò)無(wú)量綱化歸一化處理，將其映射到指定空間內(nèi)。

步驟2 將給定時(shí)空劃分成N個(gè)時(shí)空單元，將每個(gè)時(shí)空單元的用戶與工作者編號(hào)。

步驟3 按照編碼規(guī)則，采用反向?qū)W習(xí)協(xié)同初始化螢火蟲(chóng)群，更新種群熒光素。

步驟4 螢火蟲(chóng)群在變異因子參數(shù)下向鄰域內(nèi)最亮的螢火蟲(chóng)移動(dòng)或者按照自適應(yīng)選擇四種改進(jìn)策略移動(dòng)。

步驟5 對(duì)不可行解進(jìn)行檢查和處理。

步驟6 將目標(biāo)函數(shù)值與公告板對(duì)比，如果沒(méi)有公告板更優(yōu)，則公告板不變；反之，取代公告板數(shù)值。

步驟7 檢查是否達(dá)到終止條件（達(dá)到迭代數(shù)或達(dá)到用戶滿意效用要求），達(dá)到條件后輸出用戶滿意效用較好的任務(wù)分配組合。

2.2.4 時(shí)空復(fù)雜度分析

設(shè)種群規(guī)模為n，用戶與工作者組合數(shù)為m，用戶偏好指標(biāo)數(shù)量為p，每只螢火蟲(chóng)（m維）代表一種組合，最大迭代數(shù)為T。

算法時(shí)間復(fù)雜度分析：初始化螢火蟲(chóng)種群時(shí)間復(fù)雜度為O（n），計(jì)算一對(duì)用戶與工作者匹配的效用時(shí)間復(fù)雜度O（m*p），故每一次迭代中計(jì)算任務(wù)分配總效用時(shí)間復(fù)雜度O（n*m*p）；每次迭代中計(jì)算螢火蟲(chóng)個(gè)體間距離的時(shí)間復(fù)雜度為O（m）；每次迭代中計(jì)算螢火蟲(chóng)個(gè)體移動(dòng)的時(shí)間復(fù)雜度為O（n*m）；每次迭代中計(jì)算螢火蟲(chóng)種群位置更新的時(shí)間復(fù)雜度為O（n2*m）；因此離散型螢火蟲(chóng)算法時(shí)間復(fù)雜度為O（n2*m*T）（實(shí)際應(yīng)用中，通常n＞p）。

算法空間復(fù)雜度分析：初始化離散螢火蟲(chóng)種群和參數(shù)空間復(fù)雜度為O（n*m）；計(jì)算螢火蟲(chóng)個(gè)體間距離的空間復(fù)雜度為O（n*m）；計(jì)算螢火蟲(chóng)個(gè)體位置更新的空間復(fù)雜度為O（m*p）；螢火蟲(chóng)群位置更新的空間復(fù)雜度為O（n*m*p）；所以，該離散型螢火蟲(chóng)算法空間復(fù)雜度為O（n*m*p）。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境和參數(shù)

實(shí)驗(yàn)在Matlab R2016a 中完成，計(jì)算機(jī)參數(shù)：系統(tǒng)Windows7、內(nèi)存8 GB，CPU Intel Core i5-4460 3.2 GHz。

參照文獻(xiàn)［18，30］，結(jié)合算法參數(shù)實(shí)驗(yàn)，本文算法參數(shù)設(shè)置如下：初始種群規(guī)模n設(shè)置為20，最大迭代次數(shù)t設(shè)置為200（本文算法t=100 時(shí)已趨于穩(wěn)定，為了對(duì)比其他算法，t取200）。本文所有對(duì)比實(shí)驗(yàn)均取20 次獨(dú)立重復(fù)實(shí)驗(yàn)的平均值作為對(duì)比數(shù)據(jù)。因?yàn)橛脩羝煤脱訒r(shí)等待均需要考慮，假設(shè)兩方面對(duì)用戶同等重要，r1=0.5，r2=0.5。設(shè)定模擬用戶滿意效用和延時(shí)等待效用的最大值均為100，經(jīng)實(shí)驗(yàn)計(jì)算，兩類數(shù)據(jù)取值在同一量綱范圍，取c1=1，c2=1。對(duì)比算法中，除表3 中的參數(shù)，其他未提及的參數(shù)或其他算法中各類參數(shù)，均使用原文默認(rèn)參數(shù)，以保持對(duì)比算法性能。

由于貪婪算法是目前空間眾包任務(wù)分配的常用算法［6-7］，有學(xué)者使用基于隨機(jī)閾值的改進(jìn)貪婪算法（Greedy algorithm based on Random threshold，GR）［6］取得較好效果。MGSO（Modified Glowworm Swarm Optimization）算法［24］、FGSO（Fire Glowworm Swarm Optimization）算法［25］和本文一樣，都是在GSO 算法上改進(jìn)的較新算法，按同樣方式進(jìn)行初始編碼。本文引入時(shí)空單元將動(dòng)態(tài)任務(wù)分配轉(zhuǎn)化為靜態(tài)場(chǎng)景的組合問(wèn)題，前文分析該組合問(wèn)題近似TSP，所以TSP 相關(guān)算法可以計(jì) 算 SSCTA模型 。IDFA（Improved Discrete Firefly Algorithm）［26］和CDFA（Change Based on Firefly Algorithm）［27］是基于另一種螢火蟲(chóng)算法改進(jìn)解決組合問(wèn)題取得良好效果的算法。此外，為了對(duì)比反向?qū)W習(xí)初始化策略對(duì)改進(jìn)的影響，將本文IGSO 算法初始化策略刪除后得到DGSO（Discrete Glowworm Swarm Optimization）算法。綜上，詳見(jiàn)表3 所有算法。

表3 不同算法的主要參數(shù)Tab.3 Main parameters of different algorithms

3.2 IGSO-SSCTA方法實(shí)驗(yàn)

3.2.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源

實(shí)驗(yàn)數(shù)據(jù)包含用戶偏好、位置、速度、工作者得分、時(shí)間、工作者任務(wù)完成成功率等，其中，位置數(shù)據(jù)是在聚數(shù)力網(wǎng)站（http：//dataju.cn）［32］下載，刪除重復(fù)位置信息后，得到實(shí)驗(yàn)所需3 000 個(gè)任務(wù)地理位置坐標(biāo)，按比例映射到［0，100］，其他數(shù)據(jù)通過(guò)實(shí)際調(diào)查和隨機(jī)產(chǎn)生，具體如表4 所示。其中，考慮實(shí)際生活中，每個(gè)用戶各側(cè)重偏好均不一致，假設(shè)每個(gè)用戶存在1～2 種偏好。如果是一種偏好，則系數(shù)為1；如果存在兩種偏好，則兩種偏好系數(shù)和為1。該項(xiàng)數(shù)據(jù)為隨機(jī)生成。

表4 實(shí)驗(yàn)數(shù)據(jù)說(shuō)明Tab.4 Experimental data explanation

3.2.2 小規(guī)模數(shù)據(jù)實(shí)驗(yàn)說(shuō)明

1）不同策略用戶滿意效用對(duì)比。

根據(jù)表4 實(shí)驗(yàn)數(shù)據(jù)來(lái)源方式，假設(shè)同一空間單元連續(xù)12個(gè)時(shí)間戳組成的時(shí)空單位K1～K12依次發(fā)生M1中12 種規(guī)模的任務(wù)分配，合成12 組小規(guī)模數(shù)據(jù)集Sdate1～Sdate12。分別用四種策略計(jì)算任務(wù)分配的用戶滿意效用：第一種是IGSO-SSCTA，結(jié)果記為P（S）；第二種是考慮距離成本的任務(wù)分配［3］，結(jié)果記為P（L）；第三種考慮時(shí)間總和最小的任務(wù)分配［12］，結(jié)果記為P（T）；第四種是隨機(jī)分配，結(jié)果記為P（R）。針對(duì)每個(gè)數(shù)據(jù)集分別做20 次獨(dú)立實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果見(jiàn)表5，包含20 次實(shí)驗(yàn)結(jié)果的最大值MAX、最小值MIN 和平均值A(chǔ)VG。12 組數(shù)據(jù)集上實(shí)驗(yàn)平均值顯示，IGSO-SSCTA 方法不受用戶與工作者的位置影響，在12 組數(shù)據(jù)集上，P（S）模式用戶滿意效用總是最優(yōu)。綜合12 組數(shù)據(jù)集的平均結(jié)果，P（S）相較于P（T）、P（L）和P（R）分別提升了9.64%、11.77%、15.70%。這說(shuō)明IGSO-SSCTA 方法在小規(guī)模數(shù)據(jù)集上任務(wù)分配的用戶滿意效用有顯著提升，針對(duì)不同數(shù)據(jù)集有廣泛的適用性。P（R）策略用戶滿意效用最低，P（T）比P（L）均要高，這說(shuō)明等待時(shí)間比路程長(zhǎng)路在用戶滿意效用上影響更直接。靜態(tài)視角下，將Sdate1～Sdate12對(duì)應(yīng)K1～K12的用戶滿意效用，由于K1～K12是同一空間的12 個(gè)連續(xù)時(shí)間戳，所以Sdate1～Sdate12實(shí)驗(yàn)結(jié)果可直接相加。這種時(shí)空分割方法提供了靜態(tài)任務(wù)分配轉(zhuǎn)化動(dòng)態(tài)任務(wù)分配的一種策略。

表5 四種策略的用戶滿意效用對(duì)比Tab.5 User satisfaction utility comparison of four strategies

2）不同算法計(jì)算結(jié)果對(duì)比。

選擇表3 中的7 種算法來(lái)進(jìn)行性能測(cè)試對(duì)比，重復(fù)20 次實(shí)驗(yàn)得到圖1。7 種算法均在初始化時(shí)使用同樣編碼方式，均使用自身算法迭代更新和求解方式，種群均為20。根據(jù)目標(biāo)函數(shù)迭代200 次平均結(jié)果，得到圖1。

從整體結(jié)果看，IGSO 在12 組數(shù)據(jù)集上最終求解均優(yōu)于其他算法；DGSO 算法整體上弱于IGSO 算法，但強(qiáng)于其他算法；GR 求解結(jié)果明顯弱于其他算法；IDFA、CDFA、MGSO 和FGSO 算法計(jì)算結(jié)果較為接近。這說(shuō)明IGSO 有較好的尋優(yōu)能力，因?yàn)樗惴ㄔ黾恿怂姆N移動(dòng)策略。DGSO 在Sdate1、Sdate4和Sdate6和IGSO 求解結(jié)果很接近，在其他數(shù)據(jù)集上略低于IGSO，這說(shuō)明反向?qū)W習(xí)初始化在一定程度上可以提高算法尋優(yōu)效率。GR 隨著數(shù)據(jù)集規(guī)模增大，求解結(jié)果相較于其他算法差距越來(lái)越大。IDFA、CDFA、MGSO 和FGSO 算法在不同數(shù)據(jù)集上求解結(jié)果各有優(yōu)劣，這說(shuō)明適用性不同，側(cè)面說(shuō)明了IGSO 算法的穩(wěn)定性。從尋優(yōu)速度看，在初始化到迭代20 次內(nèi)，IGSO 尋優(yōu)效率高于其他算法，而IGSO 與DGSO 尋優(yōu)策略相同，這說(shuō)明反向?qū)W習(xí)協(xié)同初始化提高了初始解的質(zhì)量，所以提高了尋優(yōu)效率。當(dāng)?shù)\(yùn)行到100 次后，所有算法趨于穩(wěn)定，IGSO 計(jì)算結(jié)果仍然優(yōu)于其他算法。

綜上，IGSO 算法結(jié)果相比較其他6 種算法，收斂更快，求得平均結(jié)果更優(yōu)。

3）不同算法尋優(yōu)時(shí)間對(duì)比。

根據(jù)7 種算法20 次重復(fù)實(shí)驗(yàn)消耗的平均時(shí)間，得到表6。

表6 不同算法的求解時(shí)間 單位：sTab.6 Solution times of different algorithms unit：s

IGSO 比MGSO、FGSO、IDFA 耗時(shí)短，原因是使用了自適應(yīng)選擇的四種移動(dòng)策略，多種尋優(yōu)策略一定程度上減小了求解時(shí)間。在Sdate1～Sdate12上隨著數(shù)據(jù)集規(guī)模增大，7 種算法尋優(yōu)求解時(shí)間有小幅度增加，GR 尋優(yōu)時(shí)間顯著增長(zhǎng)。DGSO算法在Sdate1～Sdate3上求解時(shí)間略低于IGSO算法，在Sdate4～Sdate12高于IGSO 算法，這說(shuō)明反向?qū)W習(xí)會(huì)耗用時(shí)間；但隨著數(shù)據(jù)集規(guī)模增大，IGSO 耗時(shí)比DGSO 更短，這說(shuō)明反向?qū)W習(xí)會(huì)產(chǎn)生更優(yōu)的初始解，提高了后期尋優(yōu)的效率，所以縮短了總時(shí)間。因?yàn)? 種算法種群等主要參數(shù)相同，由此可見(jiàn)IGSO 收斂較快，尋優(yōu)速度快，IGSO、IDFA 和CDFA 相較于GR，更適用規(guī)模較大數(shù)據(jù)集。

3.2.3 較大規(guī)模數(shù)據(jù)實(shí)驗(yàn)說(shuō)明

當(dāng)m分別取M2中的6 組較大規(guī)模數(shù)據(jù)集時(shí)，重復(fù)20 次獨(dú)立實(shí)驗(yàn)，平均結(jié)果見(jiàn)表7。在不同規(guī)模數(shù)據(jù)集計(jì)算結(jié)果中，IGSO 始終比其他對(duì)比算法要更高，IDFA 和CDFA 互有高低，始終優(yōu)于GR。綜合對(duì)比，IGSO 在較大規(guī)模數(shù)據(jù)集上仍然有更好的求解能力，說(shuō)明算法穩(wěn)定性較好。

表7 七種算法在M2上的求解結(jié)果Tab.7 Results of seven algorithms on M2

從小規(guī)模數(shù)據(jù)集M1及較大規(guī)模數(shù)據(jù)集M2的實(shí)驗(yàn)可以看出，IGSO-SSCTA 相較于其他算法能較好地適用于各種規(guī)模的數(shù)據(jù)集。在實(shí)際應(yīng)用場(chǎng)景下，m的取值理論上是任意正整數(shù)，而每一次分配都是在時(shí)空單位下相應(yīng)的工作者和用戶完成匹配組合，所以分割適宜大小的時(shí)空單元K，從而控制m的規(guī)模，保證IGSO-SSCTA 有較好的計(jì)算效率和穩(wěn)定性。

3.3 IGSO算法參數(shù)調(diào)試

IGSO 算法主要參數(shù)包括種群規(guī)模、感知半徑、鄰域閾值和變異因子。其中，從上述7 種算法性能對(duì)比實(shí)驗(yàn)中可以得知迭代次數(shù)到200前，IGSO 算法結(jié)果均趨于穩(wěn)定，為測(cè)試其他參數(shù)對(duì)算法性能影響，以Sdate1為實(shí)驗(yàn)數(shù)據(jù)集，重復(fù)獨(dú)立實(shí)驗(yàn)20 次取平均值，得到圖2。

IGSO 算法計(jì)算的用戶滿意效用隨種群規(guī)模變大而遞增，直到種群規(guī)模達(dá)到20，用戶滿意效用趨于穩(wěn)定；用戶滿意效用隨著鄰域閾值的增大不斷波動(dòng)，在鄰域閾值取6 時(shí)取得最佳值；用戶滿意效用隨著感知距離的增大，計(jì)算結(jié)果先降低再升高最后又降低，在15 時(shí)達(dá)到最大值；算法隨變異因子取值變化計(jì)算結(jié)果也一直波動(dòng)，變異因子取0.4 時(shí)算法性能最優(yōu)，這說(shuō)明算法的四種移動(dòng)策略在改善算法求解性能方便有較顯著的提升作用。通過(guò)參數(shù)實(shí)驗(yàn)，種群規(guī)模取20，鄰域閾值取6，感知距離取15，變異因子取0.4。

4 結(jié)語(yǔ)

針對(duì)生活中專車類空間眾包平臺(tái)不關(guān)注用戶存在偏好和延時(shí)等待的現(xiàn)狀，為了進(jìn)一步提高用戶滿意效用，本文提出了基于用戶滿意效用的空間眾包任務(wù)分配方法IGSOSSCTA。與其他方法對(duì)比，該方法能顯著提高用戶滿意效用。改進(jìn)的離散螢火蟲(chóng)群優(yōu)化算法IGSO 與其他算法在不同規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比結(jié)果表明，IGSO 在該空間眾包任務(wù)分配應(yīng)用中有更好的適用性、穩(wěn)定性和收斂性。下一步將圍繞激勵(lì)工作者角度，研究在隱私保護(hù)前提下，如何提高專車類空間眾包工作者的服務(wù)質(zhì)量和積極性。