朱 菲，劉 安，孫玉娥，李 姝

1(蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006)

2(蘇州大學 軌道交通學院，江蘇 蘇州 215137)

3(沈陽理工大學 裝備工程學院，沈陽 110159)

E-mail：anliu@suda.edu.cn

1 引 言

隨著移動互聯(lián)網(wǎng)的發(fā)展和基于GPS的智能設備的普及，空間眾包逐漸吸引了來自工業(yè)界和學術界的廣泛關注.近年來，基于空間眾包的應用快速發(fā)展，越來越多的人可以在眾包平臺發(fā)布帶有空間屬性的任務，平臺指派合適的工人前往指定地點完成任務.如在滴滴打車中，用戶向平臺上傳自己所在的具體位置，被分配到該訂單的司機需要到達該位置接到乘客，載乘客移動到目的地后獲得報酬.

在已有的關于空間眾包的工作中，綜述[1]對空間眾包的研究現(xiàn)狀與未來發(fā)展進行了總結，任務分配被認為是該領域的核心問題之一.以往解決任務分配問題的工作大都是對任務和工人兩類對象進行匹配，根據(jù)任務屬性從空閑工人池中挑選符合條件(如技能、可信度等)的工人，通知其前往用戶指定的地點執(zhí)行任務.在這一過程中，工人需要前往完成任務的地址由用戶決定，平臺并不參與.但這一假設并不總是成立，例如在美容美發(fā)類O2O應用南瓜車中，平臺需要為工人和用戶指定合適的任務場所.

受到這一啟發(fā)，我們發(fā)現(xiàn)在很多空間眾包場景中，任務地點可以很大程度上影響原有的任務-工人兩類對象任務的效果.以空間眾包中經(jīng)典的打車場景為例，在圖1中有一個用戶u1和兩個網(wǎng)約車司機w1、w2.如果任務點就設為用戶所在的位置坐標，考慮到在路網(wǎng)下w1到u1的距離小于w2，傳統(tǒng)匹配算法通知w1前往u1的位置接送乘客.然而，如果平臺可以建議用戶移動到附近的旗標處p1，那么w2到上車點的路網(wǎng)距離將大大減少.改變上車點后，平臺會將該訂單分配給路網(wǎng)距離更短的w2而非需要繞路的w1，用戶也能更快坐上車開始行程.

圖1 打車場景中的任務點選址示例圖Fig.1 Example of task location in taxi scenario

基于這種發(fā)現(xiàn)，我們首次提出了面向路網(wǎng)的空間眾包三維匹配任務選址問題.通過在用戶允許范圍內(nèi)調整任務地點，能最大化地節(jié)約工人們的旅行成本，在宏觀角度上減少碳排放.同時，為了避免因刻意追求減少旅行成本而選擇距離較遠的不合適的工人，我們不僅選擇任務點，還挑選合適的工人，保證在工人旅行成本減小的同時，工人到任務點的距離也盡可能減小，從而減少用戶的等待時間.顯然，該工作可以應用在許多空間眾包場景(如外賣配送)，這也證實了我們所提出的問題具有廣泛的現(xiàn)實意義.同時需要說明的是，目前沒有相關工作與本文問題的優(yōu)化目標一致，且涉及到工作地點的分配工作都是基于歐式距離展開研究，所以現(xiàn)有算法不能直接解決本文問題.

為了解決本文所提出的任務點選址問題，我們首先將原問題規(guī)約到最大三維匹配問題，證明其在多項式時間內(nèi)不能被找到最優(yōu)解.由于在將原問題建模到三分圖結構的過程中，我們需要對路網(wǎng)空間中的所有用戶、工人和任務點兩兩進行檢查，確認是否滿足給定約束.由于待驗證的對象數(shù)量往往很龐大且實際滿足限制的對象是少量的，所以遍歷浪費算力和時間.并且，對于每一個用戶-任務點-工人組合，我們都要計算工人節(jié)約的旅行成本和最終移動距離，每一次計算都包括多次路網(wǎng)下的最短路徑查詢.顯然，如果使用樸素解法，這一過程的用時在現(xiàn)實場景中是不可接受的.因此我們提出了篩選可用匹配對的優(yōu)化算法，通過空間索引快速查找指定范圍內(nèi)的對象，并優(yōu)化多點對間的最短路徑查詢，對大量重復計算的最短路徑進行提取復用.然后，本文對任務點容量充足/不足的情況進行分析，并證明了前者可用二分圖完美匹配的Kuhn and Munkres算法(下文簡稱KM)解決，針對后者提出了分塊貪心算法.本文的具體工作如下：

1)首次提出了空間眾包中的路網(wǎng)環(huán)境下的三維匹配任務點選址問題.該問題通過調整任務點并根據(jù)調整后的任務點選擇工人，旨在最大化節(jié)約的工人的旅行成本并使用戶的等待時間盡可能小.

2)通過對該問題進行規(guī)約，我們證明其具有NP難度.本文首先提出了篩選可用匹配對和多點對最短路徑查詢優(yōu)化算法，并在此基礎上將原問題的不同情況分別建模到二分圖和三分圖上，最終給出貪心解法.

