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

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

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

6 馬旭燕;;眾包在項目翻譯教學中的應用初探[J];上海翻譯;2017年06期

7 王志宏;傅長濤;李陽陽;;眾包的行業(yè)應用研究述評[J];長安大學學報(社會科學版);2017年05期

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

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

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

相關會議論文 前10條

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

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

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

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

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

6 張錚;;O2O眾包模式交通事故的責任承擔——以車輛掛靠關系為類推[A];法院改革與民商事審判問題研究——全國法院第29屆學術討論會獲獎論文集（下）[C];2018年

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

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

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

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

相關重要報紙文章 前10條

1 記者 楊梅 梅文婷;罰眾包管理公司萬元 邀請騎手擔當志愿者[N];上海法治報;2019年

2 陳曦;天津探索科研眾包揭榜機制[N];科技日報;2019年

3 本報記者 張露;華少加盟“眾包造車” 中國好汽車要出爐了[N];中國青年報;2015年

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

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

6 蘇報評論員 金根;攻關技術瓶頸，“科研眾包”有戲[N];蘇州日報;2018年

7 記者 吳潔;從“雙創(chuàng)”到“四眾” 創(chuàng)客們準備好了嗎[N];昆明日報;2016年

8 季征;云南：搭建平臺釋放創(chuàng)業(yè)創(chuàng)新能量[N];云南經(jīng)濟日報;2016年

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

10 記者 邱登科;廣東公布首批科研眾包培育平臺[N];民營經(jīng)濟報;2017年

相關博士學位論文 前10條

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

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

3 李紹園;多標記眾包學習研究[D];南京大學;2018年

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

5 向為;創(chuàng)意設計柔性眾包的方法與應用[D];浙江大學;2017年

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

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

8 馮小亮;基于雙邊市場的眾包模式研究[D];武漢大學;2012年

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

10 龐建剛;眾包社區(qū)創(chuàng)新的運營機制設計[D];中國科學技術大學;2014年

相關碩士學位論文 前10條

1 陳稼s

本文編號：2667722