空间众包中的任务分配算法研究

发布时间：2020-08-25 15:09

【摘要】：随着移动设备的普及以及无线网络资费的快速下降,空间众包作为一种集群众智慧于一身的新型框架,广泛地用于解决和位置相关的问题(如外卖配送)。工人必须实际行驶到任务指定位置才可以完成任务。本文研究空间众包领域的一个重要问题 任务分配问题,即在满足任务和工人双方限制条件的基础上,采用合理的任务分配方案,最大化任务分配数量。目前主流的任务分配方法主要是从特定场景出发,通过近似解算法,逼近最大化任务分配数量的目标。然而,大部分的任务分配算法对场景的限制条件过多,基于贪心策略的近似解算法通常会陷入局部最优的结果中。和以往方法相比,本文主要关注如何使用精确解算法,解决最大化全局任务分配数量的问题,具体研究内容如下:(1)本文着重研究了空间众包中的任务分配问题,介绍了已有的分配方案,描述了具有代表性的各类算法的优势,并分析了其中存在的问题。(2)本文首次研究工作时间约束下的最优任务分配问题,该模式中工人具有不同工作时长,其完成任务的能力和最晚工作时间相关,该问题消除了以往研究中为工人添加的诸多不切实际的限制,更加贴近实际问题。(3)本文创新性地提出了基于树分解技术的精确解算法,根据工人任务重叠情况为工人划定分组,并使用搜索树结构重新组织工人分组,最后提出了启发式深度优先算法搜索全局最优的分配方案。此外,为提升搜索算法的效率,本文提出三种优化策略,极大地减少了搜索的次数。(4)本文通过实验分析了关键参数对本方案效率的影响,并和已有的最佳任务分配方案进行对比,展示出本算法的有效性。
【学位授予单位】：苏州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

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

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

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

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

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

6 郝迎春;祖菊;;人力资源众包服务平台应用研究[J];企业改革与管理;2017年07期

7 张永云;张生太;吴翠花;;嵌入还是卷入:众包个体缘何贡献知识?[J];科研管理;2017年05期

8 张宏树;陈雪波;;众包十年背景下的众筹新闻再考察[J];青年记者;2017年17期

9 任重;;基于万众创新的科研众包研究:定义、理论内涵与启示[J];自然辩证法通讯;2017年04期

10 王晔;;科研众包模式下图书馆支持服务研究[J];图书馆研究;2017年04期

相关会议论文 前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];2015年

9 刘春成;唐松源;Chongyi Wei;Joseph Tucker;;从群众中来,到群众中去:众包与健康传播[A];2015年度中国健康传播大会优秀论文集[C];2015年

10 卢新元;黄河;赵敏;卢泉;;众包模式下基于接包方的风险分析及控制研究[A];第十一届（2016）中国管理学年会论文集[C];2016年

相关重要报纸文章 前10条

1 本报记者 胡军;全民快递时代 安全问题待解[N];中国消费者报;2016年

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

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

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

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

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

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

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

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

10 本报记者 陶力;达达布局同城物流：“跑腿”采用离散式众包模式[N];21世纪经济报道;2017年

相关博士学位论文 前10条

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

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

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

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

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

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

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

8 胡昭阳;众包科学：网络传播语境下的公众参与创新[D];中国科学技术大学;2015年

9 李春华;基于机器学习模型与众包的知识融合方法研究[D];苏州大学;2017年

10 邹凌飞;众包社区成员创造力绩效影响因素分析及其应用研究[D];华中科技大学;2015年

相关硕士学位论文 前10条

1 王梦婧;基于众包的物流配送调度优化方案[D];哈尔滨工业大学;2017年

2 张倩茹;互联网竞赛型众包模式下雇主绩效影响因素与管理策略[D];长安大学;2018年

3 莫小燕;基于众包手机数据的实时路况估计和路径规划研究[D];哈尔滨工业大学;2017年

4 江雨;基于不确定任务环境的众包用户行为分析及调度策略研究[D];华东师范大学;2018年

5 吴永成;基于众包平台针对可达性查询的不确定图清洗研究[D];华东师范大学;2018年

6 章汉铭;基于表示学习的众包服务领域用户消费意图理解技术的研究[D];哈尔滨工业大学;2018年

7 张真铭;科研众包平台双边用户参与行为的影响因素研究[D];太原理工大学;2018年

8 赵敏;众包模式下我国中小企业创新绩效影响研究[D];华中师范大学;2018年

9 艾阔;众包数据提取平台的设计与实现[D];北京交通大学;2018年

10 孙毓鸿;基于众包的CIDP平台出版编撰流程改进研究[D];西安工业大学;2018年

本文编号：2803851