陳天一，高麗萍

（上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

近年來，空間眾包下任務(wù)分配問題［1-2］受到越來越多研究者關(guān)注，即在滿足約束條件的前提下為任務(wù)分配合適的工作者。隨著互聯(lián)網(wǎng)的快速發(fā)展和移動(dòng)智能設(shè)備的普及，空間眾包應(yīng)用日漸成熟，給人們的生活帶來了極大便利。例如，美團(tuán)外賣、餓了么等平臺(tái)能夠提供美食、藥品等多種商品類型，用戶可以根據(jù)自身意愿選擇對(duì)應(yīng)的配送門店購(gòu)買所需物品。然而，大多數(shù)用戶在購(gòu)買商品時(shí)，為節(jié)約送達(dá)時(shí)間往往會(huì)傾向于選擇距離較近的配送點(diǎn)，因此會(huì)存在指定地點(diǎn)附近工作者較少的情況，導(dǎo)致平臺(tái)不得不從更遠(yuǎn)的地方派遣工作者執(zhí)行該任務(wù)，反而延長(zhǎng)了交付時(shí)間。

目前，大多數(shù)研究［3-10］主要考慮了任務(wù)和工作者兩類對(duì)象，其目標(biāo)是在滿足任務(wù)和工作者約束的前提下通過一對(duì)一或一對(duì)多的匹配模式分配任務(wù)。Cheng 等［11］提出通過協(xié)調(diào)不同平臺(tái)之間的工作者資源實(shí)現(xiàn)動(dòng)態(tài)任務(wù)分配以最大化平臺(tái)總收入。Liu 等［12］設(shè)計(jì)通過歷史數(shù)據(jù)學(xué)習(xí)接近最佳閾值的Greedy-OT 算法以最大化分配數(shù)量。Chen等［13］研究如何降低分配中最長(zhǎng)等待時(shí)間以提高用戶滿意度，并假設(shè)任務(wù)會(huì)一直等待工作者到來，考慮任務(wù)具有截止期限。Qian 等［14］提出一種多臂賭博機(jī)與批處理相結(jié)合的自適應(yīng)算法，以最小化任務(wù)的平均等待時(shí)間。Miao等［15］考慮存在不可靠工作者，進(jìn)而提出一種評(píng)估任務(wù)質(zhì)量的概率模型和描述工作者行為的搭便車模型。但是，這些研究都沒有考慮配送地點(diǎn)選取對(duì)任務(wù)分配的影響。

Song 等［16］首次提出了基于三類對(duì)象的在線匹配問題，證明此問題的離線版本是NP-hard，并設(shè)計(jì)一種自適應(yīng)隨機(jī)閾值算法以最大化分配總效用。Li 等［17］提出一種3 類穩(wěn)定匹配問題，以最大限度地增加穩(wěn)定匹配的數(shù)量。Pan等［18］指出文獻(xiàn)［16］忽略了任務(wù)和工作者之間的距離成本和公平性，通過自動(dòng)協(xié)商的分配方式提高平均匹配質(zhì)量和總效用。Zheng 等［19］考慮任務(wù)不同需求類型，研究如何根據(jù)任務(wù)需求分配合適的配送地點(diǎn)和工作者，并為工作者規(guī)劃合適的配送路線使總效用最大化。已有研究［20-23］提出根據(jù)任務(wù)或工作者的歷史數(shù)據(jù)預(yù)測(cè)未來分布或質(zhì)量進(jìn)行任務(wù)分配以滿足不同的優(yōu)化目標(biāo)。但上述研究都忽略了用戶需求和移動(dòng)成本對(duì)任務(wù)分配的影響。

