摘 要：應急物資的“最后一公里”配送為整個救援行動的末端環(huán)節(jié)，是提高整個救援行動效率的關鍵所在。為了解決細粒度的應急物資配送任務分配問題，提出了一種基于K-means聚類的博弈論任務分配算法，該算法能夠保證所有任務在容忍時間內得到分配的同時最小化工人數(shù)量；然后，設計了一種延遲更新優(yōu)化策略以進一步提升算法的運行效率；最后，在真實數(shù)據(jù)集上進行實驗，結果表明所提算法與隨機任務分配算法、貪心任務分配算法、K-means聚類任務分配算法相比，在工人數(shù)量方面分別減少了38%、28%、10%。結合延遲更新優(yōu)化策略后，算法在最優(yōu)分配結果的基礎上提升了12.5%的運行效率，驗證了所提算法的有效性與實用性。

關鍵詞：空間眾包；應急物資配送；任務分配；博弈論；最小化工人數(shù)量

中圖分類號：TP399 文獻標志碼：A 文章編號：1001-3695（2025）02-023-0494-07

doi： 10.19734/j.issn.1001-3695.2024.06.0200

Spatial crowdsourcing task allocation algorithm for fine-grained

emergency material distribution

Liu Junling^{1， 2}， Wu Qingqing^{1， 2}， Sun Huanliang^{1， 2’}， Xu Jingke^{1， 2， 3}

（1.School of Computer Science amp; Engineering， Shenyang Jianzhu University， Shenyang 110168， China; 2. Liaoning Province Big Data Ma-nagement amp; Analysis Laboratory of Urban Construction， Shenyang 110168， China; 3. Shenyang Branch of National Special Computer Enginee-ring Technology Research Center， Shenyang 110168， China）

Abstract：The last-mile delivery of emergency supplies represents the final phase of the entire rescue operation and is crucial for enhancing the efficiency of the entire rescue effort. To address the fine-grained task allocation of emergency material distribution， this paper proposed a game-theoretic task allocation algorithm based on K-means clustering. This algorithm ensured that all tasks were assigned within a tolerable time while minimizing the number of workers. Then it designed a delay update optimization strategy to further improve the operational efficiency of the algorithm. Finally， conducting experiments on a real dataset， it demonstrates that the proposed algorithm reduces the number of workers by 38%， 28%， and 10% compared to the random task allocation algorithm， the greedy task allocation algorithm， and the K-means clustering task allocation algorithm， respectively. By integrating the delay update optimization strategy， a 12.5% increase in operational efficiency is achieved on top of the optimal allocation result， validating the effectiveness and practicality of the proposed algorithm.

Key words：spatial crowdsourcing; emergency materials distribution; task allocation; game theory; minimizing the number of workers

0 引言

空間眾包是眾包的一個特定研究方向，專注于利用空間眾包平臺將時空任務分配給移動工人，并要求工人在指定地點完成任務?？臻g眾包在數(shù)據(jù)搜集、外賣配送、交通物流、公共安全、災難響應等^[1～3]多個領域展現(xiàn)出廣泛的應用潛力。

災難響應是空間眾包的一個重要應用領域，災難發(fā)生后應急物資的迅速、準確配送對于挽救生命和減輕損失至關重要。特別是在“最后一公里”配送環(huán)節(jié)，這一末端環(huán)節(jié)由于直接關系到受災群眾的即時需求，對應急物資配送的時效性、準確性和靈活性要求極高。然而，在災難情境下物資需求量的激增、配送環(huán)境的不確定性以及時間窗口的嚴格限制^[4]，都極大地增加了任務分配的難度。現(xiàn)有的研究大多利用遺傳算法^[5]、模擬退火算法^[6]等智能優(yōu)化算法求解宏觀層面的整體物資調度問題，即物資從供應點批量配送到受災區(qū)域中心。然而，這些方法并不完全適用于求解更細粒度的物資配送任務分配問題，即物資從受災區(qū)域中心精準配送到受災群眾手中的這一環(huán)節(jié)。特別是在資源有限的情況下，如何有效地選擇最少的工人以按時完成所有物資配送任務，成為了一個亟待解決的重要問題。空間眾包技術通過調度分配分散的人力資源，為解決這一問題提供了新的解決途徑。本文將空間眾包技術引入災難救援領域，提出了面向細粒度應急物資配送的任務分配問題。給定一組物資配送任務和一組候選工人，目標是保證所有任務都能在規(guī)定容忍時間內得到分配的同時最小化工人數(shù)量。該問題可以歸約為集合覆蓋問題^[7]，是典型的NP-hard問題。本文算法將細粒度應急物資配送任務分配問題轉換為一個多工人博弈問題，通過基于聚類的方法進行初始任務分配，并利用最佳響應策略迭代更新工人策略，直至達到純納什均衡，實現(xiàn)工人數(shù)量的最小化。此外，為了提高算法的運行效率，設計了延遲更新優(yōu)化策略，減少不必要的計算。該算法為災難響應中的“最后一公里”物資配送提供一種新的解決方案，旨在提高救援效率和節(jié)約人力資源的同時，實現(xiàn)更快速、更準確的應急物資配送。圖1給出了利用貪心任務分配算法與本文博弈論任務分配算法的具體任務分配實例。在空間區(qū)域內有8個任務與8個工人，其中任務的等級用5種不同顏色標注，紅色、橙色、黃色、綠色、藍色表示等級由高到低（參見電子版）。不同等級的任務容忍時間不同，最小容忍時間為1，最大容忍時間為10。假設所有工人具有相同速度，兩個位置之間距離為歐幾里德距離。圖1（a）是利用貪心任務分配算法實現(xiàn)的分配實例。在保證所有任務都能在容忍時間內完成的情況下，按照任務等級次序貪心地選擇距離最近的工人進行分配，得到分配結果〈w₁， （3，1）， {s₅，s₃}〉， 〈w₄， （2，6）， {s₁}〉， 〈w₅， （5，1）， {s₈}〉， 〈w₇， （6，3）， {s₇，s₄，s₂}〉， 〈w₈， （2，2）， {s₆}〉，選擇工人數(shù)為5。此分配算法沒有從全局角度考慮任務的時空信息以及工人分配任務集合之間的相互關系，因此往往得到的是局部有效解而不是全局的最優(yōu)解。圖1（b）是利用博弈論任務分配算法的分配實例，可以得到最優(yōu)任務分配結果〈w₁， （3，1）， {s₅}〉，〈w₅， （5，1）， {s₇，s₈}〉，〈w₆， （5，6）， {s₁，s₄，s₂}〉，〈w₈， （1，3）， {s₃，s₆}〉，此時選擇的工人數(shù)最少為4。

