面向路網(wǎng)的空間眾包群組任務(wù)匹配和調(diào)度算法

錢勤紅，劉 安，孫玉娥

1(蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006) 2(蘇州大學(xué) 軌道交通學(xué)院，江蘇 蘇州 215137)

1 引 言

智能設(shè)備和移動互聯(lián)網(wǎng)的發(fā)展使得空間眾包的應(yīng)用和研究日益流行.空間眾包是一種新型的問題解決架構(gòu)，通過雇傭大眾工人來有效地完成具有時空屬性的任務(wù).目前著名的空間眾包應(yīng)用包括滴滴出行打車平臺、餓了么外賣平臺、Task Rabbit家政平臺等.在空間眾包系統(tǒng)中，任務(wù)可以分成兩類：個人任務(wù)和群組任務(wù).前者指的是單個工人就能完成的任務(wù)，比如一個外賣訂單只需安排給一個騎手.后者指的是需要多個工人組成團隊才能完成的任務(wù)，比如裝修房屋的任務(wù)需要掌握刷墻、布線、組裝家具等技能的工人團隊合作才能完成.

綜述[1]對空間眾包的現(xiàn)有工作進行了全面的梳理和總結(jié)，并指出任務(wù)匹配和任務(wù)調(diào)度(任務(wù)規(guī)劃)是研究空間眾包的兩個基礎(chǔ)問題.大多數(shù)任務(wù)匹配工作[2-5]主要針對簡單的個人任務(wù)展開研究的，即如何將任務(wù)分配最合適的工人.隨著研究的深入，有工作研究了群組任務(wù)匹配[6-11]問題，該問題旨在組建滿足任務(wù)約束的工人團隊完成任務(wù).現(xiàn)有的任務(wù)調(diào)度[12-17]工作都是針對個人任務(wù)展開研究的，為工人規(guī)劃執(zhí)行個人任務(wù)的調(diào)度序列.而關(guān)于群組任務(wù)調(diào)度問題暫時還沒有工作對此展開研究.

考慮到現(xiàn)有工作的不足，本文研究了群組任務(wù)匹配和調(diào)度問題.該問題研究的是在考慮路網(wǎng)的場景下，不僅為動態(tài)到達平臺的任務(wù)組建一個滿足技能和時空約束的團隊，同時安排團隊中工人完成任務(wù)的路線.現(xiàn)有群組任務(wù)匹配工作與本文工作的不同在于，它們都沒有從工人角度考慮.例如文獻[11]研究在線多技能任務(wù)匹配問題，依次為動態(tài)到達平臺的任務(wù)組建團隊，但該工作沒有考慮當(dāng)工人能夠完成多個任務(wù)且此刻需要去完成平臺之前分配給他的其余任務(wù)時，工人應(yīng)該以何種路線完成當(dāng)前任務(wù)和剩余待完成任務(wù).現(xiàn)有任務(wù)調(diào)度工作與本文工作的不同在于，它們都是基于任務(wù)是個人任務(wù)假設(shè)研究的，沒有考慮群組任務(wù)需要多個具有專業(yè)技能的工人合作才能完成的情況.同時，現(xiàn)有絕大部分任務(wù)匹配和調(diào)度工作都是基于歐式距離假設(shè)展開研究的，用歐式距離估計工人與任務(wù)之間的旅行成本可能與實際工人完成任務(wù)的旅行成本有較大的偏差從而導(dǎo)致匹配或調(diào)度無效.如圖1所示，假設(shè)任務(wù)和工人分別出現(xiàn)在v1和v12，兩點之間的歐式距離很近而實際路網(wǎng)距離卻很遠.為了避免出現(xiàn)類似偏差同時更貼合實際，本文假設(shè)工人完成任務(wù)的旅行成本是基于路網(wǎng)距離計算的.

圖1 路網(wǎng)樣例Fig.1 Example of road network

解決本文問題的一個直接想法是遍歷所有工人驗證其是否滿足截止時間、預(yù)算或技能約束找到有效工人集，然后在有效工人集中組建能完成任務(wù)的團隊.在考慮路網(wǎng)的場景下，遍歷驗證工人是否能在任務(wù)指定截止時間之前或成本預(yù)算內(nèi)完成任務(wù)涉及大量的最短路徑計算，在大規(guī)模路網(wǎng)上的最短路徑計算成本是昂貴的，同時待驗證的工人數(shù)量是龐大的而實際滿足約束的工人是少量的.也就是說遍歷所有工人驗證其有效性是浪費且耗時的.因此本文應(yīng)用空間換時間的思想，提出基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法框架.該框架由網(wǎng)格索引、搜索有效工人集算法和組建團隊算法組成.該框架首先通過網(wǎng)格索引存儲路網(wǎng)信息和工人信息快速過濾掉不滿足時間或預(yù)算約束的工人，避免大量無效的最短路徑計算.然后利用基于剪枝策略的搜索算法搜索到滿足任務(wù)約束的有效工人集.最后通過組建團隊算法迭代地在有效工人集中選擇最小成本覆蓋比的工人加入團隊完成任務(wù).本文的具體工作如下：

1)首先介紹了空間眾包中的群組任務(wù)匹配和調(diào)度問題，該問題旨在為動態(tài)到達平臺的任務(wù)組建團隊，同時安排團隊中工人完成任務(wù)的路線，從而最大化任務(wù)完成效用.

2)為了解決該問題，提出了基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法框架，并詳解介紹了框架內(nèi)的網(wǎng)格索引、搜索有效工人算法和團隊組建算法.