3)為了評估本文算法的性能，本文在真實數(shù)據(jù)集上進行了實驗，證明了所提出算法在效用和時空開銷方面都有很好的表現(xiàn).

本文的其余內(nèi)容組織如下：第2部分討論與本文相關的已有工作；第3部分介紹問題定義并證明其復雜度；第4部分提出解決方案；第5部分給出實驗結果并進行分析；第6部分總結全文.

2 相關工作

本章首先介紹了空間眾包中任務分配領域的經(jīng)典工作，然后特別討論了3類對象匹配中與本文相關的工作，并進行了區(qū)分.

2.1 任務分配

綜述[1]將現(xiàn)有的空間眾包研究歸納為4個方向：任務分配、質量控制、激勵機制和隱私保護，其中任務分配一般被劃分為匹配問題和調度問題.

作為被公認為空間眾包領域的核心問題，大部分任務分配都是對任務和工人2類對象進行匹配，旨在在滿足平臺和用戶約束的前提下實現(xiàn)不同的優(yōu)化目標.文獻[2]考慮任務數(shù)相對于工人數(shù)非常稀缺的情況并提出了一種公平的分配方式.考慮到不同類型的任務，如多人合作和有技能需求，學術界也涌現(xiàn)了一批優(yōu)秀工作.文獻[3]針對需要多人合作的任務提出了能夠最大化合作效用的分配方式.文獻[4]提出了多技能導向的任務分配問題，并給出了多種有效算法.同時，由于空間眾包的任務分配過程中通常涉及到一些敏感信息，如坐標位置和任務報價等，隱私保護技術也被應用在大量的任務分配工作中.文獻[5]實現(xiàn)了在滿足社會利益最大化的同時保護隱私的任務分配.

與上述兩類對象匹配不同，本文考慮任務點對于分配效果的影響.由于現(xiàn)實中存在很多需要平臺確定任務地址的場景，所以我們的想法更加全面與新穎.

2.2 3類對象匹配

近年來，有少數(shù)任務匹配工作也將任務點作為需要匹配的第3類對象.從匹配問題的優(yōu)化目標上看，工作[6]最大化完成的任務-工人匹配對的效用，而文獻[7]最大化穩(wěn)定匹配數(shù).文獻[8]中，平臺為每個騎手規(guī)劃路線，包括購買某件物品的具體位置，使得物品質量、工人評分和獎賞綜合效用最高.但是他們并不考慮任務地點改變對工人旅行成本產(chǎn)生的影響，而本文以此任務點選址的首要目標，因此這些工作并不完全適用于我們的問題.并且相比工作[6]直接將容量為n的對象拆分成n個容量為1的對象建模并統(tǒng)一進行三維匹配，我們分情況討論并規(guī)約到二分圖匹配和三維匹配問題，能適應更多場景.

3 問題定義和復雜度

本章先給出形式化的問題定義，然后給出本文問題的復雜性分析.

3.1 問題定義

首先介紹4個基本概念，然后給出可用三維匹配的定義及其效用的計算方式，最后定義路網(wǎng)環(huán)境下的空間眾包三維匹配任務點選址問題.

定義1.(路網(wǎng))路網(wǎng)定義為一張有向帶權圖G=.結點集合V中的每個結點v表示實際路網(wǎng)中的一個位置點，由其經(jīng)緯度坐標唯一確定；邊集合E中的每條邊e=(vi，vj)表示在路網(wǎng)上從位置vi前往位置vj的最短路徑，邊權集合W中的每個權重d(e)表示經(jīng)過邊e所代表的最短路徑的旅行成本.為了簡便起見，本文用最短路徑e=(vi，vj)的移動距離d(vi，vj)作為旅行成本.本文所提出的方法可以輕松地擴展到旅行成本為時間的場景中，因為在工人或用戶移動速度已知時，距離和時間很容易進行相互轉換.

定義2.(用戶)一個用戶定義為u=，表示用戶在路網(wǎng)上的位置點為lu，他/她愿意移動的地理范圍是以lu為圓心，ru為半徑的區(qū)域.

定義3.(工人)一個工人定義為w=，表示工人在路網(wǎng)上的位置點為lw，他/她愿意前往執(zhí)行任務的位置必須在以lw為圓心，rw為半徑的區(qū)域內(nèi).以打車應用為例，當上車點到工人當前所在位置lw的距離超過rw時，司機w就會拒絕接受該訂單.

定義4.(任務點)一個任務點定義為p=，表示任務點在路網(wǎng)上的位置為lp，并且能夠容納的在該點執(zhí)行任務的最大工人數(shù)(即容量)為正整數(shù)cp.以打車場景為例，如果較多的車輛都在同一地點等待乘客，很可能會造成交通堵塞，因此為任務點設置容量屬性非常合理且貼近現(xiàn)實.

定義5.(可用三維匹配)一個用戶-任務點-工人三維匹配(u，p，w)可用，當且僅當它滿足下列約束：