本文考慮到任務(wù)需求多樣性和配送地點(diǎn)選擇主觀性，以最小化分配成本為目標(biāo)，根據(jù)任務(wù)需求為請(qǐng)求者尋找合適的配送點(diǎn)與工作者，提出一種基于貪心的延時(shí)匹配算法（TDMG），利用任務(wù)的等待時(shí)間以獲得更好的分配結(jié)果，同時(shí)通過約束設(shè)置快速篩選匹配對(duì)以加快分配效率。最后，在模擬數(shù)據(jù)集與真實(shí)數(shù)據(jù)集上對(duì)所提出的算法進(jìn)行不同參數(shù)下的性能比較分析，實(shí)驗(yàn)結(jié)果證明了本文所提出的方法具有可行性和有效性。

1 問題定義

定義1：眾包工作者定義為w=＜lw，aw，vw＞，其中l(wèi)w表示工作者位置，aw表示工作者上線時(shí)間，vw表示工作者移動(dòng)速度。為簡(jiǎn)化問題，本文假設(shè)所有工作者的移動(dòng)速度均為1，因此分配成本可視作為工作者的移動(dòng)距離。

定義2：眾包任務(wù)定義為t=＜lt，at，et，it，Pt＞，其中l(wèi)t表示任務(wù)位置，at表示任務(wù)發(fā)布時(shí)間，et表示任務(wù)等待時(shí)間，it表示任務(wù)所需物品，Pt={p1，p2，...，pn}表示滿足所需物品的地點(diǎn)并按其與任務(wù)的距離進(jìn)行升序排列的集合。工作者必須前往相應(yīng)的配送點(diǎn)p∈Pt領(lǐng)取物品并交付于請(qǐng)求者以完成任務(wù)。

定義3：配送地點(diǎn)定義為p=＜lp，Sp＞，其中l(wèi)p表示地點(diǎn)位置，表示所提供物品類型。配送地點(diǎn)的位置與供應(yīng)信息都提前已知并存儲(chǔ)在眾包平臺(tái)中。為了簡(jiǎn)化問題，本文假設(shè)每個(gè)地點(diǎn)包含兩種物品類型。

定義4：匹配對(duì)定義為(w，p，t)，表示工作者w移動(dòng)至配送點(diǎn)lp領(lǐng)取物品，然后前往任務(wù)所在位置lt進(jìn)行交付以完成任務(wù)。

定義5：分配成本定義為Cost(w，p，t)=d(w，p) +d(p，t)，其中d(.，.)表示任意兩點(diǎn)之間的歐式距離。

定義6：面向任務(wù)需求的在線三類分配問題定義，給定一組工作者集合W，一組任務(wù)集合T以及一組地點(diǎn)集合P，任務(wù)與工作者會(huì)在隨機(jī)時(shí)間內(nèi)動(dòng)態(tài)出現(xiàn)在眾包平臺(tái)上，目標(biāo)函數(shù)如式（1）所示。

其目的是在W、T、P中找到匹配集合M，使得任務(wù)分配平均成本最小化，其中|M|=表示平臺(tái)中任務(wù)分配的總數(shù)量。如果任務(wù)匹配成功，則I(w，p，t)=1，反之匹配未成功，則I(w，p，t)=0。同時(shí)，滿足以下約束條件：①任務(wù)在分配時(shí)必須選擇滿足其所需物品的配送地點(diǎn)，即it?Sp；②工作者和任務(wù)上線后才可以進(jìn)行分配，任務(wù)超過等待時(shí)間將會(huì)在平臺(tái)上消失；③每一個(gè)工作者最多只能分配一個(gè)任務(wù)，任務(wù)被分配后一定會(huì)完成。

2 基于貪心的延時(shí)匹配算法

Tong 等［24］對(duì)在線最小匹配的代表性算法進(jìn)行全面的實(shí)驗(yàn)比較，實(shí)驗(yàn)表明貪心算法比其他算法有更好的效果，但是貪心算法無法保證未來不會(huì)出現(xiàn)比當(dāng)前更好的分配結(jié)果。本文考慮到在任務(wù)等待期間內(nèi)陸續(xù)可能會(huì)出現(xiàn)新的工作者加入平臺(tái)，如果任務(wù)與新的工作者匹配比與當(dāng)前在線工作者匹配有更好的效果，則可以將原先被任務(wù)占用的工作者釋放并將新的工作者分配給任務(wù)，從而可以有效地降低任務(wù)分配的平均成本。

