移动众包平台的任务分配算法

发布时间：2020-05-17 01:53

【摘要】：近年来随着通信技术的进步,移动设备的计算能力高速发展。同时设备的成本也在迅速下降,智能移动设备已经触及了我们生活的每一个角落。伴随着硬件的普及,越来越多的移动众包(Mobile Crowdsourcing)应用也层出不穷。这些应用的提供商建立了许多移动众包平台,借助众包的思想利用这些设备来提高生活质量。而在这类移动众包问题中,最核心也是最困难的问题要属任务分配问题,即如何把不同位置不同时间的各个任务高效地分配给动态进出平台的用户们。一个高效的任务分配方案能够提升任务完成效率,既能提高用户收入,也能节约平台成本。在过去的文章中,对于这类任务分配问题,由于它的复杂性,研究者们往往采用启发式算法,通过调节参数的方式得到实际方案,但是缺少理论上的验证。因此这些方案通常只适用一些特殊情况,一旦环境发生变化,算法效率就会大幅下降。所以本文试图通过一些组合优化的方法得到一个理论上可以验证的高效方案。本文考虑了涉及时空特性任务的移动众包平台中的有界任务分配问题(Bounded Task Allocation Problem)。首先,本文将这一类实际问题通过数学方式建模为一个整数线性规划问题,并通过归约的方法证明了这类问题属于NP困难问题。随后,本文给出了一个近似算法设计作为解决方案。通过严谨的理论分析,本文证明了这个算法是一个具有(2+?)近似比的近似算法,并且给出了例子说明这个近似比的分析是严格的。最后,通过一些模拟实验,将算法和过去的两个基准方案进行了对比。实验结果显示本文的算法在实际问题中也能有很好的表现。就我们所知,本文是第一个对这类任务分配问题给出一个具有常数近似比算法的论文。
【图文】：

在一个重定向网络中，有一个带权的点集和一个带权的边集。给定一个起始点、终点点对和一个时间限制，重定向问题的目标是找到一条从起始点到终点的路径，使其包含边的权重不超过时间限制，而包含点的权重尽可能大。图2 1表示了一个重定向问题的实例。在这个例子中，用户需要在 9:00 时刻从源点出发，在 17:00 前到达目标点，目标是期间所经过的所有点的分数总和尽可能高。图 2 1 一个重定向问题的实例[56]— 8 —

有各自固定的起始点以及共同的长度限制，目标是使得这些路径所经过的实心黑点尽可能多。图4 1(b)，，4 1(c)和4 1(d)分别表示：单用户，5 单位时间；单用户，7 单位时间；双用户，5 单位时间三种情况下的最优解。每个用户的初始位置用黑色圆圈，移动路径用虚线来表示。从图4 1(b)和4 1(c)的对比，可以发现，当规划总时间发生变化的时候，用户最优路径可能会发生极大变化，走上完全不同的路线。同样的，从图4 1(b)和4 1(d)中也可以发现
【学位授予单位】：上海交通大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：F724.6;O221.1

【相似文献】

相关期刊论文 前10条

1 刘伟;丁凯文;刘德海;;基于微分博弈的网络众包违约风险控制机制研究[J];系统工程理论与实践;2019年10期

2 冯洋;王yN;房春荣;郭楠楠;陈振宇;;高可信众包群体构建方法[J];中国科学:信息科学;2019年11期

3 邓媚;陈程;张宗法;;广东科研众包平台的发展动向分析[J];科技创新发展战略研究;2019年03期

4 郑俊杰;;众包法律问题探究[J];合作经济与科技;2019年18期

5 王鸿飞;陈丽敏;何静;;科研众包平台发展现状与对策——基于国际、国内、广东省科研众包培育平台案例的分析[J];科技创新发展战略研究;2019年05期

6 马旭燕;;众包在项目翻译教学中的应用初探[J];上海翻译;2017年06期

7 王志宏;傅长涛;李阳阳;;众包的行业应用研究述评[J];长安大学学报(社会科学版);2017年05期

8 李洋;温亮明;李健;;国内图书馆众包研究文献综述[J];知识管理论坛;2018年02期

9 刘彤;;关于档案众包的分析与研究[J];山东档案;2018年04期