本文的主要貢獻如下：a）提出了面向細粒度應急物資配送的任務分配問題，該問題旨在保證所有任務在容忍時間內得到分配的同時最小化工人數(shù)量；b）結合博弈論方法和延遲更新優(yōu)化策略，設計一種高效的任務分配算法，實現(xiàn)以最小化工人數(shù)量為目標的任務匹配；c）利用真實數(shù)據(jù)集進行實驗，評估了所提算法的有效性。

1 相關工作

1.1 空間眾包

隨著智能手機的廣泛應用和無線寬帶的普及，一種新型眾包模式應運而生，稱為空間眾包^[8]?？臻g眾包是指將一組具有時空特性的任務分配給一組工人，工人必須在一定的約束條件下親自前往特定的地點執(zhí)行這些任務以獲取一定的報酬獎勵^[3，9]。空間眾包在數(shù)據(jù)搜集、地圖服務、送餐裝修、智能交通、災難響應、城市規(guī)劃等眾多領域都有所應用^[10，11]。

在空間眾包中，任務的發(fā)布模式可以分為工人選擇任務模式^[12，13]和服務器分配任務模式^[14，15]。在工人選擇任務模式下，空間眾包平臺發(fā)布空間任務，工人可以根據(jù)個人偏好、技能和資源在眾包平臺上自主選擇合適的任務來執(zhí)行，無須與服務器協(xié)調，此模式賦予了工人較大的靈活性和選擇權。服務器分配任務模式則由空間眾包平臺根據(jù)收集到的任務和工人時空信息，通過算法自動為工人分配合適的任務，此模式旨在優(yōu)化資源配置，提高任務完成的效率和質量。本文研究的重點是服務器分配任務模式下的空間眾包。

1.2 任務分配

任務分配是空間眾包的一個核心問題，要求在時空約束的條件下將任務分配給合適的工人，同時滿足不同的優(yōu)化目標以實現(xiàn)服務器的最優(yōu)分配^[16，17]。在服務器分配任務模式下，最常見的算法是貪心算法，文獻[18]提出最大任務分配問題，將問題轉換為最大流量問題，對于每批任務貪心地采用Ford-Fulkerson算法求解該問題。文獻[19]基于貪心算法將在線最大加權二部匹配問題的最新算法擴展到在線微任務分配問題，在最大化總收益的同時最小化任務分配的總花費。除了貪心算法外，文獻[20]研究了任務分配中最優(yōu)任務分配問題，利用樹分解技術將工人分割成獨立的集合，并提出一種帶啟發(fā)式的深度優(yōu)先搜索算法，使完成的總任務數(shù)目最大化。文獻[21]研究了基于聯(lián)盟的任務分配問題，通過引入博弈論設計了一種基于均衡的啟發(fā)式算法，在滿足公平性的約束下，實現(xiàn)最大化工人的總獎勵。然而，現(xiàn)有空間眾包研究的優(yōu)化目標大多關注于商業(yè)應用領域的最大化報酬^{[22，23]}和最小化旅行成本^[24，25]，這與本文所提最小化工人數(shù)量這一優(yōu)化目標有所不同，本文的優(yōu)化目標更關注于節(jié)約災難救援中的人力成本，同時保證不同等級任務完成的及時性。文獻[26，27]的研究目標為最小化工人數(shù)量，但并不關注任務的類型與完成的及時性。以上研究與本文所提問題在優(yōu)化目標與約束條件上均有所不同。應用現(xiàn)有算法雖然可以有效解決本文提出的任務分配問題，但并不完全適用，且細粒度應急物資配送任務分配問題更注重的是通過高效的算法得出全局最優(yōu)解，并不是局部的有效解。因此，本文針對提出的面向細粒度應急物資配送的空間眾包任務分配問題設計專門的任務分配算法，保證所有配送任務在容忍時間內得到分配的同時，能夠最小化工人數(shù)量。

1.3 應急物資配送

災難事件的發(fā)生對受災人民的生存和社會的發(fā)展造成嚴重影響，合理有效地調度人力資源進行物資配送在應急工作中顯得尤為重要。當災難發(fā)生時，確保受災人民所需的各種物資能夠在要求時間內送達，對于減少人員傷亡損失具有決定性作用。文獻[28]研究了單受災點、單物資種類的救援物資配送與調度問題，這并不適用于大規(guī)模災難事件救援活動。近年來針對多受災點、多物資種類的救援物資配送與調度得到廣泛關注。文獻[29]在需求量不確定的場景下，提出了應急物資中心選址與配送路徑模型。文獻[30]在考慮災后需求情況不確定的情況下，以配送成本最小化為目標構建了配送模型。盡管以上研究在宏觀層面的救援物資調度取得了一定進展，但這些研究的方法并不完全適用于求解細粒度的應急物資配送任務分配問題。本文將空間眾包技術引入災難救援領域中的應急物資配送，與傳統(tǒng)的物資調度研究不同，本文更側重于細粒度應急物資配送任務的任務分配問題，旨在保證所有物資配送任務能在容忍時間內得到響應的同時，最小化工人數(shù)量。

2 問題定義