1)任務點p在用戶u愿意接受的移動范圍內(nèi)，即d(lu，lp)≤ru；

2)任務點p在工人w愿意接受訂單的地理范圍內(nèi)，即d(lw，lp)≤rw；

3)相比工人w需要移動到用戶所在位置lu的路網(wǎng)距離d(lw，lu)，他/她到任務點p的路網(wǎng)旅行成本d(lw，lp)更短，即dt(u，p，w)=d(lw，lu)-d(lw，lp)>0.

定義6.(面向路網(wǎng)的空間眾包三維匹配任務選址問題)給定路網(wǎng)G中的用戶集合U={u1，…，um}，工人集合W={w1，…，wn}和任務點集合P={p1，…，pk}，本問題的求解目標是找到U，W，P的一個可用三維匹配集合M?U×P×W使得該集合的總效用最大化，即Maximizeμ(M)=∑(u，p，w)∈Mμ(u，p，w)，且滿足以下約束：

1)可用性約束：集合M中的每個三維匹配都是可用的，即都滿足定義5中的所有約束.

2)唯一性約束：每個用戶u在M中至多出現(xiàn)一次，每個工人w在M中至多出現(xiàn)一次；

3)容量約束：每個任務點p在M中至多出現(xiàn)cp次.

3.2 問題復雜性

定理1.面向路網(wǎng)的空間眾包三維匹配任務點選址問題具有NP難度.

證明：考慮原問題的一種特殊情況：在歐式空間中，提交了訂單的用戶數(shù)、工人數(shù)和任務地點數(shù)相等，每個任務點的容量都為1，每個可用三維匹配對中工人節(jié)約的旅行距離和最終移動距離相等.此時，該問題等價于三維匹配問題的優(yōu)化問題，而三維匹配問題的決策問題已經(jīng)被證明是NP完全問題[6].

另外，本文問題的難度遠超上述的特例，無論是路網(wǎng)中的距離計算更為復雜，還是需要考慮到容量等其他約束.因此，面向路網(wǎng)的空間眾包三維匹配任務點選址問題也至少是NP難度的.

4 解決方案

本章首先給出解決本文面向路網(wǎng)的空間眾包三維匹配任務點選址算法(下文簡稱路網(wǎng)下的任務點選址算法)框架；隨后依次介紹框架中基于篩選可用匹配對和多點對間最短路徑距離的優(yōu)化算法；最后，對上車點容量不同的情況進行分析，證明了上車點充足時的原問題可用二分圖中的KM算法[9]解決，并給出了解決上車點不足場景下的原問題的分塊貪心算法.

4.1 路網(wǎng)下的任務點選址算法框架

在本文問題中，在給定路網(wǎng)環(huán)境下，平臺掌握著在原地等待服務的m個用戶，n個空閑工人和k個適合作為任務場所(如司機等待乘客)的任務點的相關信息.目標是為每個訂單請求指定一個任務點和分配一個工人，使其能與發(fā)起訂單的用戶構成一個可用三維匹配對，最終能最大化平臺上所有可用三維匹配對的效用之和.值得注意的是如定義5中所示，每個可用三維匹配對的效用越大，說明該訂單所指派工人能節(jié)約的旅行成本越大，同時他/她最終移動到任務點的旅行成本越小，即用戶等待工人的越短，這顯然是考慮到工人和用戶雙方利益的.

為解決該問題，一種最直觀的思想是遍歷所有的用戶-任務點-工人，一一檢查是否能滿足限制.找到所有的可用三維匹配對后，逐一計算它們的效用值.之后嘗試組合已有的可用三維匹配對，構造出所有滿足定義6中約束的集合，最終比較得出最優(yōu)解M.然而在現(xiàn)實應用中，在篩選可用匹配對時，需要計算用戶-任務點和工人-任務點之間的距離判斷是否滿足空間約束.顯然這一過程是極其耗時的，因此我們加入了篩選可用匹配對優(yōu)化算法(算法2)，通過建立空間索引進行加速.同時在計算每個可用匹配對的效用時，需要計算其中的工人-任務點和工人-用戶的最短路徑距離.同樣地，我們基于精度換速度的思想，提出了多點對間的最短路徑長度計算優(yōu)化算法(算法3)，大大加快了點對之間的距離計算.最后，由于對可觀數(shù)量的可用三維匹配對進行組合后暴力查找最優(yōu)解的解空間是很龐大的，所以我們對上車點容量充足和不足的情況做了分析，對于前者我們使用KM算法(算法4)進行求解，對于后者我們在已有的三維匹配貪心算法上進行了分塊優(yōu)化并求解(算法5).

算法1.路網(wǎng)下的任務點選址算法框架

輸入：道路網(wǎng)絡圖G，用戶集U，工人集W，任務點集P

輸出：可用三維匹配集合M

1.篩選可用三維匹配對(U，P，W)//算法2

2.Foreach可用三維匹配對(u，p，w)

3. 計算μ(u，p，w)//算法3

4.Ifmax(cp)≥|U|

5. KM算法求得最優(yōu)匹配M//算法4

6.Else