3)為了評估算法的性能，在真實數(shù)據(jù)集和合成數(shù)據(jù)集上進行了實驗.結(jié)果表明，對比其他算法，本文提出的剪枝策略和組建團隊算法更有效.

2 相關(guān)工作

綜述[1]指出任務(wù)分配、質(zhì)量控制、隱私保護、激勵機制是研究空間眾包工作的四個核心問題.其中，任務(wù)分配通常被建模為匹配問題和調(diào)度問題，同時按任務(wù)的屬性區(qū)分個人任務(wù)和群組任務(wù).然而當(dāng)前關(guān)于任務(wù)調(diào)度的工作都是基于個人任務(wù)假設(shè)開展研究的，且現(xiàn)有關(guān)于群組任務(wù)匹配的工作沒有考慮工人是如何執(zhí)行任務(wù)的.因此現(xiàn)有的方法不能直接應(yīng)用解決本文提出的問題.接下來從任務(wù)調(diào)度和群組任務(wù)匹配角度分別回顧與本文相關(guān)的工作.

2.1 任務(wù)調(diào)度問題

任務(wù)調(diào)度是指不僅需要考慮將多個合適的任務(wù)分配給工人同時還需要規(guī)劃工人完成任務(wù)的調(diào)度序列.文獻[12]研究了單工人的任務(wù)調(diào)度問題，該問題旨在給定工人的出行成本約束下，通過精確算法和近似算法為一個工人找到完成任務(wù)的調(diào)度序列，從而最大化任務(wù)完成的數(shù)量.文獻[15]研究了單工人的在線任務(wù)調(diào)度問題，考慮任務(wù)是動態(tài)到達平臺的且工人是持續(xù)更新的場景下，為一個工人規(guī)劃一條執(zhí)行任務(wù)的調(diào)度序列.文獻[14]研究了同時規(guī)劃多個工人的任務(wù)調(diào)度序列問題，它是基于文獻[2]和文獻[12]擴展的工作.該工作通過迭代進行匹配和調(diào)度，逐步逼近最優(yōu)解.文獻[16]研究了多工人任務(wù)調(diào)度問題，通過樹分解技術(shù)處理工人之間的任務(wù)沖突，從而最大化任務(wù)完成數(shù)量.文獻[17]研究了多工人在線任務(wù)調(diào)度問題，通過延遲調(diào)度和快速調(diào)度兩種算法規(guī)劃工人執(zhí)行任務(wù)的調(diào)度序列，從而使得任務(wù)完成總效用最大.

以上工作都是基于歐式距離假設(shè)展開研究的，但在實際應(yīng)用中工人是按地圖中的路線執(zhí)行任務(wù)的.雖然有部分工作[13，18]考慮了路網(wǎng)信息，但它們研究的問題與本文不同.文獻[13]研究的是基于路網(wǎng)的單工人任務(wù)調(diào)度問題，旨在為工人推薦多條互相非支配的執(zhí)行任務(wù)路線.文獻[18]研究的是基于路網(wǎng)的拼車問題，拼車問題是空間眾包的一類實際應(yīng)用問題.該工作根據(jù)拼車任務(wù)的特有屬性設(shè)計了網(wǎng)格索引存儲信息加快響應(yīng)速度，但該網(wǎng)格索引不能直接解決本文問題.原因是一方面拼車的任務(wù)屬性和本文研究的任務(wù)屬性不同，另一方面將網(wǎng)格中心之間的距離作為近似網(wǎng)格距離，這會導(dǎo)致搜索到的有效工人集是不完整的.

2.2 群組任務(wù)匹配

群組任務(wù)匹配問題是指將多個工人組成團隊去完成一個群組任務(wù)的匹配問題.文獻[6]研究了以最大化時空多樣性和可靠性為優(yōu)化目標的任務(wù)匹配問題.該工作通過貪心、隨機抽樣和分治3種不同的啟發(fā)式算法為任務(wù)組建時空多樣性和可靠性最高的團隊.文獻[7]研究了多技能任務(wù)匹配問題，該問題旨在組建一個掌握任務(wù)所需技能的工人團隊，在任務(wù)預(yù)算的約束下最大化平臺收益.文獻[8]研究了細粒度收費的群組任務(wù)匹配問題，該問題假設(shè)工人完成任務(wù)時的不同技能對應(yīng)不同收費.文獻[9]研究了以最大化團隊合作質(zhì)量為優(yōu)化目標的群組任務(wù)匹配問題，該問題假設(shè)不同工人之間的合作質(zhì)量是不同的.文獻[10]研究了任務(wù)之間存在先后依賴關(guān)系的群組任務(wù)匹配問題.文獻[11]研究了在線群組任務(wù)匹配問題，該工作通過貪心算法依次處理每個動態(tài)到達平臺的任務(wù)和工人.

3 系統(tǒng)模型和問題定義

3.1 系統(tǒng)模型

本文研究的群組任務(wù)匹配和調(diào)度系統(tǒng)由空間眾包平臺、若干個任務(wù)發(fā)布者以及若干個工人組成，如圖2所示.任務(wù)發(fā)布者通過移動設(shè)備(如智能手機)實時提交任務(wù)，每個任務(wù)都指定了地點、預(yù)算、截止時間和所需技能集.平臺在收到新的任務(wù)后，將組建一個工人團隊完成任務(wù).要求該團隊既滿足當(dāng)前任務(wù)的約束，同時不違反團隊中各工人的現(xiàn)有任務(wù)調(diào)度序列中待完成任務(wù)的約束.最后通知工人和任務(wù)發(fā)布者當(dāng)前任務(wù)的調(diào)度結(jié)果.