貪心算法會(huì)為每個(gè)任務(wù)計(jì)算所有可能的匹配對(duì)，能夠有效找到當(dāng)前最優(yōu)結(jié)果，但是算法運(yùn)行效率較低。如果當(dāng)前任務(wù)與地點(diǎn)之間的距離d(t，p)不小于當(dāng)前最小成本Costmin，則組合工作者形成的匹配結(jié)果Cost(w，p，t)必然大于Costmin。因此，通過參數(shù)δ 對(duì)遍歷范圍進(jìn)行約束，主要作用是過濾距離較遠(yuǎn)的配送地點(diǎn)和分配成本較大的匹配對(duì)，以提高算法運(yùn)行效率。同時(shí)，δ 的大小會(huì)影響算法性能，如果δ 較小，運(yùn)行效率會(huì)提高，但是可能會(huì)過濾掉一些優(yōu)質(zhì)的匹配對(duì)導(dǎo)致分配成本上升。反之δ 較大，可以有效降低分配成本，但是會(huì)產(chǎn)生大量不必要的計(jì)算導(dǎo)致運(yùn)行效率降低，因此通過多次實(shí)驗(yàn)測(cè)試，將δ設(shè)置為0.4。

具體執(zhí)行過程如算法1 所示。算法在每個(gè)時(shí)刻運(yùn)行一次，首先更新任務(wù)集合和工作者集合（第1 行），通過算法2 檢查并處理優(yōu)化集合中每個(gè)匹配對(duì)的狀態(tài)（第2 行）。然后對(duì)于每個(gè)任務(wù)，遍歷地點(diǎn)集合，若任務(wù)與地點(diǎn)之間的距離不小于δ*當(dāng)前最小成本，則跳過本次循環(huán)以減小搜索空間（第3-6 行）；然后遍歷工作者集合，貪婪地尋找分配成本最小的匹配對(duì)并將其存放在優(yōu)化集合中，同時(shí)移除已完成匹配的工作者和任務(wù)，并更新閾值γ的大小（第7-15行）。最后輸出匹配集合M（第16行）。

在每個(gè)時(shí)刻，算法2 會(huì)為集合內(nèi)每個(gè)匹配對(duì)中的任務(wù)尋找更合適的工作者，但是這會(huì)導(dǎo)致更多的時(shí)間支出。為了減少遍歷集合所需時(shí)間，通過閾值γ判斷匹配對(duì)的狀態(tài)。如果匹配對(duì)的成本大于γ，任務(wù)會(huì)繼續(xù)留在集合中并等待更合適的工作者；反之如果分配成本不大于γ，則立刻輸出匹配對(duì)并加入匹配集合。研究發(fā)現(xiàn)，合適的閾值約束可以有效地減小集合的計(jì)算時(shí)間，防止一些表現(xiàn)很好的匹配對(duì)繼續(xù)留在集合中，降低運(yùn)行效率并浪費(fèi)用戶的時(shí)間。算法具體執(zhí)行過程為：

算法在每個(gè)時(shí)刻會(huì)通過式（2）動(dòng)態(tài)調(diào)整閾值大小，從而提高算法分配效果。

其中，Costcur表示當(dāng)前時(shí)刻下已分配任務(wù)的平均成本，Costavg表示匹配集合M 中任務(wù)分配的總平均成本。θ是調(diào)整系數(shù)，設(shè)置大小為0.1。當(dāng)Costcur≥Costavg，說明當(dāng)前時(shí)刻下的分配效果比總體的分配效果差，反之則說明當(dāng)前時(shí)刻下的分配效果比總體的分配效果好。