定義1 空間任務集^[3]。給定一個空間任務集S，集合中的每個任務s∈S可由四元組s = 〈id， l， r，τ〉表示，其中id為任務編號，l為任務位置，r為任務等級，τ為任務的容忍時間。

本文借鑒文獻[31]中提出的熵權TOPSIS評價方法，基于該評價法得出的量化結果對應急物資配送任務的緊迫性進行了等級劃分。將任務共劃分為5個等級，從高到低分別用數(shù)字1、2、3、4、5表示。任務等級越高表示任務越緊急，不同等級任務的容忍時間不同。從文獻[32]的研究結果可以看出，應急物資需求緊迫度與容忍時間呈反比，即等級越高的任務容忍時間越短。因此，采用增長型的冪函數(shù)來建立任務等級與容忍時間之間的映射關系如式（1）所示。

τ=τ_min+τ_max－τ_min（n－1）^b×（r－1）（1）

其中：r為任務等級；τ_min為最小容忍時間；τ_max為最大容忍時間；n為等級總數(shù)；b為一個正指數(shù)，用來控制容忍時間隨著等級增加的增長速率。

定義2 工人集^[3]。給定一個工人集W，集合中的每個工人w∈W可由三元組w = 〈id， l， v〉表示，其中id為工人編號，l為工人位置，v為工人移動速度。

本文采用文獻[17]提出的無冗余任務分配模式，即服務器只會將一個任務分配給單個工人。假設工人完成一個任務后會立刻前往下一個任務，完成任務本身所需要的時間忽略不計。

定義3 任務分配^[20]。任務分配可由三元組A_w = 〈w， S_w， l〉表示，其中w為選擇的工人，S_wS為分配給工人w的任務集合，l為工人w開始執(zhí)行任務的位置。

本文假設工人以執(zhí)行位置為中心點出發(fā)依次完成任務集合中的任務，一個任務完成返回中心點后再配送下一個任務。

定義4 細粒度應急物資配送任務分配問題。給定空間任務集S和候選工人集W，細粒度應急物資配送任務分配問題的目標是找到一個任務分配集合A使得集合中的工人數(shù)量少，同時滿足以下約束：a）容忍時間約束。每個任務需要在對應的容忍時間內完成。b）完全分配約束。在任務分配集合A中，空間任務集S中的所有任務都能得到分配。c）不變性約束。任務集合一旦被分配就不能改變^[33]。

定理1 細粒度應急物資配送任務分配問題是NP-hard問題。

證明 該定理可以通過集合覆蓋問題的簡化來證明。集合覆蓋問題^[7]可以描述為：給定一個包含n個元素的集合U和一個包含m個元素的子集S，其中每個子集S_i"U。目標是選擇S中的最小子集集合C，使得C中所有子集的并集能夠覆蓋U中的所有元素，并且C中的子集元素兩兩不相交。對于給定的集合覆蓋問題，可以將其轉換為細粒度應急物資配送任務分配問題。給定一個含有n個任務的集合S，其中每個任務可以視為集合U中的一個元素。一個由m個元素構成的子集S′，每個子集S′_i對應于集合S中的一個子集。在這種情況下，每個工人可以看做是子集S′中的一個集合，即每個工人可以完成一組特定的任務。目標是找到子集S′的最小集合C，使得C中所有工人的并集能夠覆蓋所有的任務S，同時每個工人的任務集合不存在重復。根據(jù)這個映射，可以證明變換后的細粒度應急物資配送任務分配問題可解條件為當且僅當集合覆蓋問題可解。由于集合覆蓋問題已知是NP-hard問題，所以提出的細粒度應急物資配送任務分配問題也是NP-hard問題。

表1簡要概述了本文所使用的符號。

3 基于K-means聚類的博弈論任務分配算法

在細粒度的物資配送任務分配過程中每個工人的任務分配集合不僅受到自身位置與移動速度的影響，還與其他工人的任務分配集合相關。即任務分配時需要選出最少的工人，使其能夠在任務容忍時間的約束下，通過共同合作完成所有物資的配送。在這種情況下，每個工人的最優(yōu)決策不僅取決于自身的選擇，還必須考慮其他工人的決策，這種相互依賴的決策關系可以使用博弈論來建模求解。博弈論可以用來分析和解決這種多參與者、多目標的優(yōu)化問題，其中每個參與者在尋求個人效用最大化的同時，考慮到其他工人的策略選擇。本文在現(xiàn)有的博弈論模型基礎上^[34]，針對細粒度應急物資配送任務分配問題，提出了一個基于K-means聚類的博弈論任務分配算法。該算法先使用基于K-means聚類的初始任務分配算法得到初始工人集合以及工人的初始策略，然后迭代地調整工人的任務集合以及工人數(shù)量，直到達到純納什均衡。在純納什均衡分配結果中，工人保留當前分配的任務集合，任何工人都不能通過單方面調整任務集合中的任務來提高自己的效用或者使整體的工人數(shù)量減少，意味著經(jīng)過博弈后的工人數(shù)量最少。

3.1 博弈論建模與純納什均衡

本文將細粒度應急物資配送任務分配問題建模為一個n人戰(zhàn)略博弈G=〈W，ST，U〉，由玩家、策略空間和效用函數(shù)構成，具體如下：

a）W={w₁，…，w_n}（n≥2）是一組作為玩家的工人，在本文的后續(xù)部分，術語玩家表示工人，初始玩家由基于K-means聚類的初始任務分配算法得到。

b）ST={ST_i}ⁿ_i=1是每個玩家w_i的策略集，即每個玩家博弈的策略空間。ST_i表示工人w_i可用的有限策略集，包括所有可能的任務集合和空任務集合1，其中1表示w_i不選擇任何任務的情況。策略博弈Euclid Math OneGAp的聯(lián)合策略st=（st₁，st₂，…，st_n）∈ST，其中st_i∈ST_i為玩家w_i（0 lt; i ≤n）選擇的策略，即任務集合S_w。