圖2 群組任務(wù)匹配和調(diào)度系統(tǒng)Fig.2 Group task matching and scheduling system

3.2 問題定義

定義1.(路網(wǎng)) 通過圖G=表示路網(wǎng).其中每個節(jié)點v∈V表示一個實際位置點；每條邊e=(u，v)∈E表示連接兩個實際位置點的路段；每條邊都與一個權(quán)重w(e)∈W關(guān)聯(lián)，權(quán)重表示經(jīng)過這條邊的成本.旅行成本可以用距離或時間來衡量，當(dāng)工人速度(由β表示)已知時，距離和時間可以相互轉(zhuǎn)換，因此本文將旅行距離作為旅行成本.為了簡單起見，本文假設(shè)路網(wǎng)是無向圖且工人的速度是一致且恒定的，但本文提出的解決方案很容易擴展到有向路網(wǎng)和工人速度是隨時間變化的場景中.

定義4.(群組任務(wù))t=表示一個群組任務(wù).在時間att，任務(wù)被提交到平臺上，要求在位置lt和截止時間dt之前被完成.同時分配給該任務(wù)的團隊技能并集能夠覆蓋任務(wù)所需的技能集Kt={kt0，kt1，…}，且團隊完成任務(wù)的總成本不超過預(yù)算Bt.

(1)

定義6.(工人的報酬)如果工人w被平臺安排去完成任務(wù)t，那么平臺會根據(jù)他的繞行成本支付給工人報酬R(w，t)=α.dcost(w，t).α是一個常數(shù)，表示工人報酬和繞行成本之間的比例關(guān)系.

定義8.(群組任務(wù)匹配和調(diào)度問題)給定道路網(wǎng)絡(luò)G，更新后的工人集W，當(dāng)前到達平臺的任務(wù)t，組建能夠完成任務(wù)的團隊Wt，同時更新團隊Wt中每個工人完成該任務(wù)以及剩余待完成任務(wù)的調(diào)度序列，從而最大化效用，即Max(U(t，Wt))，且滿足以下約束：

1)截止時間約束：任務(wù)需要在截止時間之前被完成.

2)預(yù)算約束：任務(wù)發(fā)布者支付給團隊的報酬不超過預(yù)算.

3)容量約束：工人的當(dāng)前任務(wù)調(diào)度序列長度不超過容量.

4)不變性約束：任務(wù)調(diào)度序列一旦確定，則不能改變.

定義9.(有效任務(wù)調(diào)度序列)當(dāng)且僅當(dāng)以下條件成立時，Sw被稱為有效任務(wù)調(diào)度序列：

1)|Sw|≤cw，即序列中待完成任務(wù)的數(shù)量不超過工人容量.

2)?t∈Sw，expt≤dt，即序列中每個待完成任務(wù)的期望完成時間都不超過對應(yīng)截止時間.期望完成時間是指工人在當(dāng)前時間沿平臺給定路線完成任務(wù)的時間，序列中每個任務(wù)都與它的期望完成時間關(guān)聯(lián)，它可能因為新任務(wù)的插入而改變.

定義10.(有效工人)給定任務(wù)t，當(dāng)且僅當(dāng)以下條件成立時，工人w才稱為有效工人，由vwt=表示，其中iloc和icost分別表示任務(wù)插入該工人任務(wù)調(diào)度序列的位置和成本：

1)Kw∩Kt≠?，即工人掌握的技能和任務(wù)需要的技能交集不為空.

3)R(w，t)≤Bt，即工人完成任務(wù)的成本不超過任務(wù)預(yù)算.

4 解決方案

本章將介紹群組任務(wù)匹配和調(diào)度問題的解決方案.首先介紹基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法框架，然后介紹框架中網(wǎng)格索引、搜索有效工人集算法和組建團隊算法.

4.1 基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法框架

在實際應(yīng)用中，由于任務(wù)是動態(tài)出現(xiàn)的，平臺只能依據(jù)當(dāng)前的信息進行調(diào)度，因此本文假設(shè)平臺依次處理每個動態(tài)到達平臺的任務(wù).對于每個任務(wù)，直接遍歷所有工人驗證其有效性然后組建團隊的方法存在大量無效的最短路徑計算.因此本文根據(jù)空間換時間的思想，提出了基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法框架，該框架通過網(wǎng)格索引預(yù)先計算存儲的信息快速過濾掉不滿足約束的工人，避免大量無效的計算，加快實時響應(yīng)速度.

如算法框架1所示.對于每個動態(tài)出現(xiàn)的任務(wù)，平臺首先根據(jù)工人的新狀態(tài)更新索引結(jié)構(gòu)，然后通過最新的索引結(jié)構(gòu)找到有效工人集以及對應(yīng)工人的有效任務(wù)序列，然后在有效工人集中找到滿足約束的團隊，最后通知團隊內(nèi)的每個工人按指定路線完成該任務(wù)，同時向任務(wù)發(fā)布者返回團隊信息.若沒有找到滿足約束的團隊，則拒絕該任務(wù)，任務(wù)發(fā)布者可以更改任務(wù)的基本信息(放寬約束，如增加預(yù)算)再次提交.

算法框架1.基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度框架

輸入：任務(wù)T，道路網(wǎng)絡(luò)圖G，工人集W

輸出：完成對應(yīng)任務(wù)的團隊集{…，，…}