7. 分塊貪心算法求得最優(yōu)匹配M//算法5

8.根據(jù)匹配M通知相應的工人和用戶前往任務點

本文所提出的路網(wǎng)下任務點選址算法框架的偽代碼如算法1所示.

4.2 篩選可用三維匹配對優(yōu)化算法

如引言部分所述，平臺上提交訂單的用戶數(shù)，等待分配的工人數(shù)和有剩余容量的任務點數(shù)都是非常龐大的，然而它們能組成的可用三維匹配對數(shù)卻是較小的.鑒于此，首先分析樸素遍歷找到可用匹配對方法的復雜度，之后提出一種優(yōu)化算法，利用Rtree結構快速篩選可用的三維匹配對.

首先介紹樸素遍歷尋找可用三維匹配對的方法，并分析其復雜度.如圖2所示，平臺上有用戶集合U={u1，…，um}，工人集合W={w1，…，wn}和任務點集合P={p1，…，pk}.對每個用戶ui，要對p∈{p1，…，pk}逐一進行檢查：如果d(lui，lp)≥rui，則該用戶愿意前往該任務點(圖2中用實線表示)；否則，用戶ui不能和任務p在同一個可用三維匹配對中(圖2中用虛線表示).遍歷得到ui愿意前往的所有任務點集合P(ui)后，對其中的每個任務點p，繼續(xù)對每個空閑工人w∈{w1，…，wn}進行遍歷：如果d(lw，lp)≥rw，則該工人愿意移動到該任務點工作(圖2中用實線表示)；否則，工人w不能和任務點p在同一個可用三維匹配對中(圖2中用虛線表示).如此，經(jīng)過先后對任務點集合和工人集合的遍歷，我們找到了所有包含用戶ui的可用三維匹配對.因此，用樸素遍歷算法找到本文問題中所有用戶的可用匹配對的時間復雜度為O(m×k×n)，這在現(xiàn)實場景中顯然是不可接受的.

圖2 三維匹配問題示例圖Fig.2 Example of 3-dimensional matching

本文利用Rtree中能快速搜索指定空間范圍內(nèi)的點的特性，提出一種篩選可用匹配對優(yōu)化算法.基本思想是根據(jù)所有任務點的位置建立一棵Rtree，再對每個工人搜索其工作范圍內(nèi)的任務點，并為任務點添加愿意前往該地址的工人標簽.然后對每個用戶在Rtree中快速搜索他/她活動范圍內(nèi)的任務點，并根據(jù)這些任務點的工人標簽直接構建該用戶的可用三維匹配對.

偽代碼如算法2所示.輸入為路網(wǎng)G下的用戶集合U、工人集合W和任務點集合P，輸出為所有可用三維匹配對組成的集合M′.在執(zhí)行過程中，首先為所有任務點所在的區(qū)域建立RTree空間索引(第1行)，然后對每個任務點p，初始化愿意移動到lp完成任務的工人標簽為空集(第2-第3行).隨后，對每個工人w在Rtree中搜索他/她愿意活動的區(qū)域內(nèi)的所有任務點P(w)，并在這些任務點的工人標簽中添加w(第4-第7行).接下來，對提交任務請求的每個用戶u，在Rtree中搜索他/她愿意前往的所有任務點P(u)(第8-第10行)，并檢索每個可達任務點p∈P(u)的工人標簽p.workers，然后依次將標簽內(nèi)的工人w∈p.workers、任務點p和用戶u組成可用三維匹配對(u，p，w)(第11-第13行).

算法2.篩選可用三維匹配對優(yōu)化算法

輸入：道路網(wǎng)絡圖G，用戶集U，工人集W，任務點集P

輸出：可用三維匹配對集合M′

1.根據(jù)P中的任務點經(jīng)緯度坐標lp建立Rtree

2.Foreachp∈P

3.p.workers=φ

4.Foreachw∈W

5.areaw為以lw為圓心rw為半徑的圓外切正方形區(qū)域

6. 在Rtree中搜索與areaw重疊區(qū)域內(nèi)的任務點P(w)

7.p.workers.add(w)

8.Foreachu∈U

9.areau為以lu為圓心ru為半徑的圓外切正方形區(qū)域

10.在Rtree中搜索與areau重疊區(qū)域內(nèi)的任務點P(u)

11.Foreachp∈P(u)

12. Foreachw∈p.workers

13.M′.add((u，p，w))

14.返回M′

4.3 最短路徑長度計算優(yōu)化算法

得到集合U×P×W中包含所有可用三維匹配對的集合M′后，需要計算其中每個可用三維匹配對(u，p，w)的效用μ(u，p，w)，其中涉及到工人-任務點和工人-用戶之間的最短路徑長度計算.考慮到現(xiàn)有的一些最短路徑算法不能很好地平衡精度與速度，如Dijkstra算法[10]復雜度較高，A*過于依賴潛在價值函數(shù)的設計，本文借鑒了文獻[11]中避免很多相鄰的點對之共用的部分最短路徑被多次重復計算的基本思想，提出了基于路網(wǎng)的任務點選址場景下的最短路徑長度計算優(yōu)化算法.