c）U=U_iⁿ_i=1表示玩家的效用函數(shù)，U_i=ST→R為玩家w_i的效用函數(shù)，可以定義為對減少工人數(shù)量的貢獻。玩家w_i選擇任務集合S_wi對減少整體工人數(shù)量的貢獻C（w_i，S_wi）可以由式（2）計算。

C（w_i，S_wi）=α×N_i+β×R_i－γ×L_i（2）

其中：α、β、γ分別表示控制貢獻因子N_i、R_i、L_i的權重，且滿足α+β+γ=1。N_i、R_i、L_i可分別由式（3）～（5）計算得出。

N_i=S_wi|S|－∑n－1j≠i，w_j∈WS_wj（3）

其中：N_i表示任務集合S_wi中的任務數(shù)量S_wi在剩余任務集中的占比；|S|是任務集S中的總任務數(shù)。N_i越大表示選擇該任務集合會使剩余的任務數(shù)量越少，越能減少整體工人數(shù)量。

R_i=H（S_wi）H－∑n－1j≠i，w_j∈WH（S_wj）（4）

R_i表示任務集合S_wi中高等級任務的數(shù)量H（S_wi）在剩余高等級任務的占比。其中，H表示任務集S中高等級任務數(shù)。由于容忍時間的限制，越多高等級的任務被執(zhí)行則后續(xù)需要專門選擇執(zhí)行高等級任務的工人越少，即R_i越大表示對減少整體工人數(shù)量的貢獻越大。

L_i=∑S_wij=1，s_j∈S_widis（w_i，s_j）（5）

L_i表示工人w_i按照定義3中假設的任務執(zhí)行方式執(zhí)行完S_wi中所有任務的旅行成本。L_i越小，表示任務集合S_wi中的任務距離越近，越能將更多近距離任務分配給同一個工人，從而減少工人數(shù)量。因此，對于每個聯(lián)合策略st∈ST，U_i（st）∈R表示w_i的效用，可由式（6）計算。

U_i（st）=U_i（st_i，st_-i）=C（w_i，S_wi）（6）

其中：st_i為玩家w_i在聯(lián)合策略ST中的策略；st_-i為除去玩家w_i之外的所有參與者的聯(lián)合策略。

由于每個工人需要有一個確定性策略，即選擇一個任務集合或者都不選擇，所以只需要考慮純策略也就是確定性策略，這意味著工人w_i可以從ST_i中選擇的策略概率為1，而ST_i中剩余策略的概率為0。下面將證明提出的任務分配博弈具有純納什均衡，其中每個玩家都執(zhí)行確定性策略。純納什均衡是博弈的一種狀態(tài)，在這種狀態(tài)下，當其他工人不再改變自己的策略時，沒有一個工人能夠通過改變自己的策略來提高效用。

定理2 細粒度應急物資配送任務分配博弈是一個精確潛勢博弈，且至少有一個純納什均衡。

證明 為了證明定理2，需要證明細粒度應急物資配送任務分配博弈是具有全局勢函數(shù)的精確潛勢博弈，其中所有玩家動機都可以映射到這個勢函數(shù)上。根據(jù)精確潛勢博弈的定義：如果存在函數(shù)F：ST→R，對于所有的策略st∈ST，每個工人w_i∈W都能滿足條件：

U_i（st_i^′，st_-i）－U_i（st_i，st_-i）=F（st_i^′，st_-i）－F（st_i，st_-i） st_i，st^′_i∈ST_i（7）

則策略博弈=〈W，ST，U〉被稱為是一個精確潛勢博弈^[35]。其中st_i^′和st_i是工人w_i可以選擇的策略，st_-i是除工人w_i以外的其他工人的聯(lián)合策略，函數(shù)F是策略博弈的勢函數(shù)。

在細粒度應急物資配送任務分配博弈中，將勢函數(shù)定義為F（st）=∑w_i∈WC（w_i，S_wi），表示所有工人的效用之和，可以得到

F（st_i^′，st_-i）－F（st_i，st_-i）=C（w_i，S^′_wi）+∑w∈W－w_iC（w，S_w）－

C（w_i，S_wi）+∑w∈W－w_iC（w，S_w）=C（w_i，S^′_wi）－C（w_i，S_wi）=

U_i（st_i^′，st_-i）－U_i（st_i，st_-i）（8）

因此，由式（8）可以證明細粒度應急物資配送任務分配博弈是一個精確潛勢博弈，且至少有一個純納什均衡。對于精確潛勢博弈，可以通過最佳響應策略來解決，最終實現(xiàn)純納什均衡。

3.2 帶閾值的最佳響應策略

基于以上的建模與分析，提出一種帶閾值的最佳響應策略，以找到戰(zhàn)略博弈Euclid Math OneGAp的純納什均衡策略，其中每個工人都會分配到其最佳的任務集合，從而減少工人數(shù)量。算法1是基于K-means聚類的博弈論任務分配算法的整體過程，其中詳細介紹了帶閾值的最佳響應策略。在博弈的開始，通過算法2得到的解集A作為博弈玩家和其初始策略（第1～4行）。接著進入博弈迭代的過程，每個玩家根據(jù)其他玩家的策略與剩余任務集生成可執(zhí)行的任務集合，接著找出當前狀態(tài)下的最佳響應任務集合（第7～15行）。若選擇最佳響應策略后的效用值大于等于設定閾值，則更新玩家的策略。若玩家無最佳響應策略或最佳響應策略的效用值小于閾值，則剔除玩家，并且將該玩家的上一輪策略清除（第16～20行）。反復進行迭代過程，直到所有玩家的策略都不再更新自己的策略且沒有待執(zhí)行的任務，達到純納什均衡停止博弈，返回最佳分配結果A（第23、24行）。

算法1 K-means-game task assignment algorithm （KGTA）

輸入：任務集S；已分配工人集AW；未分配工人集UW。

