【摘要】：近年來(lái)隨著通信技術(shù)的進(jìn)步,移動(dòng)設(shè)備的計(jì)算能力高速發(fā)展。同時(shí)設(shè)備的成本也在迅速下降,智能移動(dòng)設(shè)備已經(jīng)觸及了我們生活的每一個(gè)角落。伴隨著硬件的普及,越來(lái)越多的移動(dòng)眾包(Mobile Crowdsourcing)應(yīng)用也層出不窮。這些應(yīng)用的提供商建立了許多移動(dòng)眾包平臺(tái),借助眾包的思想利用這些設(shè)備來(lái)提高生活質(zhì)量。而在這類(lèi)移動(dòng)眾包問(wèn)題中,最核心也是最困難的問(wèn)題要屬任務(wù)分配問(wèn)題,即如何把不同位置不同時(shí)間的各個(gè)任務(wù)高效地分配給動(dòng)態(tài)進(jìn)出平臺(tái)的用戶(hù)們。一個(gè)高效的任務(wù)分配方案能夠提升任務(wù)完成效率,既能提高用戶(hù)收入,也能節(jié)約平臺(tái)成本。在過(guò)去的文章中,對(duì)于這類(lèi)任務(wù)分配問(wèn)題,由于它的復(fù)雜性,研究者們往往采用啟發(fā)式算法,通過(guò)調(diào)節(jié)參數(shù)的方式得到實(shí)際方案,但是缺少理論上的驗(yàn)證。因此這些方案通常只適用一些特殊情況,一旦環(huán)境發(fā)生變化,算法效率就會(huì)大幅下降。所以本文試圖通過(guò)一些組合優(yōu)化的方法得到一個(gè)理論上可以驗(yàn)證的高效方案。本文考慮了涉及時(shí)空特性任務(wù)的移動(dòng)眾包平臺(tái)中的有界任務(wù)分配問(wèn)題(Bounded Task Allocation Problem)。首先,本文將這一類(lèi)實(shí)際問(wèn)題通過(guò)數(shù)學(xué)方式建模為一個(gè)整數(shù)線性規(guī)劃問(wèn)題,并通過(guò)歸約的方法證明了這類(lèi)問(wèn)題屬于NP困難問(wèn)題。隨后,本文給出了一個(gè)近似算法設(shè)計(jì)作為解決方案。通過(guò)嚴(yán)謹(jǐn)?shù)睦碚摲治?本文證明了這個(gè)算法是一個(gè)具有(2+?)近似比的近似算法,并且給出了例子說(shuō)明這個(gè)近似比的分析是嚴(yán)格的。最后,通過(guò)一些模擬實(shí)驗(yàn),將算法和過(guò)去的兩個(gè)基準(zhǔn)方案進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果顯示本文的算法在實(shí)際問(wèn)題中也能有很好的表現(xiàn)。就我們所知,本文是第一個(gè)對(duì)這類(lèi)任務(wù)分配問(wèn)題給出一個(gè)具有常數(shù)近似比算法的論文。
【圖文】：

在一個(gè)重定向網(wǎng)絡(luò)中，有一個(gè)帶權(quán)的點(diǎn)集和一個(gè)帶權(quán)的邊集。給定一個(gè)起始點(diǎn)、終點(diǎn)點(diǎn)對(duì)和一個(gè)時(shí)間限制，重定向問(wèn)題的目標(biāo)是找到一條從起始點(diǎn)到終點(diǎn)的路徑，使其包含邊的權(quán)重不超過(guò)時(shí)間限制，而包含點(diǎn)的權(quán)重盡可能大。圖2 1表示了一個(gè)重定向問(wèn)題的實(shí)例。在這個(gè)例子中，用戶(hù)需要在 9:00 時(shí)刻從源點(diǎn)出發(fā)，在 17:00 前到達(dá)目標(biāo)點(diǎn)，目標(biāo)是期間所經(jīng)過(guò)的所有點(diǎn)的分?jǐn)?shù)總和盡可能高。圖 2 1 一個(gè)重定向問(wèn)題的實(shí)例[56]— 8 —