算法會(huì)在每個(gè)時(shí)刻檢查每個(gè)匹配對(duì)的狀態(tài)，如果當(dāng)前時(shí)間小于任務(wù)的截止時(shí)間且分配結(jié)果大于閾值γ，則遍歷滿足任務(wù)需求的每一個(gè)配送地點(diǎn)，若任務(wù)與地點(diǎn)之間的距離不小于δ*當(dāng)前最小花費(fèi)，則跳過本次循環(huán)以加快運(yùn)行速度（第1-5 行）；對(duì)于這些地點(diǎn)，遍歷工作者集合，若存在更優(yōu)的工作者wnew，則將新的工作者wnew和地點(diǎn)pnew與任務(wù)構(gòu)成匹配并替換當(dāng)前集合中的匹配對(duì)，并將原先被任務(wù)占用的工作者釋放并重新放回工作者集合（第6-11 行）；如果當(dāng)前時(shí)刻已經(jīng)到達(dá)匹配對(duì)中任務(wù)的截止時(shí)間或分配結(jié)果不大于閾值γ，則將匹配對(duì)從集合中移除并加入匹配集合M（第12-14行）。

復(fù)雜性分析：算法在每個(gè)時(shí)刻運(yùn)行一次，需要同時(shí)遍歷任務(wù)集合、配送點(diǎn)集合和工作者集合，因此算法時(shí)間復(fù)雜度是O(|T| × |P| × |W|)。同時(shí)，算法需要分別存儲(chǔ)任務(wù)和配送地點(diǎn)、配送地點(diǎn)與工作者之間的距離以及優(yōu)化集合中的匹配對(duì)，空間復(fù)雜度是O(|T| × |P|+|P| × |W|)。

3 實(shí)驗(yàn)分析

通過在不同參數(shù)分布的模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，從輸入?yún)?shù)δ、三者數(shù)量和任務(wù)等待時(shí)間分別研究不同算法對(duì)分配效果和運(yùn)行效率的影響，以驗(yàn)證所提出算法在分配花費(fèi)和運(yùn)行時(shí)間上的可行性和有效性。實(shí)驗(yàn)比較算法如下：①在線隨機(jī)算法（Random），即隨機(jī)選擇工作者并分配合適的配送地點(diǎn)使得分配成本最?。虎诘攸c(diǎn)就近分配算法（LNP），即選擇距離最近的配送點(diǎn)并分配離配送點(diǎn)最近的工作者；③貪心算法（Greedy），即選擇合適的配送點(diǎn)和工作者使得分配成本最小，即minCost(w，p，t)；自適應(yīng)閾值算法（Adaptive-RT），即根據(jù)文獻(xiàn)［16］中所提出的策略，動(dòng)態(tài)調(diào)整使用不同閾值的概率并選擇滿足閾值約束的匹配對(duì)；④離線算法（Offline），即在所有工作者和任務(wù)信息提前已知的前提下，根據(jù)貪心策略進(jìn)行分配，使得分配結(jié)果接近最優(yōu)解。

3.1 實(shí)驗(yàn)設(shè)置

首先通過在不同參數(shù)選取的模擬數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，相關(guān)參數(shù)如表1 所示（默認(rèn)設(shè)置已加粗表示）。真實(shí)數(shù)據(jù)集使用滴滴平臺(tái)于2016 年11 月成都市采集的訂單數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分別將訂單起始和訂單結(jié)束信息視作為任務(wù)和工作者信息，并隨機(jī)抽取不同數(shù)量的任務(wù)和工作者進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境在macOS 系統(tǒng)下運(yùn)行，編譯平臺(tái)為PyCharm，CPU 為2.6GHz Core i7，內(nèi)存為16g。為避免偶然性，所有實(shí)驗(yàn)數(shù)據(jù)均是取10次運(yùn)行結(jié)果的平均值。