輸出：任務分配A。

1 AW = ?， A= ?， W= KCTA（S，AW，UW）;

2 for each worker w_iSymbolNC@ W do

3

add 〈 w_i ， center ， S_wi 〉 to A;

4 end for

5 t = 1;

6 repeat

7

for each worker w_iSymbolNC@ W do

8 S′ = S;

9 for each worker w_pSymbolNC@ W amp;amp; p lt; i do

10 S′ = S′ – {st_p^t};

11 end for

12 for each worker w_qSymbolNC@ W amp;amp; q gt; i do

13 S′ = S′ - {st_q^t-1};

14 end for

15 find the best-response S_wi from S′ for w_i;

16 if U_i（st）≥ η then

17 st_i = S_wi ;

18 else" U_i（st）lt; η|| S_wi == 1

19 W._st^t-1 = W._st^t-1 - st_i;

20 W=W- w_i;

21

end for

22

t = t + 1;

23 until W._st^t = W._st^t–1 and S′ is empty

24 return A

3.2.1 基于K-means聚類的初始任務分配算法

由于分布在空間中的任務具有聚集現(xiàn)象，所以借鑒文獻[1，36]中對任務聚類的思想，提出基于K-means聚類的初始任務分配算法。該算法根據(jù)任務的等級以及容忍時間選取最小的k值對任務進行聚類，在任務分配過程中不斷選擇距離聚類中心最近的工人，直到所有的任務都能在容忍時間內得到分配。算法2為該算法的主要過程。首先對所有的任務進行等級劃分，接著依次對每個等級的任務進行初始K-means聚類，得到k個聚類中心（第2～4行）。對于每個等級的任務，優(yōu)先從已分配工人中尋找可執(zhí)行工人，將任務加入該工人的任務集合并且從任務集中移除（第6～12行）。對于該等級的剩余任務，選擇距離聚類中心最近的k個工人到聚類中心進行任務匹配，將任務分配的結果加入A中（第13～21行）。該等級的所有任務都被執(zhí)行完成后，進行下一等級任務的分配。最終返回任務分配結果A。

算法2 K-means cluster task assignment algorithm （KCTA）

輸入：任務集S；已分配工人集AW；未分配工人集UW。

輸出：任務分配A。

3.2.2 延遲更新優(yōu)化策略

由于在博弈的過程中，無論其他工人的策略是否發(fā)生變化，每個工人在每一輪迭代中都需要重新計算最佳響應策略，這在求解大規(guī)模問題時速度較慢。所以采用文獻[37]中的延遲更新思想設計了延遲更新優(yōu)化策略（lazy update optimization strategy， LUO）來提高算法的運行效率。該策略不會改變算法的結果，只會減少算法的運行時間，減少不必要的計算。延遲更新優(yōu)化策略意味著只在其他工人的最佳響應策略可能發(fā)生變化時才重新計算工人的最佳響應策略。具體來說，只有在以下兩種情況出現(xiàn)時，才需要重新計算工人的最佳響應策略：a）當有工人被剔除時，上一輪博弈中該工人的任務集合被重新放回剩余任務集中，其他工人需要根據(jù)當前剩余任務集中的任務進行博弈，此時需要計算其他工人的最佳響應策略。具體來說，對于工人w_i，如果他被剔除博弈，則上一輪分配給w_i的任務集合st_i將被重新放回剩余任務集S′中，即S′ = S′ + st_i。根據(jù)式（2）可知，博弈玩家中的其他工人w_j一定可以找到一個能夠增加其貢獻的新任務集合，即C（w_j，S^′_wj）gt;C（w_j，S_wj），其中S^′_wj是工人w_i上一輪策略st_i中的任意一個任務加入S_wj后的一個任務集合，那么工人w_j一定有動機改變其最佳響應策略。

b）當其他工人策略中分配的任務集合發(fā)生變化時，即有新的任務被放回剩余任務集S′中或剩余任務集S′中有任務被加入到其他工人的任務集合中。此時，工人被其他任務所吸引，要改變當前任務集合中的任務，則需要重新計算工人的最佳響應策略，該情況的具體說明與情況a）類似。

因此，只需要在以上兩種情況可能發(fā)生時才需要重新計算工人的最佳響應策略。通過該策略可以減少算法1中第15行的計算次數(shù)，提升算法的運行效率。

4 實驗評價

4.1 數(shù)據(jù)集及參數(shù)設置

本文實驗的數(shù)據(jù)集來自于2022年第十九屆中國研究生數(shù)學建模競賽F題（https：//cpipc.acge.org.cn/），問題的背景為大規(guī)模疫情爆發(fā)期間采用封閉式管理方式的情況下居民生活物資發(fā)放問題，該問題的目標是在全面提高疫情防控效率的同時，努力節(jié)約相關部門的人員投入與經(jīng)費支出。這與本文研究的細粒度應急物資配送任務分配問題在目標和背景上具有高度一致性。該問題的數(shù)據(jù)集涵蓋了長春市在COVID-19疫情期間的1 409個小區(qū)基本信息。本文從原始數(shù)據(jù)集中隨機抽取1 000個作為任務數(shù)據(jù)集，工人數(shù)結合任務數(shù)隨機上下浮動獲得。實驗運行在配備Intel^?Core^TMi7-7820X CPU@3.60 GHz和64 GB的機器上，采用的編程語言為Java。實驗中任務參數(shù)設置來源于真實數(shù)據(jù)集，其等級參數(shù)設置根據(jù)真實災難事件發(fā)生后各等級數(shù)量的特點采用泊松分布原理隨機生成，各任務等級的容忍時間通過式（1）計算得出，其中最大和最小容忍時間是根據(jù)疫情期間收集到的真實歷史數(shù)據(jù)進行分析所設定。實驗中工人參數(shù)設置來自于合成數(shù)據(jù)集，其移動速度的設定考慮了任務集的真實地理距離范圍以及任務的容忍時間要求，以確保合成數(shù)據(jù)的真實性和實驗結果的準確性。表2、3展示了實驗的參數(shù)設置，其中所有參數(shù)的默認值加粗表示。