下面以圖3為例解釋在面向路網(wǎng)的任務點選址場景下的最短路徑長度計算優(yōu)化算法.首先將可用三維匹配對中出現(xiàn)的所有用戶{u1，u2}、任務點{p1，p2}和工人{w1，w2，w3}根據(jù)他們經(jīng)緯度坐標映射到路網(wǎng)平面中的一批位置點.其次對所有用戶點進行聚類并找到該用戶簇的中心位置點lCU，并依次類推對任務點和工人聚類后找到中心點lCP和lCW.之后計算并保存兩個簇中心點間的最短路徑長度，作為簇之間的距離.此時，如果要計算兩類對象點(用戶-工人，或用戶-任務點)之間的最短路徑長度，就可以轉化為求兩個位置點分別到所在簇的中心點的距離與兩個簇之間距離的和.如果要計算可用三維匹配對(u2，p1，w3)的效用，按照定義5有μ(u2，p1，w3)=d(lw3，lu2)-d(lw3，lp1)/d(lw3，lp1)，那么在該最短路徑長度計算優(yōu)化算法中d(lw3，lu2)=d(lw3，lCW)+d(lCW，lCU)+d(lCU，lu2).同樣地，d(lw3，lp1)=d(lw3，lCW)+d(lCW，lCP)+d(lCP，lp1).顯然在簇之間的最短路徑被提前計算并保存下來時，相同的兩個簇內(nèi)的多點對間最短路徑長度可以避免大量重復計算.因為本文中對于所有可用三維匹配對都涉及兩次最短路徑長度計算，所以這一優(yōu)化可以大幅降低計算耗時，提高本文解決方案的效率.

圖3 最短路徑長度計算優(yōu)化算法示例圖Fig.3 Example of optimization algorithm for shortest path length calculation

算法3.最短路徑長度計算優(yōu)化算法

輸入：路圖G，用戶集U，工人集W，任務點集P，起點s∈W，終點t∈U∪P

輸出：起點s到終點t的最短路徑長度d(ls，lt)

1.根據(jù)U中的用戶經(jīng)緯度坐標lU層次聚類成簇集CU

2.numu=len(CU)

3.Foriin[0，numu-1]

4. 確定CU[i]的中心點位置lCU[i]

5.根據(jù)P中的工人經(jīng)緯度坐標lP層次聚類成簇集CP

6.nump=len(CP)

7.Forjin[0，nump-1]

8. 確定CP[j]的中心點位置lCP[j]

9.根據(jù)W中的任務點經(jīng)緯度坐標lw層次聚類成簇集CW

10.Foreachcluster∈CW

11. 確定cluster的中心點位置lcluster

12. Foriin[0，numu-1]

13. 計算并保存兩個簇中心間的距離d(lcluster，lCU[i])

14. Forjin[0，nump-1]

15. 計算并保存兩個簇中心間的距離d(lcluster，lCW[j])

16. 找到s所在的工人簇Cs