10 曾婧婧;;国外政府资助型科研众包研究综述[J];中国科技论坛;2016年12期

相关会议论文 前10条

1 刘世群;李思佳;倪世光;彭凯平;;众包:移动互联网时代的心理研究工具[A];第二十届全国心理学学术会议--心理学与国民心理健康摘要集[C];2017年

2 尹彦;张晋冉;;天津市民参与快递众包意愿的实证研究[A];发挥社会科学作用 促进天津改革发展——天津市社会科学界第十二届学术年会优秀论文集（中）[C];2017年

3 赵巍;;众包负面效应及潜在风险研究[A];“决策论坛——企业行政管理与创新学术研讨会”论文集（上）[C];2016年

4 任延静;林丽慧;;众包平台创新竞赛中加价延期机制采纳决策的研究[A];第八届（2013）中国管理学年会——信息管理分会场论文集[C];2013年

5 周素红;彭伊侬;;众包理念下的参与式新型城市治理[A];持续发展 理性规划——2017中国城市规划年会论文集（12城乡治理与政策研究）[C];2017年

6 张铮;;O2O众包模式交通事故的责任承担——以车辆挂靠关系为类推[A];法院改革与民商事审判问题研究——全国法院第29届学术讨论会获奖论文集（下）[C];2018年

7 刘汕;邓琼;;互联网环境下众包创新服务绩效的关键影响因素研究[A];第十五届全国计算机模拟与信息技术学术会议论文集[C];2015年

8 王冬升;黄健;;利用众包方式解决地理国情覆盖分类监测[A];第二十届华东六省一市测绘学会（江苏）学术交流会论文集[C];2018年

9 聂勇浩;刘佳鑫;;历史档案数字化中的众包实施模式研究[A];新时代档案工作者的使命：融合与创新——2018年全国档案工作者年会论文集[C];2018年

10 陈鹤阳;陈婧;;众包模式下应急管理的情报分析[A];“四个全面”·创新发展·天津机遇——天津市社会科学界第十一届学术年会优秀论文集（中）[C];2015年

相关重要报纸文章 前10条

1 记者 杨梅 梅文婷;罚众包管理公司万元 邀请骑手担当志愿者[N];上海法治报;2019年

2 陈曦;天津探索科研众包揭榜机制[N];科技日报;2019年

3 本报记者 张露;华少加盟“众包造车” 中国好汽车要出炉了[N];中国青年报;2015年

4 省政协委员 李明喜;致力打造科研众包平台[N];江淮时报;2017年

5 陈健秀 夏福良;从打包生产走向众包定制[N];中国石化报;2018年

6 苏报评论员 金根;攻关技术瓶颈，“科研众包”有戏[N];苏州日报;2018年

7 记者 吴洁;从“双创”到“四众” 创客们准备好了吗[N];昆明日报;2016年

8 季征;云南：搭建平台释放创业创新能量[N];云南经济日报;2016年

9 本报记者 季征;搭建平台释放创业创新能量[N];云南日报;2016年

10 记者 邱登科;广东公布首批科研众包培育平台[N];民营经济报;2017年

相关博士学位论文 前10条

1 张立晔;基于众包的WLAN室内定位技术研究[D];哈尔滨工业大学;2018年

2 提倪（Muhammad Zahid Tunio）;面向众包软件开发的任务分配技术研究[D];北京邮电大学;2018年

3 李绍园;多标记众包学习研究[D];南京大学;2018年

4 宋奕;智能环境下众包物流企业员工组织行为与运作的仿真研究[D];华中科技大学;2018年

5 向为;创意设计柔性众包的方法与应用[D];浙江大学;2017年

6 吴薇;众包竞赛情境下接包者持续参与行为研究：竞争自我效能的作用[D];中国科学技术大学;2018年

7 林素芬;基于众包参与者网络的众包绩效提升研究[D];华侨大学;2015年

8 冯小亮;基于双边市场的众包模式研究[D];武汉大学;2012年

9 饶华铭;人本计算系统中众包数据质量控制方法的改进及其应用研究[D];南京理工大学;2017年

10 庞建刚;众包社区创新的运营机制设计[D];中国科学技术大学;2014年

相关硕士学位论文 前10条

1 陈稼s

本文编号：2667722