1.構(gòu)建網(wǎng)格索引(G，W)

2.Foreach新出現(xiàn)的任務(wù)ti∈T

3. 根據(jù)工人們的新狀態(tài)更新網(wǎng)格索引

4.VWti=搜索有效工人算法(ti，W) //算法1

5.Wti=組建團隊算法(t，VWti) //算法4

6. IfWti≠?

7. 更新團隊中工人的任務(wù)調(diào)度序列和路線

8. 通知工人完成任務(wù)

9. 通知任務(wù)發(fā)布者團隊信息

10. Else

11. 通知任務(wù)發(fā)布者拒絕服務(wù)該任務(wù)

4.2 網(wǎng)格索引

本文使用網(wǎng)格劃分路網(wǎng)并維護工人的位置信息，加快有效工人的搜索.

定義11.(邊界節(jié)點)假設(shè)一條邊e=(u，v)中的節(jié)點u和節(jié)點v不屬于同一個網(wǎng)格，那么就稱u和v為邊界節(jié)點.每個網(wǎng)格單元gi都維護各自的邊界節(jié)點列表，由BVi表示.如圖1所示，節(jié)點v4和v5分別是g0和g5的一個邊界節(jié)點.

Dij=min{spl(u，v)|u∈BVi，v∈BVj}

(2)

同時，為了精確估計兩個節(jié)點之間的最短路徑長度，需要預(yù)先計算并存儲所有網(wǎng)格對之間的最短距離，由矩陣D表示.矩陣中每個元素Dij表示gi和gj之間的最短距離，由公式(2)計算可得，即網(wǎng)格對的各自邊界節(jié)點之間的最短路徑長度的最小值.

除此之外，每個網(wǎng)格單元gi都維護以下信息：

1)邊界節(jié)點列表BVi：該列表記錄網(wǎng)格的邊界節(jié)點.

2)節(jié)點列表Vi：該列表記錄位于該網(wǎng)格的所有節(jié)點，同時記錄節(jié)點v∈Vi到各邊界節(jié)點的最短路徑長度的最小值，記為v.min=min{|u∈BVi}.

3)鄰居網(wǎng)格列表NGi：該列表中的網(wǎng)格gj∈NGi與當(dāng)前網(wǎng)格gi之間有路徑可達，即Dij≠∞.同時該列表以Dij的值從小到大排序存儲.

4)工人列表Wi：該列表記錄當(dāng)前時間位于網(wǎng)格gi的所有工人.該列表記錄當(dāng)前或即將位于網(wǎng)格gi的所有工人，即將位于網(wǎng)格的工人是指根據(jù)其調(diào)度路徑行駛，在給定時間閾值內(nèi)能夠到達網(wǎng)格gi的工人.同時該列表以工人的當(dāng)前位置到網(wǎng)格gi的邊界節(jié)點的最短路徑長度的最小值從小到大排序存儲，由于工人位置是也是路網(wǎng)上的一個節(jié)點v，因此該最小值可以通過查詢當(dāng)前網(wǎng)格的節(jié)點列表可以快速獲取，即該最小值為v.min.也就是說更新網(wǎng)格索引中的工人并維護其有序性是快速的.

本文通過兩個節(jié)點之間的最短路徑長度下界快速過濾掉不滿足約束的工人從而加快響應(yīng)速度，最短路徑長度下界lspl(u，v)是基于網(wǎng)格對距離矩陣D計算的，如計算公式(3)所示.對于兩個節(jié)點u∈gi和v∈gj，如果兩個節(jié)點所在的網(wǎng)格相同，那么下界為lspl(u，v)=0；如果不同則lspl(u，v)=Dij+u.min+v.min，其中u.min和v.min是分別被存儲在網(wǎng)格gi和網(wǎng)格gj的節(jié)點列表中，可快速查詢得到.也就是說最短路徑長度的下界計算時間復(fù)雜度為O(1).同樣的，從節(jié)點v∈gj到網(wǎng)格gi的最短路徑長度下界如計算公式(4)所示.

本文假設(shè)工人的當(dāng)前位置和任務(wù)位置都可映射到一個路網(wǎng)節(jié)點上.為了簡化公式，本文用lspl(w，t)=lspl(clw，lt)表示工人w從當(dāng)前位置移動到任務(wù)t所在位置的最短路徑長度下界.同樣的，用lspl(ti，tj)=lspl(lti，ltj)表示任務(wù)ti和任務(wù)tj之間的最短路徑長度下界.

最后，分析更新網(wǎng)格索引的時間復(fù)雜度.根據(jù)上述信息可知，只有工人列表是需要更新的，其余路網(wǎng)信息都是靜態(tài)的，只需要計算一次.最壞情況是所有工人都移動到新的網(wǎng)格，也就是說需要更新每個網(wǎng)格的工人列表.因此更新網(wǎng)格索引的時間復(fù)雜度等于更新每個網(wǎng)格的工人列表并維護其有序性的時間復(fù)雜度，O(nng×nw×lognw).

(3)

(4)

4.3 剪枝策略

為了避免大量無效的最短路徑計算，接下來根據(jù)之前公式(3)計算的最短距離下界設(shè)計不同的剪枝策略.

剪枝2.給定任務(wù)t，網(wǎng)格gi，若lspl(gi，lt)>(dt-att)×β，那么位于網(wǎng)格gi內(nèi)的所有工人都將被剪掉.具體而言位于網(wǎng)格gi的所有工人無法在截止時間之前完成該任務(wù)，因此該網(wǎng)格內(nèi)的工人可被安全剪去.同樣的，給定一個工人w，若lspl(clw，lt)>(dt-att)×β，那么也無需繼續(xù)驗證該工人的有效性.