17. 計算s到簇Cs中心的距離d(ls，lCs.

18. 找到t所在的用戶或任務點簇Ct

19. 計算簇Ct中心到t的距離d(lCt，lt)

20.d(ls，lt)=d(ls，lCs)+d(lCs，lCt)+d(lCt，lt)

最短路徑長度計算優(yōu)化的偽代碼如算法3所示.輸入為路網(wǎng)G下的用戶集合U、工人集合W、任務點集合P、一個起點s(對象類別為工人)和一個終點t(對象類別為用戶/任務點)，輸出為起點到終點的最短路徑長度d(ls，lt).值得注意的是，第1-第15行為對給定工人、用戶和任務點的數(shù)據(jù)預處理部分，僅第16-第20行是給定起點和終點后計算最短路徑長度所需的操作.在執(zhí)行過程中，首先為所有用戶進行層次聚類，停止條件為兩個用戶簇之間的距離超過指定閾值，并找到每個用戶簇中所有位置點坐標的平均值坐標點作為該簇的中心點位置(第1-第4行).并對路網(wǎng)中的所有任務點做同樣的操作(第5-第8行).接著，在對所有工人進行聚類并確定中心點(第9-第11行)后，提前計算并保存工人簇到其他兩類對象簇的最短路徑距離(第12-第15行).給定一個起點s后，首先找到它所在的簇，并計算s到該簇中心點lCs的路網(wǎng)距離(第16-第17行).隨后，找到給定終點t的所在簇和簇中心點lCt到t的最短路徑長度(第18-第19行).最后，查找數(shù)據(jù)預處理階段保存的起點所在簇到終點所在簇之間的距離d(lCs，lCt)，并加上兩個端點與其所在簇中心點的距離，就是所求的起點s到終點t的最短路徑長度(第20行).

4.4 任務點容量充足時的任務選址算法

通過上述兩個優(yōu)化算法，得到原路網(wǎng)下的任務點選址問題中的所有可用三維匹配對的集合M′和其中每個可用三維匹配對的效用.本部分首先證明在所有任務點的容量超過用戶數(shù)量時，原問題可以規(guī)約到二分圖的完美匹配問題，然后給出基于KM算法的解決辦法.

定理2.給定所有可用三維匹配對的集合M′，其中有用戶集合U={u1，…，um}，工人集合W={w1，…，wn}和任務點集合P={p1，…，pk}，如果min{cp1，…，cpk}≥m，原問題可以規(guī)約到二分圖上的完美匹配問題.

證明：給定用戶ui和工人wj，稱能與他們組成可用三維匹配對且效用最高的任務點為p.由于每個任務點的容量都大于等于用戶數(shù)，所以即使其他所有的用戶-工人組合都在任務點p處取得最高效用，用戶ui和工人wj仍然能在p處執(zhí)行任務，即取到最高效用μ(ui，p，wj).則原問題的目標是找到一個集合M?M′，所有用戶在其中至多出現(xiàn)一次，且M中所有可用三維匹配對的效用之和最高.

構造一個二分圖，兩個互不相交的點集合為U和W，連接ui和wj之間的邊權重為μ(ui，p，wj)，其中p為能與ui和wj組成可用三維匹配對且效用最高的任務點.此時，原問題的目標可以規(guī)約到在構造的二分圖中找到完美匹配M，本文使用經(jīng)典KM算法[9]解決.

算法4.任務點容量充足時的任務選址算法

輸入：道路網(wǎng)絡圖G，可用三維匹配對集合M′=U×P×W

輸出：最優(yōu)可用三維匹配對集合M?M′

1.Foreachu∈U

2.Mu為包含u的所有可用三維匹配對集合

3.Wu是Mu中的工人集合

4. Foreachw∈Wu

5.μu，w是Mu中包含u，w的三維匹配對的最大效用

6.構造二分圖GM=(U，W)

7.二分圖中邊e(u，w)=μu，w

8.KM算法找到GM中的完美匹配M

9.返回M

任務點容量充足時的任務點選址偽代碼如算法4所示.輸入為路網(wǎng)G下的可用三維匹配集合M′=U×P×W，輸出原問題所求的最優(yōu)可用三維匹配對結合M.在執(zhí)行過程中，首先對M′的每個用戶u，找到能與其組成可用三維匹配對的工人集合Wu(第1～第3行).然后遍歷該集合中的工人，計算包含u的可用三維匹配對的最大效用μu，w(第4-第5行).接著構造二分圖GM，包括兩個互不相交的結點集合U和W，連接兩個結點u和w的邊權重為μu，w(第6-第7行).最后，用經(jīng)典KM算法找到GM中的完美匹配M，并作為路網(wǎng)下任務點選址問題在任務點容量充足時的最終解返回.

4.5 任務點容量不足時的分塊貪心任務選址算法

當任務點容量不足時，可以將原問題規(guī)約到最大三維匹配問題，目標是在三分圖U×P×W中尋找最大匹配M.由于在文獻[12]中，最大三維匹配問題已經(jīng)被證明是NP難的，所以無法在多項式時間內(nèi)找到本文問題在任務點容量不足情況下的最優(yōu)解.經(jīng)典的近似算法有貪心和局部搜索，前者在每一次選擇一條權值最大的邊，后者每次替換已有匹配中的一條邊來獲得更好的匹配效果.然而，在空間眾包場景中，3類對象(用戶、任務點和工人)的數(shù)量非常龐大，所以以上兩種近似算法的用時依舊不可小覷.同時，平臺需要很快做出決策并通知相關工人前往指定任務點，否則用戶和工人就會陷入空等.基于這種需求，本文對傳統(tǒng)最大三維匹配問題中的貪心算法進行了優(yōu)化，提出了分塊貪心算法.

傳統(tǒng)的最大三維匹配問題貪心算法在每一輪要遍歷所有的邊，找到一條權值最大的邊e(u，p，w).在此之后，因為任務點p的剩余容量發(fā)生了變化，還要遍歷所有剩余邊去更新與p有關的邊的權值.所以我們對原三分圖進行了分塊處理，按照路網(wǎng)中所有對象的位置聚類結果將其分成多個互不相交的三分圖.經(jīng)過這種處理，既能比隨機拆分盡量少地降低精度，又能加快尋找最大邊的過程，更能方便并行處理.下文以圖4為例解釋分塊貪心任務點選址算法.

圖4 分塊貪心示例圖Fig.4 Example of partitioned-greedy

對于平臺上的所有3類對象(包括用戶、任務點和工人)的位置點，統(tǒng)一按照經(jīng)緯度坐標進行聚類.之后，根據(jù)聚類結果為每個簇建立三分圖.如圖4中就有為簇C1和C2和分別建立的三分圖G1和G2，每個圖包括對應的簇內(nèi)所有位置點，每條連接3個點的邊表示該簇內(nèi)的可用三維匹配對.對每個三分圖記錄其中的最大邊并記錄其權值，如max1=9，max2=10.貪心地選擇最大邊(u4，p3，w3)后，僅需要更新三分圖G2中與p3相關的邊，之后重新計算該圖中的最大邊.在下一輪中，直接將更新后的max2=8直接與上一輪的max1比較，就可得到全局最大邊.

任務點容量不足時的分塊貪心任務點選址的偽代碼如算法5所示.輸入為路網(wǎng)G下的用戶集合U、工人集合W和任務點集合P，輸出為原問題所求的最優(yōu)可用三維匹配對結合M.首先對路網(wǎng)中的所有對象點統(tǒng)一按照經(jīng)緯度坐標進行聚類，得到簇集合C(第1行).之后在算法1和算法2的優(yōu)化基礎上，為每個簇建立三分圖并計算每條邊的權值，同時該簇的最大邊及其權值(第2-第6行).由于每個用戶在最終匹配中至多出現(xiàn)一次，所以在工人和任務點充足時共貪心選擇m次最大邊，對應m個用戶提出的所有訂單.在每一輪，將最大邊p加入最終匹配集合后，更新該簇中與p共用任務點的其他邊，并在剩余邊中確定該簇的當前最大邊繼續(xù)與其他簇的最大邊進行比較(第7-第11行).重復以上更新過程，直至最優(yōu)可用三維匹配對集合M包含每個用戶所在的邊.

算法5.任務點容量不足時的分塊貪心任務點選址算法

輸入：道路網(wǎng)絡圖G，用戶集U，工人集W，任務點集P

輸出：最優(yōu)可用三維匹配對集合M

1.對所有對象點進行聚類得到簇集合C={c1，…，cq}

2.Foriin[0，q-1]

3. 利用算法1找到ci中的可用匹配對組合Mi

4. 利用算法2計算Mi中每個匹配對的效用μ(Mi)

5. 根據(jù)Mi和μ(Mi)建立三分圖Gi

6. 記錄最大邊權值maxi

7.Forjin[0，m-1]

8.p是權值為{max1，…，maxp}中最大值的邊

9. 將邊p加入最大匹配M

10. 更新p所在三分圖中包含p的其他邊

11. 更新該簇的最大邊并記錄權值

12.返回M

5 實驗分析

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

本文使用真實數(shù)據(jù)來測試所提出的方法.考慮到工人最大可接受范圍rw和用戶最大可接受范圍ru的限制，工人和用戶不會移動太遠的距離，因此把所有對象都限制在一個城市內(nèi).本文選擇西安作為目標城市，從滴滴打車1獲取從2018年10月1日～2018年10月30日該市4500000條打車訂單數(shù)據(jù)，包括訂單編號和訂單軌跡數(shù)據(jù).訂單軌跡點的采集間隔是2-4s，且已經(jīng)做過綁路處理，保證數(shù)據(jù)都能夠對應到實際的道路信息.若一個訂單在短時間內(nèi)出現(xiàn)兩個軌跡點行駛方向相反，認為這個訂單存在繞路接用戶(乘客)的情況，我們抽取這種訂單的初始軌跡點作為工人(司機)初始位置，繞路后的第一個軌跡點作為用戶初始位置.之后從OSM(OpenStreetMap：一個開源的地圖數(shù)據(jù)社區(qū))獲取西安路網(wǎng)數(shù)據(jù)，并導出路網(wǎng)數(shù)據(jù)中的節(jié)點作為獲取候選上車點.最終，本文中所使用的數(shù)據(jù)集包含50000個工人，10000個用戶以及100000個候選任務點.

表1展示了本文實驗的參數(shù)設置，其中黑體字表示實驗的默認參數(shù).在每一個實驗中，只改變其中一個參數(shù)，展示被測方法的效用和運行時間，其余參數(shù)保持默認值.

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

5.2 對比算法

如前文所述，在任務點容量充足的情況下，我們將原問題轉化成二分最大匹配問題；在任務點容量不足的情況下，轉化為最大三維匹配問題.對于前者，可用KM算法求得最優(yōu)解；對于后者，可用貪心算法求得較優(yōu)解.為了證明本文所提出的篩選可用三維匹配對優(yōu)化算法和最短路徑長度計算優(yōu)化算法的優(yōu)化效果，本文會在KM和貪心兩種傳統(tǒng)算法的基礎上分別添加兩種優(yōu)化.具體來說：

1)對于KM算法不做任何優(yōu)化，KM(o1)代表只使用篩選可用三維匹配對優(yōu)化算法進行優(yōu)化，KM(o2)代表只使用最短路徑長度計算優(yōu)化算法進行優(yōu)化，KM(o1+o2)代表同時使用兩種優(yōu)化.

