彭鵬，倪志偉，朱旭輝

（1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009；2.北方民族大學(xué)，銀川 750021；3.過程優(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）?？臻g眾包指以時(shí)空數(shù)據(jù)管理平臺為基礎(chǔ)，將具有時(shí)空特性的眾包任務(wù)分配給非特定的眾包參與者，要求眾包參與者在一定約束條件下完成任務(wù)的一種新型眾包計(jì)算模式［1］。共享經(jīng)濟(jì)和互聯(lián)網(wǎng)的廣泛應(yīng)用使近年來各類O2O（Online To Offline）應(yīng)用都采用了空間眾包技術(shù)來提高其服務(wù)質(zhì)量，如交通運(yùn)輸、電商平臺、各類社交平臺和自然災(zāi)害防控等。空間眾包應(yīng)用廣泛，遍及衣食住行等各領(lǐng)域，如滴滴打車、美團(tuán)外賣、餓了么等平臺。隨著終端硬件、數(shù)據(jù)分析技術(shù)和優(yōu)化算法的不斷發(fā)展和升級，空間眾包應(yīng)用將會扮演著越來越重要的角色［2］。如新冠肺炎此類傳染疫情防控期間，人們可以通過空間眾包平臺實(shí)現(xiàn)多項(xiàng)社會服務(wù)，避免人員聚集，對疫情防控具有積極作用。

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

空間眾包任務(wù)分配算法主要為貪婪算法。如文獻(xiàn)［6-7］中均使用貪婪算法計(jì)算3 類對象的動態(tài)效用。文獻(xiàn)［11］中將在線最大加權(quán)二部匹配問題的最新算法擴(kuò)展到全局在線微任務(wù)分配，并提出二階段框架，使用貪婪算法計(jì)算。文獻(xiàn)［12］中以實(shí)時(shí)專車類服務(wù)為例，令所有乘客在訂單被分配后至專車抵達(dá)期間的等待時(shí)間之和最小，研究了動態(tài)在線最小化二分圖權(quán)值和匹配模型，通過實(shí)驗(yàn)說明貪心算法求解該模型具有很好效果。除貪婪算法外，文獻(xiàn)［3］中用禁忌算法計(jì)算任務(wù)分配的總移動成本。文獻(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)境下的交互場景，上述算法能在不同場景中使用，但貪婪算法效率較低，強(qiáng)化學(xué)習(xí)訓(xùn)練模型需要較長時(shí)間。群智能算法更適合較多任務(wù)和工作者匹配組合求解，計(jì)算效率高，且不需要訓(xùn)練模型。

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

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

1 SSCTA模型

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

1.1 SSCTA模型定義

研究場景假設(shè)模型符合以下前提條件：1）在線空間眾包工作者才有可能接收到任務(wù)；2）空間眾包工作者正在完成任務(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個面積為R的正方形，某一時(shí)間戳T內(nèi)的每一個正方形組成一個時(shí)空單位K，K=R×T。

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

定義5延時(shí)等待效用。延時(shí)等待時(shí)間是用戶從發(fā)出任務(wù)申請到工作者到達(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用戶滿意效用。用來描述用戶滿意程度的高低，用suw表示，由用戶偏好效用和延時(shí)等待效用、任務(wù)完成期望組成。任務(wù)完成期望由對應(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ì)

通過隨機(jī)抽樣共發(fā)放500 份問卷（收回問卷495份，其中有效問卷490 份），問卷主要內(nèi)容是調(diào)研用戶偏好的指標(biāo)及用戶對延時(shí)等待的閾值接受程度，通過與20 位調(diào)查對象深度訪談與頭腦風(fēng)暴產(chǎn)生。調(diào)查過程是對合肥市商業(yè)區(qū)和住宅區(qū)等人員密集的地區(qū)隨機(jī)采樣，人群年齡分布為20 歲以下占26.8%，20～50 歲占70.3%，50 歲以上占2.9%。用戶偏好設(shè)置為多選。統(tǒng)計(jì)發(fā)現(xiàn)用戶對遵守交通規(guī)則、車內(nèi)衛(wèi)生、駕駛平穩(wěn)、文明禮儀、路況熟悉度、車輛品質(zhì)等六個方面最為重視，其次還有用戶對工作者性別、車內(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)給予綜合評價(jià)，取值范圍是［0，100］；E、F、G 由各用戶在任務(wù)完成后對該工作者評價(jià)，取值范圍也是［0，100］；工作者性別指標(biāo)主要從安全角度考慮，如女性用戶在夜晚出行時(shí)，傾向女性工作者，取值為0 或者100，性別符合為100，否則為0。

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

問卷還針對用戶等待時(shí)間，以0 s～100 s、100 s～300 s、大于300 s 分段進(jìn)行了調(diào)查。調(diào)查發(fā)現(xiàn)82%以上用戶對從發(fā)出任務(wù)申請到系統(tǒng)指派工作者到達(dá)任務(wù)地點(diǎn)的理想等待時(shí)間在100 s 內(nèi)（含系統(tǒng)分配任務(wù)時(shí)間，分配任務(wù)理想時(shí)間為20 s），75%以上用戶認(rèn)為可接受最長等待時(shí)間為300 s，超過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，詳見定義5。

1.2.3 SSCTA模型構(gòu)建

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

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

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

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

2.1 GSO算法原理

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

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

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

2.2 IGSO-SSCTA方法整體方案

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

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

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

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

1）編碼和解碼。

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

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

反向?qū)W習(xí)［28］主要是檢測種群某時(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ì)算。

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

其中：g∈[1，m]。

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

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

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

表2 四種移動策略Tab.2 Four mobile strategies

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

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

6）不可行解處理。

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

2.2.3 IGSO-SSCTA方法流程和步驟

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

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

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

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

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

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

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

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

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

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

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

算法空間復(fù)雜度分析：初始化離散螢火蟲種群和參數(shù)空間復(fù)雜度為O（n*m）；計(jì)算螢火蟲個體間距離的空間復(fù)雜度為O（n*m）；計(jì)算螢火蟲個體位置更新的空間復(fù)雜度為O（m*p）；螢火蟲群位置更新的空間復(fù)雜度為O（n*m*p）；所以，該離散型螢火蟲算法空間復(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)定，為了對比其他算法，t取200）。本文所有對比實(shí)驗(yàn)均取20 次獨(dú)立重復(fù)實(shí)驗(yàn)的平均值作為對比數(shù)據(jù)。因?yàn)橛脩羝煤脱訒r(shí)等待均需要考慮，假設(shè)兩方面對用戶同等重要，r1=0.5，r2=0.5。設(shè)定模擬用戶滿意效用和延時(shí)等待效用的最大值均為100，經(jīng)實(shí)驗(yàn)計(jì)算，兩類數(shù)據(jù)取值在同一量綱范圍，取c1=1，c2=1。對比算法中，除表3 中的參數(shù)，其他未提及的參數(shù)或其他算法中各類參數(shù)，均使用原文默認(rèn)參數(shù)，以保持對比算法性能。

由于貪婪算法是目前空間眾包任務(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í)空單元將動態(tài)任務(wù)分配轉(zhuǎn)化為靜態(tài)場景的組合問題，前文分析該組合問題近似TSP，所以TSP 相關(guān)算法可以計(jì) 算 SSCTA模型 。IDFA（Improved Discrete Firefly Algorithm）［26］和CDFA（Change Based on Firefly Algorithm）［27］是基于另一種螢火蟲算法改進(jìn)解決組合問題取得良好效果的算法。此外，為了對比反向?qū)W習(xí)初始化策略對改進(jìn)的影響，將本文IGSO 算法初始化策略刪除后得到DGSO（Discrete Glowworm Swarm Optimization）算法。綜上，詳見表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ù)來源

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

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

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

