空間眾包下面向任務需求的在線三類分配策略

陳天一，高麗萍

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引言

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

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

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

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

1 問題定義

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

定義2：眾包任務定義為t=＜lt，at，et，it，Pt＞，其中lt表示任務位置，at表示任務發布時間，et表示任務等待時間，it表示任務所需物品，Pt={p1，p2，...，pn}表示滿足所需物品的地點并按其與任務的距離進行升序排列的集合。工作者必須前往相應的配送點p∈Pt領取物品并交付于請求者以完成任務。

定義3：配送地點定義為p=＜lp，Sp＞，其中lp表示地點位置，表示所提供物品類型。配送地點的位置與供應信息都提前已知并存儲在眾包平臺中。為了簡化問題，本文假設每個地點包含兩種物品類型。

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

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

定義6：面向任務需求的在線三類分配問題定義，給定一組工作者集合W，一組任務集合T以及一組地點集合P，任務與工作者會在隨機時間內動態出現在眾包平臺上，目標函數如式（1）所示。

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

2 基于貪心的延時匹配算法

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

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

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

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

算法在每個時刻會通過式（2）動態調整閾值大小，從而提高算法分配效果。

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

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

復雜性分析：算法在每個時刻運行一次，需要同時遍歷任務集合、配送點集合和工作者集合，因此算法時間復雜度是O(|T| × |P| × |W|)。同時，算法需要分別存儲任務和配送地點、配送地點與工作者之間的距離以及優化集合中的匹配對，空間復雜度是O(|T| × |P|+|P| × |W|)。

3 實驗分析

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

3.1 實驗設置

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

Table 1 Parameter setting of simulation dataset表1 模擬數據集參數設置

3.2 實驗結果

在TDMG 中改變參數δ 對實驗結果的影響如圖1所示。

Fig.1 Experimental results of varying the parameter δ圖1 改變參數δ的實驗結果

可以看出，在分配成本方面，隨著參數δ 的取值不斷增加，任務分配的平均成本逐漸下降，然后趨于穩定。這是因為當δ 增加時，會擴大TDMG 的搜索空間并獲取到更多匹配對，從而得到更好的匹配結果。平均成本在［0.1，0.4］區間內下降幅度非常大，在［0.4，1］區間內趨于平緩并逐漸穩定下來。同時，在運行時間方面，由于搜索空間不斷增大，算法運行時間不斷攀升，且隨著參數的增長上升幅度愈發明顯。這是由于隨著δ 的增加，需要計算更多的匹配對，從而需要消耗更多時間。兼顧分配成本和運行時間，實驗中將δ設置為0.4。

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

Fig.2 Experiment results of varying the number of T，W and P圖2 改變任務、工作者與配送地點三者數量的實驗結果

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

Fig.3 Experiment results of varying the waiting time of T圖3 改變任務等待時間的實驗結果

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

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

Fig.4 Experiment results of DiDi dataset圖4 滴滴出行數據集下的實驗結果

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

5 結語

本文提出了面向任務需求的在線分配問題，在動態場景下為每個任務分配合適的配送點和工作者，使得平均分配成本最小化。為了解決這一問題，本文考慮利用任務等待期間出現的工作者尋找更優的匹配結果，并通過閾值約束設置提高任務分配效率。最后，本文通過在模擬數據集和真實數據集上的大量實驗驗證了所提方法在提升分配效果上的可行性和有效性。在未來工作中，將進一步考慮工作者在接受多個任務時的路線規劃問題，為工作者提供合理的執行方案以提高配送效率。