2)對于貪心算法不做任何優(yōu)化，貪心(o1)代表只使用篩選可用三維匹配對優(yōu)化算法進行優(yōu)化，貪心(o2)代表只使用最短路徑長度計算優(yōu)化算法進行優(yōu)化，貪心(o1+o2)代表同時使用兩種優(yōu)化.

在任務點容量不足的場景下，對于已經(jīng)加入兩種優(yōu)化的貪心算法的基礎上，本文又提出了貪心分塊算法，能在略微降低效用的前提下明顯減少運行用時.所以在將該算法與沒有分塊策略的貪心算法進行對比的同時，和其他兩種三維匹配算法進行對比：

1)優(yōu)化貪心算法：在解決最大三維匹配問題的貪心算法基礎上采用篩選可用三維匹配對優(yōu)化算法和最短路徑長度計算優(yōu)化算法.

2)局部搜索算法[6]：首先隨機產(chǎn)生一個臨時匹配集，之后不斷對其中的每一個匹配，嘗試能否更換為一個新匹配，使得不與其他匹配沖突的同時效用大于原匹配.

3)自適應閾值算法[6]：根據(jù)平臺已有的三類對象確定初始閾值，在匹配過程中僅保留效用大于該閾值的三維匹配，并不斷更新閾值.

5.3 實驗結果和分析