針對所提出的面向細粒度應急物資配送任務分配問題，結合現(xiàn)有算法設計實現(xiàn)了三個基準算法，分別為隨機任務分配算法、貪心任務分配算法、K-means聚類任務分配算法。將以上算法與所提出的基于K-means聚類的博弈論任務分配算法、結合延遲更新優(yōu)化策略的博弈論算法進行比較，比較度量為工人數(shù)量和運行時間。具體的算法如下：

4.2 實驗結果

本節(jié)測試各參數(shù)對實驗結果的影響，通過每次改變一個參數(shù)，其他參數(shù)設置為默認值來進行對比實驗。

4.2.1 任務數(shù)對算法性能的影響

圖2給出了五種算法在不同任務數(shù)下工人數(shù)量和運行時間的變化情況。從圖2（a）可以看出，隨著任務數(shù)量的不斷增加，工人數(shù)量也隨之增加。原因是更多的任務要執(zhí)行意味著需要更多的工人來完成，從而導致工人增加。其中，KGTA的工人數(shù)量最少，較RTA、GTA、KCTA相比，人數(shù)分別減少了38%、28%、10%?？紤]到運行時間，可以從圖2（b）看出，RTA和GTA的運行時間最短，其他三種算法的運行時間隨著任務數(shù)量的增加而增加。這是因為這三種算法均需要通過不斷地迭代來選擇出最少的工人數(shù)量，這一過程需要消耗更多時間，但KGTA + LUO僅在比Random算法多耗時450 ms的情況下，取得了優(yōu)于RGT和GTA38%、28%的分配結果，驗證了所提出博弈論算法及延遲更新優(yōu)化策略的有效性。

4.2.2 候選工人數(shù)對算法性能的影響

圖3給出了不同的候選工人數(shù)對五種算法性能的影響。從圖3（a）可以看出，隨著候選工人數(shù)量的增加，除RTA外其余四種算法工人數(shù)量都在平穩(wěn)下降。原因是候選工人越多，算法可以選擇出更合適的工人去執(zhí)行任務，從而減少工人數(shù)量。而RTA選擇的工人數(shù)量穩(wěn)定，是因為該算法隨機選擇工人，具有不確定性，所以候選工人數(shù)增大對結果影響不大。圖3（b）所示為不同工人數(shù)量下運行時間的變化情況，可以看出，除了RTA和GTA外，其他三種算法運行時間都明顯增加。這是由于候選工人的數(shù)量增加，算法為了選擇出更合適的工人要進行更多計算，從而運行時間也越來越長。尤其是KGTA，工人越多，需要博弈的玩家越多，為了尋找到純納什均衡，需要進行多輪迭代才能得到最優(yōu)的分配結果。但KGTA + LUO在KGTA的最優(yōu)結果上節(jié)省了12.5%的運行時間。盡管如此，五種算法都能在2 s內響應所有任務請求。

4.2.3 容忍時間對算法性能的影響

圖4給出了不同容忍時間對五種算法性能的影響。從圖4（a）可以看出，KCTA、KGTA、KGTA + LUO的工人數(shù)量隨著容忍時間增加而減少，當容忍時間從0.5 h開始增加時，三種算法的減少趨勢變得緩慢。這是由于工人的移動速度不變，盡管容忍時間增大，但是工人可選擇的任務仍然有限，導致工人數(shù)量減少的效果并不明顯。在圖4（b）中，KCTA、KGTA、KGTA+ LUO的運行時間明顯減少，原因是容忍時間增加，工人數(shù)量減少，算法需要迭代的次數(shù)減少，運行時間隨之減少。RTA和GTA的運行時間基本保持不變。

4.2.4 工人移動速度范圍對算法性能的影響

圖5給出了工人的移動速度在6～15變化時，五種算法的工人數(shù)量和運行時間的變化情況。圖5（a）顯示了當移動速度越來越大時，五種算法工人數(shù)量越來越少。原因是移動速度越大，容忍時間不變的情況下每個工人可以執(zhí)行的任務數(shù)量越來越多，算法可以有更多滿足要求的工人，從而工人數(shù)量也越來越小。圖5（b）顯示了不同移動速度下運行時間的變化，可以得出移動速度越大運行時間越短，工人移動速度變化對KCTA、KGTA和KGTA + LUO的影響較大，對RTA、GTA的影響較小。

4.2.5 聚類個數(shù)對算法性能的影響

圖6給出不同聚類個數(shù)k對KCTA、KGTA、KGTA + LUO性能的影響。從圖6可以看出，當k為50時，三種算法的工人數(shù)量與運行時間最短。其中，KGTA + LUO在與KCTA運行時間相近的情況下，取得了優(yōu)于KCTA10%的分配結果，驗證了LUO策略的有效性。

上述五組實驗結果表明，盡管傳統(tǒng)算法能夠求解出有效的任務分配結果，但在工人數(shù)量以及運行時間方面，本文提出的任務分配算法具有更好的分配結果。此外，在結合延遲更新優(yōu)化策略后，算法不僅保持了最優(yōu)的任務分配結果，并且在此基礎上減少了12.5%的運行時間，驗證了所提算法在性能和效率方面的顯著優(yōu)勢。

5 結束語