剪枝3.給定任務(wù)t，空閑工人w，若lspl(clw，lt)>Bt/α，那么該工人將被過濾掉.具體而言由于將當(dāng)前任務(wù)插入空閑工人的任務(wù)調(diào)度序列產(chǎn)生的繞行成本下界超過了任務(wù)的預(yù)算成本，即支付給該工人的最低報酬超過了任務(wù)預(yù)算，因此不需要實際計算最短路徑長度驗證該工人的有效性.

剪枝4.給定任務(wù)當(dāng)前的有效工人集VW，空閑工人w，若?vw∈VW，Kw?Kvw且lspl(w，t)≥dcost(vw，t)，這表示w被vw支配[19].具體而言，若VW中存在一個有效工人vw，w掌握的技能被vw掌握的技能包含，同時w完成任務(wù)的繞行成本下界大于等于vw完成任務(wù)的繞行成本，則不需要驗證該工人的有效性就可將其直接剪去.

剪枝5.給定任務(wù)t，非空閑工人w，和插入位置i∈{0，1，…，|Sw|}，若Sw.expti-1+lspl(lti-1，lt)/β>dt，那么對于插入位置i，i+1，…，|Sw|都直接跳過可行性檢查.其中Sw.expti-1表示插入位置前一個任務(wù)在調(diào)度序列Sw內(nèi)的期望完成時間，是在處理ti-1時計算并存儲的.具體而言，將t插入w的Sw中的位置i時，若工人完成任務(wù)t的最早期望時間超過截止時間，則不需要驗證當(dāng)前以及后續(xù)插入位置i，i+1，…，|Sw|的有效性.

剪枝6.給定任務(wù)t，非空閑工人w，和插入位置i∈{0，1，…，|Sw|}，若ld(w，t，i)>Bt/α，那么對于非空工人的插入位置i跳過有效性檢查.具體而言，將t插入w的Sw中的位置i時，若工人完成該任務(wù)的繞行成本下界超過任務(wù)預(yù)算成本，則無需計算實際繞行成本驗證該插入位置是否有效.

ld(w，t，i)表示繞行成本下界，如計算公式(5)所示.公式(5)中，當(dāng)i=0時，由于工人的當(dāng)前位置在任務(wù)到達平臺時已更新，這意味著工人的當(dāng)前位置與任務(wù)t0的位置之間的距離為(Sw.expt0-att)×β，通過任務(wù)的期望完成時間避免了工人當(dāng)前位置到任務(wù)t0的最短距離計算.其他插入位置的繞行成本下界以相同的方式計算.

(5)

剪枝7.給定任務(wù)t，非空閑工人w，插入位置i∈{0，1，…，|Sw|-1}，若?tj∈{tsi，tsi+1，…}，Sw.exptj+ld(w，t，i)/β>dtj，那么對于非空工人的插入位置i跳過可行性檢查.具體而言，將t插入w的Sw中的位置i時，若插入位置后的剩余任務(wù)的期望完成時間違反了自身的截止時間約束，則不需要計算實際繞行成本驗證該插入位置是否有效.

剪枝8.給定有效工人集VW，非空閑工人w，插入位置i，若?vw∈VW，Kw?Kvw且ld(w，t，i)≥dcost(vw，t)，則可以不繼續(xù)檢查該插入位置i的有效性.具體而言，若VW中存在一個有效工人vw，w掌握的技能被vw掌握的技能包含，同時w完成任務(wù)的繞行成本下界大于等于vw完成任務(wù)的繞行成本，則無需計算實際繞行成本驗證該插入位置是否有效.

4.4 搜索有效工人集

由于任務(wù)有技能、時間和預(yù)算的約束，不是所有工人都能完成任務(wù)，因此應(yīng)該在不違背約束條件的前提下找到可以完成任務(wù)的有效工人集.

對于每個動態(tài)任務(wù)t，根據(jù)有效工人的定義，本文設(shè)計了高效的搜索算法為任務(wù)找到有效工人集.搜索有效工人算法如算法1所示，該算法從任務(wù)所在的網(wǎng)格單元gt開始搜索工人，之后搜索該網(wǎng)格gt的鄰居網(wǎng)格列表NGt(第3行).在搜索網(wǎng)格gi內(nèi)的有效工人之前，需要驗證當(dāng)前搜索的網(wǎng)格是否有效，即若當(dāng)前網(wǎng)格內(nèi)所有工人的技能并集不包含一個或多個任務(wù)所需技能，則跳過該網(wǎng)格檢查下一個網(wǎng)格(第4-5行，剪枝1)；若任務(wù)與當(dāng)前網(wǎng)格gi的最短距離下界超過任務(wù)的最大等待距離，則直接跳出該循環(huán)結(jié)束搜索(第7-8行，剪枝2).原因是任務(wù)所在網(wǎng)格gt的鄰居網(wǎng)格列表NGt是按最短距離升序存儲的，也就是說在當(dāng)前搜索網(wǎng)格gi的工人們無法按時完成任務(wù)，那么接下來待搜索的網(wǎng)格距離任務(wù)更遠，完成任務(wù)的時間更晚，不可能滿足任務(wù)的截止時間約束，因此不繼續(xù)搜索剩余網(wǎng)格.接下來在合格網(wǎng)格中搜索有效工人集.同樣的，根據(jù)剪枝1和剪枝2過濾掉無效的工人(第11-15行).需要注意的是，網(wǎng)格中工人列表也是其到網(wǎng)格邊界節(jié)點的最短路徑長度升序存儲的，同時將任務(wù)插入空閑工人調(diào)度序列的位置和繞行成本是唯一確定的，因此若支付給該工人的最低報酬超過任務(wù)預(yù)算，則不需要驗證剩余空閑工人的有效性，即通過skip_flag標記(第16-17行).最后，由于空閑工人和非空閑工人的任務(wù)調(diào)度序列不同，因此分別調(diào)用算法2搜索空閑工人的有效調(diào)度(第18-20行)和算法3搜索非空閑工人的有效調(diào)度(第21-22行)，需要注意的是，對于非空閑工人還需要檢查他的容量約束.最后返回有效工人集(第23行).搜索有效調(diào)度的算法是基于插入啟發(fā)式設(shè)計的，本文通過盡早將不滿足約束的插入位置剪枝避免遍歷所有插入位置驗證而產(chǎn)生的無效計算