1）不同策略用戶滿意效用對比。

根據(jù)表4 實(shí)驗(yàn)數(shù)據(jù)來源方式，假設(shè)同一空間單元連續(xù)12個時(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）。針對每個數(shù)據(jù)集分別做20 次獨(dú)立實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果見表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%。這說明IGSO-SSCTA 方法在小規(guī)模數(shù)據(jù)集上任務(wù)分配的用戶滿意效用有顯著提升，針對不同數(shù)據(jù)集有廣泛的適用性。P（R）策略用戶滿意效用最低，P（T）比P（L）均要高，這說明等待時(shí)間比路程長路在用戶滿意效用上影響更直接。靜態(tài)視角下，將Sdate1～Sdate12對應(yīng)K1～K12的用戶滿意效用，由于K1～K12是同一空間的12 個連續(xù)時(shí)間戳，所以Sdate1～Sdate12實(shí)驗(yàn)結(jié)果可直接相加。這種時(shí)空分割方法提供了靜態(tài)任務(wù)分配轉(zhuǎn)化動態(tài)任務(wù)分配的一種策略。

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

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

選擇表3 中的7 種算法來進(jìn)行性能測試對比，重復(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é)果較為接近。這說明IGSO 有較好的尋優(yōu)能力，因?yàn)樗惴ㄔ黾恿怂姆N移動策略。DGSO 在Sdate1、Sdate4和Sdate6和IGSO 求解結(jié)果很接近，在其他數(shù)據(jù)集上略低于IGSO，這說明反向?qū)W習(xí)初始化在一定程度上可以提高算法尋優(yōu)效率。GR 隨著數(shù)據(jù)集規(guī)模增大，求解結(jié)果相較于其他算法差距越來越大。IDFA、CDFA、MGSO 和FGSO 算法在不同數(shù)據(jù)集上求解結(jié)果各有優(yōu)劣，這說明適用性不同，側(cè)面說明了IGSO 算法的穩(wěn)定性。從尋優(yōu)速度看，在初始化到迭代20 次內(nèi)，IGSO 尋優(yōu)效率高于其他算法，而IGSO 與DGSO 尋優(yōu)策略相同，這說明反向?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í)間對比。

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

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

當(dāng)m分別取M2中的6 組較大規(guī)模數(shù)據(jù)集時(shí)，重復(fù)20 次獨(dú)立實(shí)驗(yàn)，平均結(jié)果見表7。在不同規(guī)模數(shù)據(jù)集計(jì)算結(jié)果中，IGSO 始終比其他對比算法要更高，IDFA 和CDFA 互有高低，始終優(yōu)于GR。綜合對比，IGSO 在較大規(guī)模數(shù)據(jù)集上仍然有更好的求解能力，說明算法穩(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)用場景下，m的取值理論上是任意正整數(shù)，而每一次分配都是在時(shí)空單位下相應(yīng)的工作者和用戶完成匹配組合，所以分割適宜大小的時(shí)空單元K，從而控制m的規(guī)模，保證IGSO-SSCTA 有較好的計(jì)算效率和穩(wěn)定性。

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

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

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

4 結(jié)語

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