有各自固定的起始點(diǎn)以及共同的長(zhǎng)度限制，目標(biāo)是使得這些路徑所經(jīng)過(guò)的實(shí)心黑點(diǎn)盡可能多。圖4 1(b)，，4 1(c)和4 1(d)分別表示：?jiǎn)斡脩?hù)，5 單位時(shí)間；單用戶(hù)，7 單位時(shí)間；雙用戶(hù)，5 單位時(shí)間三種情況下的最優(yōu)解。每個(gè)用戶(hù)的初始位置用黑色圓圈，移動(dòng)路徑用虛線來(lái)表示。從圖4 1(b)和4 1(c)的對(duì)比，可以發(fā)現(xiàn)，當(dāng)規(guī)劃總時(shí)間發(fā)生變化的時(shí)候，用戶(hù)最優(yōu)路徑可能會(huì)發(fā)生極大變化，走上完全不同的路線。同樣的，從圖4 1(b)和4 1(d)中也可以發(fā)現(xiàn)
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：F724.6;O221.1

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉偉;丁凱文;劉德海;;基于微分博弈的網(wǎng)絡(luò)眾包違約風(fēng)險(xiǎn)控制機(jī)制研究[J];系統(tǒng)工程理論與實(shí)踐;2019年10期

2 馮洋;王yN;房春榮;郭楠楠;陳振宇;;高可信眾包群體構(gòu)建方法[J];中國(guó)科學(xué):信息科學(xué);2019年11期

3 鄧媚;陳程;張宗法;;廣東科研眾包平臺(tái)的發(fā)展動(dòng)向分析[J];科技創(chuàng)新發(fā)展戰(zhàn)略研究;2019年03期

4 鄭俊杰;;眾包法律問(wèn)題探究[J];合作經(jīng)濟(jì)與科技;2019年18期

5 王鴻飛;陳麗敏;何靜;;科研眾包平臺(tái)發(fā)展現(xiàn)狀與對(duì)策——基于國(guó)際、國(guó)內(nèi)、廣東省科研眾包培育平臺(tái)案例的分析[J];科技創(chuàng)新發(fā)展戰(zhàn)略研究;2019年05期

6 馬旭燕;;眾包在項(xiàng)目翻譯教學(xué)中的應(yīng)用初探[J];上海翻譯;2017年06期

7 王志宏;傅長(zhǎng)濤;李陽(yáng)陽(yáng);;眾包的行業(yè)應(yīng)用研究述評(píng)[J];長(zhǎng)安大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版);2017年05期

8 李洋;溫亮明;李健;;國(guó)內(nèi)圖書(shū)館眾包研究文獻(xiàn)綜述[J];知識(shí)管理論壇;2018年02期

9 劉彤;;關(guān)于檔案眾包的分析與研究[J];山東檔案;2018年04期

10 曾婧婧;;國(guó)外政府資助型科研眾包研究綜述[J];中國(guó)科技論壇;2016年12期

相關(guān)會(huì)議論文 前10條

1 劉世群;李思佳;倪世光;彭凱平;;眾包:移動(dòng)互聯(lián)網(wǎng)時(shí)代的心理研究工具[A];第二十屆全國(guó)心理學(xué)學(xué)術(shù)會(huì)議--心理學(xué)與國(guó)民心理健康摘要集[C];2017年

2 尹彥;張晉冉;;天津市民參與快遞眾包意愿的實(shí)證研究[A];發(fā)揮社會(huì)科學(xué)作用 促進(jìn)天津改革發(fā)展——天津市社會(huì)科學(xué)界第十二屆學(xué)術(shù)年會(huì)優(yōu)秀論文集（中）[C];2017年

3 趙巍;;眾包負(fù)面效應(yīng)及潛在風(fēng)險(xiǎn)研究[A];“決策論壇——企業(yè)行政管理與創(chuàng)新學(xué)術(shù)研討會(huì)”論文集（上）[C];2016年

4 任延靜;林麗慧;;眾包平臺(tái)創(chuàng)新競(jìng)賽中加價(jià)延期機(jī)制采納決策的研究[A];第八屆（2013）中國(guó)管理學(xué)年會(huì)——信息管理分會(huì)場(chǎng)論文集[C];2013年

5 周素紅;彭伊儂;;眾包理念下的參與式新型城市治理[A];持續(xù)發(fā)展 理性規(guī)劃——2017中國(guó)城市規(guī)劃年會(huì)論文集（12城鄉(xiāng)治理與政策研究）[C];2017年

6 張錚;;O2O眾包模式交通事故的責(zé)任承擔(dān)——以車(chē)輛掛靠關(guān)系為類(lèi)推[A];法院改革與民商事審判問(wèn)題研究——全國(guó)法院第29屆學(xué)術(shù)討論會(huì)獲獎(jiǎng)?wù)撐募ㄏ拢C];2018年