算法1.搜索有效工人算法

輸入：任務(wù)t，基于路網(wǎng)的網(wǎng)格索引

輸出：有效工人集VW={，…}

1.初始化有效工人集VW={}

2.任務(wù)位于網(wǎng)格gt內(nèi)

3.Foreach待搜索網(wǎng)格gi∈{gt∪NGt}

5. Continue// 剪枝1

6. 按公式(3)計算距離下界lspl(gi，lt)

7. Iflspl(gi，lt)>(dt-att)β

8. Break// 剪枝2

9. skip_flag = 0

10. Foreach待驗證工人w∈Wt

11. IfKw∩Kt==?

12. Continue// 剪枝1

13. 按公式(3)計算距離下界lspl(clw，lt)

14. Iflspl(clw，lt)>(dt-att)β

15. Break// 剪枝2

16. Iflspl(clw，lt)*α>Bt

17. Skip_flag = 1// 剪枝3

18. IfSw==? and(not skip_flag)

19. If not IsDominated(VW，w) // 剪枝4

20.VW=VW∪搜索空閑工人有效調(diào)度(t，w)

21. Else if|Sw|

22.VW=VW∪ 搜索非空閑工人有效調(diào)度(t，w)

23.ReturnVW

搜索空閑工人有效調(diào)度算法如算法2所示.由于空閑調(diào)度序列為空，因此任務(wù)插入其調(diào)度序列的位置是確定唯一的，即將當(dāng)前任務(wù)分配該工人后生成的任務(wù)調(diào)度唯一的.直接調(diào)用最短路徑長度函數(shù)計算工人與任務(wù)之間的實際最短距離，若工人滿足任務(wù)的截止時間和預(yù)算約束(第1-3行)，則返回該工人以及任務(wù)即將插入該任務(wù)序列中的位置0和繞行成本spl(clw，lt)(第4行).

算法2.搜索空閑工人有效調(diào)度算法

輸入：任務(wù)t，空工人w

輸出：有效插入位置及成本

1.spl(clw，lt)=shorestPathLength(clw，lt)

2.Ifspl(clw，lt)≤(dt-att)β

3. Ifspl(clw，lt)≤Bt/α

4. Return

搜索非空閑工人有效調(diào)度算法如算法3所示.和驗證空閑工人不同的是，任務(wù)插入非空閑工人任務(wù)調(diào)度的位置是不確定的，需要依次驗證每個插入位置是否滿足約束并計算對應(yīng)的實際繞行成本，找到實際繞行成本最小的那個插入位置.具體而言，首先初始化最佳插入位置和最小插入成本(第1行)，接著依次驗證每個插入位置的有效性，即若將當(dāng)前任務(wù)t插入Sw中的位置i之后，任務(wù)t的最早期望完成時間超過它的截止時間，則跳出循環(huán)結(jié)束驗證(第4-6行，剪枝5)；按公式(5)計算繞行成本下界，若該下界超過任務(wù)預(yù)算成本約束，則跳過該位置的驗證(第7-9行，剪枝6)；若插入當(dāng)前任務(wù)后，插入位置之后其他任務(wù)的最早期望完成時間超過它的截止完成時間，則跳過該位置的驗證(第10-12行，剪枝7).之后調(diào)用最短路徑長度函數(shù)和繞行成本計算公式得到實際最短距離和繞行成本驗證插入位置的有效性并保存最小插入成本的位置(第13-23行).最后返回有效非空閑工人以及最佳插入位置和最小插入成本(第24-25行).需要注意的是，插入位置i=0的前一個位置是工人的當(dāng)前位置，插入位置i=|Sw|則不需要檢查剩余任務(wù)的期望完成時間是否超過自身的截止時間.

算法3.搜索非空閑工人有效度算法

輸入：任務(wù)t，非空工人w

輸出：有效插入位置及成本

1.ilocbest=-1，icostmin=∞

2.Foreach插入位置i=[0，1，…，|Sw|]

3. flag=1

6. Break// 剪枝5

7. 按公式(5)計算繞行成本下界ld(w，t，i)

8. Ifld(w，t，i)>Bt/α

9. Continue// 剪枝6

10. Foreach插入位置之后的任務(wù)

11. Ifld(w，t，i)/β+exptj>dtj

12. flag=0 and Break // 剪枝7

13. If flag and(not Is Dominated(VW，w，i)) //剪枝8

16. Break

17. 按公式(1)計算實際繞行成本dcost(w，t，i)