本文針對災難救援領域中的細粒度應急物資配送任務分配問題提出了一種空間眾包任務分配解決方案，旨在保證所有任務在容忍時間內得到分配的同時最小化工人數(shù)量。提出了一種基于K-means聚類的博弈論任務分配算法，并且設計了一種延遲更新優(yōu)化策略以減少最佳相應策略的計算次數(shù)。在真實數(shù)據(jù)上進行詳細的實驗結果表明，所提出算法與隨機分配算法、貪心算法、K-means聚類算法相比，在減少工人數(shù)量方面分別減少了38%、28%、10%。結合延遲更新優(yōu)化策略后，算法在最優(yōu)結果的基礎上減少12.5%的運行時間，驗證了所提出算法的有效性。本文的研究為實現(xiàn)快速、精確的物資配送任務分配提供了一種切實可行的方法，有效節(jié)省了最優(yōu)任務分配的人力成本，同時確保救援行動的及時性。本文方法不局限于特定的災難救援場景，可適用于其他需要快速、高效資源分配的緊急響應領域。未來的研究將專注于提升任務分配算法的性能，并且計劃引入深度學習技術以預測救援任務和工人，實現(xiàn)更加準確高效的在線任務分配，使算法能夠適應各種災難響應場景。

參考文獻：

[1]Lin Xiaochuan， Wei Kaimin， Li Zhetao，et al. Aggregation-based dual heterogeneous task allocation in spatial crowdsourcing [J]. Frontiers of Computer Science， 2024， 18 （6）： 186605.

[2]Guo Bin， Liu Yan， Wang Leye，et al. Task allocation in spatial crowdsourcing： current state and future directions [J]. IEEE Internet of Things Journal， 2018， 5 （3）： 1749-1764.

[3]Tong Yongxin， Zhou Zimu， Zeng Yuxiang， et al. Spatial crowdsour-cing： a survey [J]. The VLDB Journal， 2020， 29： 217-250.

[4]王妍妍， 孫佰清. 模糊信息下多種類應急物資多周期分配優(yōu)化模型 [J]. 中國管理科學， 2020， 28 （3）： 40-51. （Wang Yanyan， Sun Baiqing. Multi-period optimization model of multi-type emergency materials allocation based on fuzzy information [J]. Chinese Journal of Management Science， 2020， 28 （3）： 40-51.）

[5]呂偉， 李志紅， 馬亞萍， 等. 考慮受災點需求時間窗的應急物資配送車輛路徑規(guī)劃研究 [J]. 中國安全生產(chǎn)科學技術， 2020， 16 （3）： 5-11. （Lyu Wei， Li Zhihong， Ma Yaping， et al. Research on route planning of emergency materials distribution vehicles conside-ring time window of requirements by disaster point [J]. Journal of Safety Science and Technology， 2020， 16 （3）： 5-11.）

[6]周磊， 李前鵬， 李法朝. 考慮時間滿意度的應急物資儲備庫選址模型與算法 [J]. 中國安全科學學報， 2023， 33 （3）： 188-194. （Zhou Lei， Li Qianpeng， Li Fachao. Location model and algorithm of emergency material storage considering time satisfaction [J]. China Safety Science Journal， 2023， 33 （3）： 188-194.）

[7]孫菲， 賀毅朝， 張寒崧， 等. 基于新穎二進制人工蜂群算法求解帶權集合覆蓋問題 [J]. 計算機應用研究， 2024，41（9）： 2722-2731. （Sun Fei， He Yichao， Zhang Hansong， et al. Novel binary artificial bee colony algorithm for solving weighted set covering problem [J]. Application Research of Computers， 2024，41（9）： 2722-2731.）

[8]Zhao Yongjian， Han Qi. Spatial crowdsourcing： current state and future directions [J]. IEEE Communications Magazine， 2016， 54 （7）： 102-107.

[9]倪志偉， 劉浩， 朱旭輝， 等. 基于深度強化學習的空間眾包任務分配策略 [J]. 模式識別與人工智能， 2021， 34 （3）： 191-205. （Ni Zhiwei， Liu Hao， Zhu Xuhui， et al. Task allocation strategy of spatial crowdsourcing based on deep reinforcement learning [J]. Pattern Recognition and Artificial Intelligence， 2021， 34 （3）： 191-205.）

[10]Alamri S. The geospatial crowd： emerging trends and challenges in crowdsourced spatial analytics [J]. ISPRS International Journal of GeoInformation， 2024， 13（6）： 168.

[11]毛鶯池， 穆超， 包威， 等. 空間眾包中多類型任務的分配與調度方法 [J]. 計算機應用， 2018， 38 （1）： 6-12. （Mao Yingchi， Mu Chao， Bao Wei， et al. Multi-type task assignment and scheduling oriented to spatial crowdsourcing [J].Journal of Computer Application， 2018， 38 （1）： 6-12.）

[12]Deng Dingxiong ， Shahabi C， Demiryurek U. IMaximizing the number of worker’s self-selected tasks in spatial crowdsourcing [C]// Proc of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM Press， 2013： 324 - 333.

[13]Deng Dingxiong ， Shahabi C， Demiryurek U， et al. Task selection in spatial crowd-sourcing from worker’s perspective [J]. GeoInformatica， 2016， 20： 529-568.

[14]Zhao Yan， Liu Jiaxin， Li Yunchuan，et al. Preference-aware group task assignment in spatial crowdsourcing： effectiveness and efficiency [J]. IEEE Trans on Knowledge and Data Engineering， 2023， 35 （10）： 10722-10734.

[15]Zhong Xiaolong， Miao Hao， Qiu Dazhuo，et al. Personalized location-preference learning for federated task assignment in spatial crowdsourcing [C]// Proc of the 32nd ACM International Conference on Information and Knowledge Management. New York： ACM Press， 2023： 3534-3543.

[16]Chen Zhao， Cheng Peng， Chen Lei，et al. Fair task assignment in spatial crowdsourcing [J]. Proceedings of the VLDB Endowment， 2020， 13 （12）： 2479 - 2492 .

[17]Li Yunchuan， Zhao Yan， Zheng Kai. Preference-aware group task assignment in spatial crowdsourcing： a mutual information-based approach [C]// Proc of IEEE International Conference on Data Mining. Piscataway， NJ： IEEE Press， 2021： 350-359.

