面向路網(wǎng)的空間眾包三維匹配任務(wù)點(diǎn)選址算法

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

1(蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006)

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

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

E-mail：anliu@suda.edu.cn

1 引 言

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

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

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

圖1 打車場(chǎng)景中的任務(wù)點(diǎn)選址示例圖Fig.1 Example of task location in taxi scenario

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

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

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

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

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

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

2 相關(guān)工作

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

2.1 任務(wù)分配

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

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

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

2.2 3類對(duì)象匹配

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

3 問題定義和復(fù)雜度

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

3.1 問題定義

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

定義1.(路網(wǎng))路網(wǎng)定義為一張有向帶權(quán)圖G=.結(jié)點(diǎn)集合V中的每個(gè)結(jié)點(diǎn)v表示實(shí)際路網(wǎng)中的一個(gè)位置點(diǎn)，由其經(jīng)緯度坐標(biāo)唯一確定；邊集合E中的每條邊e=(vi，vj)表示在路網(wǎng)上從位置vi前往位置vj的最短路徑，邊權(quán)集合W中的每個(gè)權(quán)重d(e)表示經(jīng)過邊e所代表的最短路徑的旅行成本.為了簡便起見，本文用最短路徑e=(vi，vj)的移動(dòng)距離d(vi，vj)作為旅行成本.本文所提出的方法可以輕松地?cái)U(kuò)展到旅行成本為時(shí)間的場(chǎng)景中，因?yàn)樵诠と嘶蛴脩粢苿?dòng)速度已知時(shí)，距離和時(shí)間很容易進(jìn)行相互轉(zhuǎn)換.

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

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

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

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

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

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

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

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

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

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

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

3.2 問題復(fù)雜性

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

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

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

4 解決方案

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

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

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

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

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

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

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

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

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

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

4.Ifmax(cp)≥|U|

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

6.Else

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

8.根據(jù)匹配M通知相應(yīng)的工人和用戶前往任務(wù)點(diǎn)

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

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

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

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

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

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

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

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

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

輸出：可用三維匹配對(duì)集合M′

1.根據(jù)P中的任務(wù)點(diǎn)經(jīng)緯度坐標(biāo)lp建立Rtree

2.Foreachp∈P

3.p.workers=φ

4.Foreachw∈W

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

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

7.p.workers.add(w)

8.Foreachu∈U

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

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

11.Foreachp∈P(u)

12. Foreachw∈p.workers

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

14.返回M′

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

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

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

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

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

輸入：路圖G，用戶集U，工人集W，任務(wù)點(diǎn)集P，起點(diǎn)s∈W，終點(diǎn)t∈U∪P

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

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

2.numu=len(CU)

3.Foriin[0，numu-1]

4. 確定CU[i]的中心點(diǎn)位置lCU[i]

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

6.nump=len(CP)

7.Forjin[0，nump-1]

8. 確定CP[j]的中心點(diǎn)位置lCP[j]

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

10.Foreachcluster∈CW

11. 確定cluster的中心點(diǎn)位置lcluster

12. Foriin[0，numu-1]

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

14. Forjin[0，nump-1]

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

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

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

18. 找到t所在的用戶或任務(wù)點(diǎn)簇Ct

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

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

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

4.4 任務(wù)點(diǎn)容量充足時(shí)的任務(wù)選址算法

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

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

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

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

算法4.任務(wù)點(diǎn)容量充足時(shí)的任務(wù)選址算法

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

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

1.Foreachu∈U

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

3.Wu是Mu中的工人集合

4. Foreachw∈Wu

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

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

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

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

9.返回M

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

4.5 任務(wù)點(diǎn)容量不足時(shí)的分塊貪心任務(wù)選址算法

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

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

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

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

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

算法5.任務(wù)點(diǎn)容量不足時(shí)的分塊貪心任務(wù)點(diǎn)選址算法

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

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

1.對(duì)所有對(duì)象點(diǎn)進(jìn)行聚類得到簇集合C={c1，…，cq}

2.Foriin[0，q-1]

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

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

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

6. 記錄最大邊權(quán)值maxi

7.Forjin[0，m-1]

8.p是權(quán)值為{max1，…，maxp}中最大值的邊

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

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

11. 更新該簇的最大邊并記錄權(quán)值

12.返回M

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

5.1 實(shí)驗(yàn)數(shù)據(jù)集與參數(shù)設(shè)置

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

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

表1 實(shí)驗(yàn)參數(shù)Table 1 Experimental parameters

5.2 對(duì)比算法

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

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

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

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

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

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

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

5.3 實(shí)驗(yàn)結(jié)果和分析

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

5.3.1 優(yōu)化方法對(duì)實(shí)驗(yàn)結(jié)果的影響

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

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

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

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

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

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

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

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

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

2)用戶數(shù)量對(duì)實(shí)驗(yàn)結(jié)果的影響

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

3)工人數(shù)量對(duì)實(shí)驗(yàn)結(jié)果的影響

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

4)任務(wù)點(diǎn)數(shù)量對(duì)實(shí)驗(yàn)結(jié)果的影響

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

6 總 結(jié)

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