18. Ifdcost(w，t)≤Bt/α

19. Foreach插入位置之后的任務(wù)

20. Ifdcost(w，t)/β+exptj>dtj

21. flag=0 and Break

22. If flag anddcost(w，t)

23.ilocbest=i，icostmin=dcost(w，t)

24.Ificostmin<∞

25. Return

最后，分析搜索有效工人算法的時間復(fù)雜度.最壞情況是所有工人都滿足任務(wù)的約束且所有工人的任務(wù)調(diào)度序列長度為|Sw|=cw-1，即需要驗證每個非空閑工人的的每個插入位置的有效性，因此搜索有效工人算法的時間復(fù)雜度是O(|W||C|)，其中|C|表示工人的容量.

4.5 組建工人團隊

通過搜索有效工人算法為任務(wù)搜索到一個有效工人集VW={，…}，該集合中每個元素表示工人w能夠以icost的繞行成本完成該任務(wù)，假設(shè)該工人被選中完成任務(wù)，那么將任務(wù)插入任務(wù)序列sw的iloc位置，并更新插入位置之后的待完成任務(wù)的期望完成時間.

文獻[11]證明了在有效工人集中組建團隊問題是一個NP難問題，因此提出最小成本覆蓋比值貪心算法為當(dāng)前任務(wù)組建團隊.其基本思想是，每次迭代選出icostw/|Kw∩Kt|(繞行成本與工人覆蓋技能的比值，該比值越小表示支付給該工人的報酬越少而工人掌握任務(wù)所需技能越多)最小的工人加入團隊，直到任務(wù)所需技能被全覆蓋或待驗證有效工人集為空.如算法4所示.每次循環(huán)都選出比值最小的工人(第3行)，若將該工人加入團隊的成本不超過任務(wù)的剩余預(yù)算，則將他加入團隊，從待組建工人集(即有效工人集)中刪除，并更新任務(wù)當(dāng)前所需覆蓋的技能以及當(dāng)前預(yù)算，同時將不包含一個或多個任務(wù)當(dāng)前所需覆蓋技能的工人從待組建工人集中刪除(第4-8行).若將該工人加入團隊的成本超過任務(wù)的剩余預(yù)算，則將他從待組建工人集中刪除(第9-10行).最后如果任務(wù)所需技能全部被覆蓋，則返回工人團隊Wt(第11-12行).該算法的時間復(fù)雜度是O(|K||VW|)，其中|K|和|VW|分別表示任務(wù)所需技能集的大小和有效工人集的大小.

算法4.最小成本覆蓋比值組建團隊算法

輸入：一個任務(wù)t，有效工人集VW

輸出：工人團隊Wt

1.初始化工人團隊Wt={}，團隊成本C=0

2.WhileKt≠? andVW≠?

3.w*=argminw∈VWicostw/|Kw∩Kt|

4. Ifα*icostw*≤Bt

5.Wt=Wt∪{w*}，VW=VW-w*

6.Kt=Kt-Kw*，Bt=Bt-α*icostw*

7.RW={w|?w∈VW，|Kw∩Kt|=?}

8.VW=VW-RW

9. Else

10.VW=VW-w*

11.IfKt= =?

12. ReturnWt

5 實驗分析

5.1 實驗數(shù)據(jù)與參數(shù)設(shè)置

通過OpenStreetMap獲取香港路網(wǎng)數(shù)據(jù)，路網(wǎng)由包含32450個頂點和66090條邊的無向圖表示.網(wǎng)格索引中相關(guān)路網(wǎng)信息提前計算并存儲.假設(shè)當(dāng)工人的任務(wù)調(diào)度序列不為空時，工人沿著給定路線行進，否則在原地等待.

本文通過由兩部分組成的合成數(shù)據(jù)集驗證算法的有效性和可擴展性.一部分是Meetup(基于位置的社交應(yīng)用)中的真實事件和用戶的位置、標簽信息.和文獻[11]類似，將Meetup中的事件將視作任務(wù)，將用戶視作工人，他們自帶的標簽作為各自的技能集，并根據(jù)事件的時間先后依次處理每個相關(guān)聯(lián)的任務(wù).本文使用分布在香港(經(jīng)度為113.843～114.283，緯度22.209～22.609)的事件和用戶初始化任務(wù)和工人信息，共計1234個任務(wù)、3275個工人.另一部分是隨機生成的信息，即任務(wù)的位置和工人初始位置隨機映射到路網(wǎng)中的節(jié)點上，而任務(wù)所需技能集大小、發(fā)布時間、最大等待時間(開始時間加上最大等待時間是截止時間)、預(yù)算以及工人的容量屬性都隨機生成.隨機生成的數(shù)據(jù)都服從以默認值為均值的高斯分布.參數(shù)設(shè)置的具體信息如表4所示，其中粗體作為默認值.本文使用表1中參數(shù)來研究算法性能.在每個實驗中，只更改一個參數(shù)并將其它參數(shù)設(shè)置為默認值.評價指標包括運行時間、任務(wù)完成效用，每個衡量指標值是所有任務(wù)的平均值.

表1 實驗參數(shù)Table 1 Experimental parameters

5.2 對比算法

為了評估本文提出的算法，需要使用其他算法作為對比算法.但是本文研究的問題不同于現(xiàn)有工作，即已有算法不能直接應(yīng)用解決本文研究的問題.因此針對本文研究的問題，設(shè)計了兩類對比算法：最大覆蓋技能組建團隊算法和基于歐式距離剪枝策略的搜索算法分別對比本文的算法框架、剪枝策略和組建團隊算法的有效性.