Table 1 Parameter setting of simulation dataset表1 模擬數(shù)據(jù)集參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果

在TDMG 中改變參數(shù)δ 對(duì)實(shí)驗(yàn)結(jié)果的影響如圖1所示。

Fig.1 Experimental results of varying the parameter δ圖1 改變參數(shù)δ的實(shí)驗(yàn)結(jié)果

可以看出，在分配成本方面，隨著參數(shù)δ 的取值不斷增加，任務(wù)分配的平均成本逐漸下降，然后趨于穩(wěn)定。這是因?yàn)楫?dāng)δ 增加時(shí)，會(huì)擴(kuò)大TDMG 的搜索空間并獲取到更多匹配對(duì)，從而得到更好的匹配結(jié)果。平均成本在［0.1，0.4］區(qū)間內(nèi)下降幅度非常大，在［0.4，1］區(qū)間內(nèi)趨于平緩并逐漸穩(wěn)定下來。同時(shí)，在運(yùn)行時(shí)間方面，由于搜索空間不斷增大，算法運(yùn)行時(shí)間不斷攀升，且隨著參數(shù)的增長(zhǎng)上升幅度愈發(fā)明顯。這是由于隨著δ 的增加，需要計(jì)算更多的匹配對(duì)，從而需要消耗更多時(shí)間。兼顧分配成本和運(yùn)行時(shí)間，實(shí)驗(yàn)中將δ設(shè)置為0.4。

圖2 展示了任務(wù)、工作者與配送地點(diǎn)三者在不同數(shù)量下對(duì)實(shí)驗(yàn)結(jié)果的影響。在分配成本方面，隨著時(shí)間段內(nèi)三者數(shù)量的不斷增多，所有算法的平均成本也隨之減小。隨著數(shù)量的增加，有更多可用的工作者，算法可以匹配更多任務(wù)并優(yōu)化每個(gè)任務(wù)的分配結(jié)果。其中，TDMG 的分配效果最接近Offline 的離線結(jié)果并遠(yuǎn)優(yōu)于其他在線分配算法，其次是Adaptive-RT、Greedy、LNP、Random。同時(shí)，隨著分配數(shù)量的增多，TDMG 的優(yōu)化效果越明顯。這是由于TDMG 可以利用每個(gè)任務(wù)的等待時(shí)間獲得更多工作者，并組成更多表現(xiàn)良好的匹配對(duì)。在運(yùn)行時(shí)間方面，隨著數(shù)量的增加，均逐漸增長(zhǎng)。其中，Random 的運(yùn)行時(shí)間最短，其次是LNP、Greedy、TDMG、Adaptive-RT。由于在每次迭代中TDMG 需要同時(shí)考慮現(xiàn)在和將來的可用工作者以尋找更好的匹配對(duì)，因此分配時(shí)間略高于其他3種算法。

Fig.2 Experiment results of varying the number of T，W and P圖2 改變?nèi)蝿?wù)、工作者與配送地點(diǎn)三者數(shù)量的實(shí)驗(yàn)結(jié)果