本節(jié)首先進行實驗，來證明本文所提出的兩個優(yōu)化算法的實際優(yōu)化效果.隨后在優(yōu)化的基礎上，將本文的貪心分塊算法與其他三維匹配領域算法進行比較，并分析不同用戶數(shù)量，不同工人數(shù)量，不同上車點數(shù)量對效用和計算時間的影響.

5.3.1 優(yōu)化方法對實驗結果的影響

從表2可以看出，在默認參數(shù)下，當任務點容量充足時，兩種優(yōu)化算法分別降低的效用較為微小，降低的運行時間較為明顯.從表3可以明顯看出，兩種優(yōu)化算法在任務點容量不足時也能大大提高傳統(tǒng)貪心算法的效率.總體來看，本文所提的優(yōu)化算法能以非常小的精度犧牲換取可觀的效率提升，在兩種不同情況下的實驗也證實了其穩(wěn)定性.

表2 兩種優(yōu)化方式在任務點容量充足時的效果Table 2 Effect of two optimization methods when the capacity of task locations are sufficient

表3 兩種優(yōu)化方式在任務點容量不足時的效果Table 3 Effect of two optimization methods when the capacity of task locations are insufficient

5.3.2 分塊貪心算法的實驗分析及參數(shù)影響

1)分塊貪心算法的性能分析

從表4可以看出，無論所有參數(shù)如何變化，分塊貪心算法的效用都維持在一個不錯的水平.算法的效用與優(yōu)化貪心算法幾乎相同，稍低的原因是在分塊的過程中僅考慮每個簇內(nèi)的可用三維匹配對，而無視不同簇之間可能存在的高效用匹配對.而在局部搜索算法中，更多次的迭代決定了它能比局部最優(yōu)的貪心算法找到更優(yōu)解.但與此同時，分塊貪心的效用也明顯高于自適應閾值算法.

表4 不同方法在參數(shù)變化下的效用Table 4 Utilities of different methods under parameter changes

從表5可以看出，分塊貪心算法的運行時間始終是所有對比方法中最低的，與優(yōu)化貪心算法的時間差也有力證明了分塊策略能明顯提高計算效率.自適應閾值算法的用時表現(xiàn)不錯是因為對于一些效用值低的可用三維匹配會被直接舍棄，所以在之后需要考慮沖突的三維匹配數(shù)量會大大減少.

表5 不同方法在參數(shù)變化下的運行時間Table 5 Running time of different methods under parameter changes

2)用戶數(shù)量對實驗結果的影響

從表4和表5看，隨著用戶數(shù)量的上升，所有算法的效用和用時都出現(xiàn)提升，這是因為可供選擇的可用三維匹配增多.其中，分塊貪心算法的效用略低于局部搜索和優(yōu)化貪心算法，但分塊貪心任務選址算法與傳統(tǒng)貪心相比，運行時間有著顯著的降低.

3)工人數(shù)量對實驗結果的影響

從表4和表5也能看出不同工人數(shù)量對所有方法的效用和運行時間的影響.隨工人數(shù)量增加，分塊貪心算法與其他算法的表現(xiàn)差距穩(wěn)定.相比優(yōu)化貪心算法，分塊貪心算法在效用只有微弱降低的情況下，運行時間都能實現(xiàn)明顯減少.

4)任務點數(shù)量對實驗結果的影響

如表4和表5所示，在任務點數(shù)量變化的前提下，分塊貪心算法始終可以使用最少的計算時間并得到近似優(yōu)化貪心的效用結果.再次證明了無論各類對象數(shù)量變化，本文所提方法表現(xiàn)穩(wěn)定.

6 總 結

本文針對現(xiàn)有的空間眾包任務分配工作忽視任務點位置對分配效果的影響和底層路網(wǎng)結構的不足，提出了面向路網(wǎng)的空間眾包三維匹配任務點選址問題.本文根據(jù)任務點容量不同的場景分別進行分析：證明了容量充足時可以將原問題規(guī)約到二分圖最大匹配問題，并且用經(jīng)典KM算法獲得最優(yōu)解；對任務點容量不足情況下的原問題，本文提出了分塊貪心算法.此外，本文還提出了兩種優(yōu)化方法，分別用于快速篩選可用三維匹配對和計算多點對之間的最短路徑長度.最后，通過實驗證明了本文所提解決方法能夠兼具速度與精度.