1)最大覆蓋技能組建團隊算法(Maximum Coverage Skill Team Formulation，MCSTF)的基本思想是根據(jù)工人掌握技能數(shù)量貪心迭代地組建團隊，即每輪迭代都從所有工人中選出一個掌握技能與待覆蓋的任務(wù)所需技能交集元素最多的工人，直到待覆蓋的任務(wù)所需技能為空或待驗證工人集為空.

2)改進的最大覆蓋技能組建團隊算法(Improved Maximum Coverage Skill Team Formulation，IMCSTF).由于MCSTF中每輪迭代選擇最佳工人時，不涉及最短路徑長度的計算，因此可以不采用本文提出的先搜索后組建的框架，而是直接組建團隊.具體而言，對于當(dāng)前到達平臺的任務(wù)，每輪迭代都從所有工人中選出一個掌握技能與待覆蓋的任務(wù)所需技能交集元素最多的工人，然后直接計算最短路徑長度驗證該工人的時空有效性同時找到最佳插入位置，若有效則將他添加至工人團隊，否則跳過該工人.直到待覆蓋的任務(wù)所需技能為空或待驗證工人集為空.

3)歐式距離剪枝策略(Euclid Distance Pruning Strategy，EDPS)是將兩點間的歐氏距離作為最短路徑長度下界對待檢查工人進行剪枝.

4)基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法(Group Task Matching and Scheduling based Grid Index Algorithm，GTMSGIA)，即本文提出的算法.其基本思想是對于當(dāng)前到達平臺的任務(wù)通過算法1先搜索有效工人集，然后基于有效工人集組建團隊，每輪迭代在有效工人集中選擇成本覆蓋比值最小的工人，直到任務(wù)所需技能被團隊掌握技能并集覆蓋或待驗證工人集為空.

5.3 實驗結(jié)果和分析

本文通過改變?nèi)蝿?wù)數(shù)量、工人數(shù)量和工人容量分別對比GMTSGIA、IMCSTF、EDPS的運行時間.因為改變搜索驗證有效性的先后關(guān)系或剪枝策略并不影響團隊完成任務(wù)的效用，所以僅對比GMTSGIA、MCSTF的任務(wù)完成效用.

5.3.1 任務(wù)數(shù)量變化對算法的影響

圖3展示了不同任務(wù)數(shù)量下的各算法運行時間，均隨著任務(wù)數(shù)量的增加而上升.這是因為任務(wù)數(shù)量的增加意味著工人的待完成任務(wù)增加，從而導(dǎo)致待驗證的插入位置增加.可以看出本文提出的算法運行時間遠小于其他兩個算法，其中IMCSTF的運行時間比EDPS更少的原因是，前者是選出覆蓋技能元素最多的工人之后再計算最短路徑長度驗證該工人是否有效，而后者需要遍歷所有工人驗證有效性，同時歐式距離只是兩點間最短路徑長度的最小值，因此它的剪枝效果遠遠不如本文提出的剪枝策略.

圖4展示不同任務(wù)數(shù)量下的各算法的任務(wù)完成的平均效用.不論在何種任務(wù)數(shù)量下，本文提出的算法都優(yōu)于MCSTF，而且接近于任務(wù)的預(yù)算均值，這表示工人完成任務(wù)的旅行成本比較小，而MCSTF算法的任務(wù)完成的平均效用僅接近預(yù)算的1/3.

5.3.2 工人數(shù)量變化對算法的影響

圖5展示了不同工人數(shù)量下的各算法運行時間，均隨工人數(shù)量的增加而上升.這是因為工人數(shù)量的增加導(dǎo)致待驗證的工人數(shù)量增加.可以看到EDPS急劇上升，而本文提出的算法一直穩(wěn)定在100ms的左右運行時間.

https：//openstreetmap.org

圖6展示不同工人數(shù)量下的各算法的任務(wù)完成的平均效用.不論在何種工人規(guī)模下，本文提出的算法都優(yōu)于MCSTF.

6 總 結(jié)

本文針對現(xiàn)有研究中任務(wù)調(diào)度問題忽略了群組任務(wù)以及底層的路網(wǎng)信息提出了群組任務(wù)匹配和調(diào)度問題，并提出了基于網(wǎng)格索引的群組任務(wù)匹配和調(diào)度算法框架解決該問題.該框架首先通過網(wǎng)格索引存儲的路網(wǎng)和工人信息快速過濾掉不滿足時間或預(yù)算約束的工人，避免大量無效的最短路徑計算.然后利用基于剪枝策略的搜索算法搜索滿足任務(wù)約束的有效工人集.最后通過組建團隊算法迭代地在有效工人集中選擇最小成本覆蓋比的工人加入團隊完成任務(wù).最后設(shè)計了對比實驗驗證本文提出的解決方案的有效性和高效性.

GTMSGIAIMCSTFEDPS543210運行時間()s1K2K3K4K5K2402.2911.3409.3871.4293.08.0977.1121.1401.1582.0.140.1570.1590.1630.165GTMSGIAMCSTF25201510501K2K3K4K5K效用237.221.235.24239.9103.114.97.81.GTMSGIAIMCSTFEDPS76543210運行時間()s1K3K5K7K9K0059.014.02.023.0234.024.08.1467.2317.3124.0484.2402.3718.GTMSGIAMCSTF3025201510501K3K5K7K9K效用237.221.9228.251.252.91.107.119.153.