圖3 展示了任務(wù)等待時(shí)間逐漸增加對(duì)實(shí)驗(yàn)結(jié)果的影響。在分配成本方面，隨著任務(wù)等待時(shí)間的增加，算法平均成本均逐漸降低，這是由于更長(zhǎng)的等待時(shí)間可以獲得更多表現(xiàn)良好的匹配對(duì)。其中，TDMG 最接近Offline 離線結(jié)果并優(yōu)于其他在線分配算法，其次是Adaptive-RT、Greedy、LNP、Random。同時(shí)，TDMG 算法的平均成本降低幅度明顯，而其他3 種算法降低非常緩慢。這是由于任務(wù)等待時(shí)間的延長(zhǎng)導(dǎo)致TDMG 可以在任務(wù)等待期間內(nèi)尋找更多工作者并組成更好的匹配對(duì)，從而使得分配效果更好。算法運(yùn)行時(shí)間均逐漸增長(zhǎng)，Random 的運(yùn)行時(shí)間最短，其次是LNP 和Greedy，3 種算法表現(xiàn)都很穩(wěn)定，沒有較大波動(dòng)趨勢(shì)，再次是TDMG 和Adaptive-RT。TDMG 一開始低于Greedy，隨著任務(wù)等待時(shí)間的增加而不斷增長(zhǎng)，逐漸高于其他3 種算法。這是由于任務(wù)等待時(shí)間增加會(huì)導(dǎo)致等待隊(duì)列中的匹配對(duì)數(shù)量變多，遍歷時(shí)間也會(huì)逐漸增加。而通過設(shè)置約束減小搜索空間，使得運(yùn)行時(shí)間增速放緩，因此在運(yùn)行效率上仍然足夠高效，滿足實(shí)時(shí)性需求。

Fig.3 Experiment results of varying the waiting time of T圖3 改變?nèi)蝿?wù)等待時(shí)間的實(shí)驗(yàn)結(jié)果

圖4 展示了在滴滴數(shù)據(jù)集下任務(wù)、工作者與地點(diǎn)在不同分配數(shù)量和等待時(shí)間變化下的實(shí)驗(yàn)結(jié)果。隨著三者數(shù)量的不斷增多，在分配成本方面，所有算法均逐漸減小。Random 算法表現(xiàn)最差，其次是LNP、Greedy、Adaptive-RT，TDMG 在表現(xiàn)上始終優(yōu)于其他4 種在線算法并最接近Offline 的離線結(jié)果。在運(yùn)行時(shí)間方面，Random 算法用時(shí)最短，其次是LNP、Greedy、TDMG、Adaptive-RT。

隨著等待時(shí)間的增加，可以觀察到TDMG 的表現(xiàn)最接近Offline 的離線結(jié)果，其次是Adaptive-RT、Greedy、LNP、Random。同時(shí)，TDMG 分配效果隨著時(shí)間的增加下降幅度明顯，其他算法沒有較為明顯的變化。在運(yùn)行時(shí)間方面，TDMG 用時(shí)增加明顯，其他算法較為緩慢。Adaptive-RT 用時(shí)相對(duì)TDMG 較長(zhǎng)，其次是Greedy、LNP、Random。

Fig.4 Experiment results of DiDi dataset圖4 滴滴出行數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果

通過在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上對(duì)算法的分配成本和效率進(jìn)行實(shí)驗(yàn)，TDMG 始終得到比Random、LNP、Greedy 和Adaptive-RT 更好的分配效果且最接近Offline 的離線結(jié)果，這也說明在任務(wù)分配過程中將當(dāng)前在線工作者和任務(wù)等待時(shí)間段內(nèi)出現(xiàn)的工作者一并加入考慮可以有效地提高分配效果。在運(yùn)行時(shí)間方面，Adaptive-RT 最高，TDMG 比Random、LNP、Greedy 需要更多的處理時(shí)間，但在運(yùn)行效率上仍然足夠高效，滿足實(shí)時(shí)性需求。

5 結(jié)語

本文提出了面向任務(wù)需求的在線分配問題，在動(dòng)態(tài)場(chǎng)景下為每個(gè)任務(wù)分配合適的配送點(diǎn)和工作者，使得平均分配成本最小化。為了解決這一問題，本文考慮利用任務(wù)等待期間出現(xiàn)的工作者尋找更優(yōu)的匹配結(jié)果，并通過閾值約束設(shè)置提高任務(wù)分配效率。最后，本文通過在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)驗(yàn)證了所提方法在提升分配效果上的可行性和有效性。在未來工作中，將進(jìn)一步考慮工作者在接受多個(gè)任務(wù)時(shí)的路線規(guī)劃問題，為工作者提供合理的執(zhí)行方案以提高配送效率。