7 劉汕;鄧瓊;;互聯(lián)網(wǎng)環(huán)境下眾包創(chuàng)新服務(wù)績(jī)效的關(guān)鍵影響因素研究[A];第十五屆全國(guó)計(jì)算機(jī)模擬與信息技術(shù)學(xué)術(shù)會(huì)議論文集[C];2015年

8 王冬升;黃健;;利用眾包方式解決地理國(guó)情覆蓋分類(lèi)監(jiān)測(cè)[A];第二十屆華東六省一市測(cè)繪學(xué)會(huì)（江蘇）學(xué)術(shù)交流會(huì)論文集[C];2018年

9 聶勇浩;劉佳鑫;;歷史檔案數(shù)字化中的眾包實(shí)施模式研究[A];新時(shí)代檔案工作者的使命：融合與創(chuàng)新——2018年全國(guó)檔案工作者年會(huì)論文集[C];2018年

10 陳鶴陽(yáng);陳婧;;眾包模式下應(yīng)急管理的情報(bào)分析[A];“四個(gè)全面”·創(chuàng)新發(fā)展·天津機(jī)遇——天津市社會(huì)科學(xué)界第十一屆學(xué)術(shù)年會(huì)優(yōu)秀論文集（中）[C];2015年

相關(guān)重要報(bào)紙文章 前10條

1 記者 楊梅 梅文婷;罰眾包管理公司萬(wàn)元 邀請(qǐng)騎手擔(dān)當(dāng)志愿者[N];上海法治報(bào);2019年

2 陳曦;天津探索科研眾包揭榜機(jī)制[N];科技日?qǐng)?bào);2019年

3 本報(bào)記者 張露;華少加盟“眾包造車(chē)” 中國(guó)好汽車(chē)要出爐了[N];中國(guó)青年報(bào);2015年

4 省政協(xié)委員 李明喜;致力打造科研眾包平臺(tái)[N];江淮時(shí)報(bào);2017年

5 陳健秀 夏福良;從打包生產(chǎn)走向眾包定制[N];中國(guó)石化報(bào);2018年

6 蘇報(bào)評(píng)論員 金根;攻關(guān)技術(shù)瓶頸，“科研眾包”有戲[N];蘇州日?qǐng)?bào);2018年

7 記者 吳潔;從“雙創(chuàng)”到“四眾” 創(chuàng)客們準(zhǔn)備好了嗎[N];昆明日?qǐng)?bào);2016年

8 季征;云南：搭建平臺(tái)釋放創(chuàng)業(yè)創(chuàng)新能量[N];云南經(jīng)濟(jì)日?qǐng)?bào);2016年

9 本報(bào)記者 季征;搭建平臺(tái)釋放創(chuàng)業(yè)創(chuàng)新能量[N];云南日?qǐng)?bào);2016年

10 記者 邱登科;廣東公布首批科研眾包培育平臺(tái)[N];民營(yíng)經(jīng)濟(jì)報(bào);2017年

相關(guān)博士學(xué)位論文 前10條

1 張立曄;基于眾包的WLAN室內(nèi)定位技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2018年

2 提倪（Muhammad Zahid Tunio）;面向眾包軟件開(kāi)發(fā)的任務(wù)分配技術(shù)研究[D];北京郵電大學(xué);2018年

3 李紹園;多標(biāo)記眾包學(xué)習(xí)研究[D];南京大學(xué);2018年

4 宋奕;智能環(huán)境下眾包物流企業(yè)員工組織行為與運(yùn)作的仿真研究[D];華中科技大學(xué);2018年

5 向?yàn)?創(chuàng)意設(shè)計(jì)柔性眾包的方法與應(yīng)用[D];浙江大學(xué);2017年

6 吳薇;眾包競(jìng)賽情境下接包者持續(xù)參與行為研究：競(jìng)爭(zhēng)自我效能的作用[D];中國(guó)科學(xué)技術(shù)大學(xué);2018年

7 林素芬;基于眾包參與者網(wǎng)絡(luò)的眾包績(jī)效提升研究[D];華僑大學(xué);2015年

8 馮小亮;基于雙邊市場(chǎng)的眾包模式研究[D];武漢大學(xué);2012年

9 饒華銘;人本計(jì)算系統(tǒng)中眾包數(shù)據(jù)質(zhì)量控制方法的改進(jìn)及其應(yīng)用研究[D];南京理工大學(xué);2017年

10 龐建剛;眾包社區(qū)創(chuàng)新的運(yùn)營(yíng)機(jī)制設(shè)計(jì)[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 陳稼s

本文編號(hào)：2667722