[18]Kazemi L， Shahabi C. GeoCrowd： enabling query answering with spatial crowdsourcing [C]// Proc of the 20th International Confe-rence on Advances in Geographic Information Systems. New York：ACM Press， 2012： 189-198.

[19]Tong Yongxin， She Jieying， Ding Bolin，et al. Online mobile micro-task allocation in spatial crowdsourcing [C]// Proc of the 32nd International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2016： 49-60.

[20]李洋， 賈夢迪， 楊文彥， 等. 基于樹分解的空間眾包最優(yōu)任務分配算法 [J]. 軟件學報， 2018， 29 （3）： 824-838. （Li Yang， Jia Mengdi， Yang Wenyan， et al. Optimal task assignment algorithm based on tree-decouple in spatial crowdsourcing [J]. Journal of Software， 2018， 29 （3）： 824-838.）

[21]Zhao Yan， Zheng Kai， Wang Ziwei，et al. Coalition-based task assignment with priority-aware fairness in spatial crowd-sourcing [J]. The VLDB Journal， 2024， 33 （1）： 163-184.

[22]Zhao Yan， Lai Tinghao， Wang Ziwei，et al. Worker-churn-based task assignment with context-LSTM in spatial crowdsourcing [J]. IEEE Trans on Knowledge and Data Engineering， 2023， 35 （9）： 9783-9796.

[23]Zhou Yunjun， Wan Shuhan， Zhang Detian，et al. Skilled task assignment with extra budget in spatial crowdsourcing [C]// Proc of International Conference on Advanced Data Mining and Applications. Cham： Springer， 2023： 520-535.

[24]He Peicong， Xin Yang， Hou Bochuan，et al. PKGS： a privacy-preserving hitchhiking task assignment scheme for spatial crowdsour-cing [J]. Electronics， 2023， 12 （15）： 3318.

[25]Peng Peng， Ni Zhiwei， Zhu Xuhui，et al. Application of clustering cooperative differential privacy in spatial crowdsourcing task allocation [J]. Journal of Intelligent amp; Fuzzy Systems， 2023， 45 （4）： 1064-1246.

[26]Zeng Yuxiang， Tong Yongxin， Chen Lei，et al. Latency-oriented task completion via spatial crowdsourcing [C]// Proc of the 34th International Confe-rence on Data Engineering. Piscataway， NJ： IEEE Press， 2018： 317-328.

[27]Guo Bin， Liu Yan， Wu Wenle，et al. ActiveCrowd： a framework for optimized multitask allocation in mobile crowdsensing systems [J] IEEE Trans on Human-Machine Systems， 2016， 47 （3）： 392-403.

[28]何建敏， 劉春林. 限制期條件下應急車輛調度問題的模糊優(yōu)化方法 [J]. 控制與決策， 2001，16（3）： 318-321. （He Jianmin， Liu Chunlin. Fuzzy programming problem for vehicle dispatch under time restriction [J]. Control and Decision， 2001， 16（3）： 318-321.）

[29]彭大江， 葉春明， 萬孟然. 基于模糊需求的應急物資中心選址—路徑問題的算法研究 [J]. 計算機應用研究， 2022， 39 （12）： 3631-3638. （Peng Dajiang， Ye Chunming， Wan Mengran. Research on algorithm for emergency resource center location-routing problem based on fuzzy demand [J]. Application Research of Computers， 2022， 39 （12）： 3631-3638.）

[30]張樹柱， 朱玉林， 王洪峰， 等. 震后初期考慮不確定性的兩階段救援物資選址與配送問題 [J/OL]. 控制工程. （2024-02-29） [2024-08-01]. https：//doiorg/10. 14107/j. cnki. kzgc. 20230026. （Zhang Shuzhu， Zhu Yulin， Wang Hongfeng， et al. Two-phase location and distribution of relief supplies considering uncertainty in the early post-earthquake period [J/OL]. Control Engineering. （2024-02-29） [2024-08-01]. https：//doi. org/10. 14107/j. cnki. kzgc. 20230026.）

[31]楊帆. 自然災害下考慮需求分級的跨區(qū)域應急物資調度優(yōu)化研究 [D]. 秦皇島： 燕山大學， 2023. （Yang Fan. Study on optimization of cross-regional emergency materials dispatch considering demand classification under natural disasters [D]. Qinhuangdao： Yanshan University， 2023.）

[32]楊倩， 王飛躍， 盧佳節(jié)， 等. 基于需求緊迫度的約束性應急物資車輛路徑模型 [J]. 清華大學學報： 自然科學版， 2024， 64 （6）： 1082-1088. （Yang Qian， Wang Feiyue， Lu Jiajie， et al. Constrained vehicle routing model for emergency relief supplies based on demand urgency [J]. Journal of Tsinghua University： Science and Technology， 2024， 64 （6）： 1082-1088.）

[33]錢勤紅， 劉安， 孫玉娥. 面向路網(wǎng)的空間眾包群組任務匹配和調度算法 [J]. 小型微型計算機系統(tǒng)， 2022， 43 （3）： 490-407. （Qian Qinhong， Liu An， Sun Yu’e. Group task matching and scheduling algorithm in spatial crowdsourcing for road network [J]. Journal of Chinese Computer Systems， 2022， 43 （3）： 490-407.）

[34]Nisan N， Roughgarden T， Tardos E，et al. Algorithmic game theory [M]. [S.l.]：Cambridge University Press， 2007.

[35]Monderer D， Shapley L S. Potential games [J]. Games and Economic Behavior， 1996， 14 （1）： 124-143.

[36]Ma Yue， Gao Xiaofeng， Bhatti S S，et al. Clustering based priority queue algorithm for spatial task assignment in crowdsourcing [J]. IEEE Trans on Services Computing， 2024， 17（2）： 452-465.

[37]Cheng Peng， Chen Lei， Ye Jieping. Cooperation-aware task assignment in spatial crowdsourcing [C]// Proc of the 35th International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2019： 1442-1453.