基于空间和社会距离的任务分配问题研究

《基于空间和社会距离的任务分配问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ｐ硕士学位论文Ｉ基于空间和社会距离的任务分配问题研究ＲｅｓｅａｒｃｈｏｆＴａｓｋＡｌｌｏｃａｔｉｏｎＰｒｏｂｌｅｍｂａｓｅｄｏｎＳａｔｉａｌａｎｄｐＳｏｃｉａｌＤｉｓｔａｎｃｅ研究生：刘红？齡觀．雜良教授钟领：软件工程钧４“摩Ｉ＝分类号：１０１５３：学校代码ＵＤＣ：密级：硕士学位论文基于空间和社会距离的任务分配问題研究作者姓名：刘红入学年份：２０１３年９月指导教师：孙焕良教授学科专业：软件工程申请学位：工学硕士所在单位：信息与控制工程学院

2、论文提交日期：２０１５年１１月论文答辩日期：２０１５年１２月学位授予日期：２０１６年１月答辩委员会主席：邢伟答辩委员会组成：邢讳陈宁李贵钟辉赵明：刘俊岭论文评阅人声明。论文中取本人声明，所呈交的学位论文是在导师的指导下独立完成的得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果。与我共同工作，也不包括本人为获得其他学位而使用过的材料过的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢＇／荀〇作者签名：／７日期：Ｐ月／Ｘ年学位论文版权使用授权

3、书本学位论文作者和指导教师完全了解沈阳建筑大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权沈阳建筑大学（或其授权机构）可以将学位论又的全部或部分内容编入有关数据库并通过网络提供检索、浏览。（如作者和导师同意论文交流；否则视为不同意。），请在下方签名作者和导师同意网上交流的时间为作者获得学位后：一不限口半年口一年口年半口两年—：作者签名：导师签名日期：：年Ａ月日期硕士研究生学位论文摘要Ｉ摘要一任务分配问题是个被广泛

4、研宄的问题，基于空间距离的任务分配是任务分配问题在基于位置的服务中的典型应用，如快递、售后服务及物流等，现有的空间任务分配问题通常以最小化空间距离代价为目标。一然而，实际应用中存在另类空间任务匹配需求，要求被服务对象与服务者之间存在一定的社会关系。服务者与服务对象的社会关系会影响服务效果，通常紧密的社会关系便于沟通、交流。例如在推销保险时，如果销售人员与客户之间具有紧密的社会关系同时空间距离较近，更容易建立销售人员与客户之间的关系，方便以后的沟通合作。一基于此需求，本文将社会网络关系结合到空间任务匹配问题中，提出了种基于空间

5、和社会距离的任务匹配问题一。该问题的目标是找到个既满足空间距离和社会关系的双重约束又满足成员容量限制且总体代价值最小的任务分配结果。本文将节点间的空间距离和社会距离的加权和作为任务代价度量。基本的匹配过程是计算所有服务对象与服务者间的任务代价，然后选择代价最小的匹配。当服务对象与服务者数量较大时，匹配效率较低。本文将该问题转化为二分图多重最优匹配问题，并对二分图构建方法和匹配方法进行优化。本文提出了四类算法实现二分图多重最优匹配过程，分别为完全二分图上的匹配算法、基于排序的完全二分图的匹配算法、启发式构建二分图的匹配算法和动

6、态建边的匹配算法。其中，完全二分图上的匹配算法是根据所有候选成员与任务之间的社会距离和空间距离构建完全二分图，然后对二分图进行分配以求得准确解，该算法需要对候选成员集合和任务集合进行全遍历，代价较大。观察发现，二分图在匹配中存在大量冗余边，如完全。因此何建立少量边的二分图成为本文的一个研允重点和难点。本文提出了启发式构建二分图的：匹配算法，该算法采用启发式建边策略进行：分图的构建，能够节省建图时间，具有较高二分二的搜索效率，但求解质量难以保证。在图构建完成后，分图分配过程的优化成为了本文另一个扣宄重点和难点。因此本文提出了基

7、于排序的完全二分图的匹配算法是对完全二，在匹配过程中加入了排序分图上的匹配算法中的分配过程进行了优化，从而减少了分配时间。为了能够提高查询精确的解的效率，本文提出了动态建边的匹配算法。本文采用真实的数据集对所提出的算法进行验证，综合评估了各类算法的效率与求解质量。同时，本文还对三种启发式构建二分图的匹配算法的查询结果进行了分析，通过改变不同参数分析最终分配结果的质量。最后，本文设计和实现了基于空间位置和社会关系的服务类任务分配系统。关键词：任务匹配；社会网络；二分图；启发式算法硕士研究生学位论文ＡｂｓｔｒａｃｔＩＩＩ

8、ＡｂｓｔｒａｃｔＴａｓｋａｌｌｏｃａｔｉｏｎｒｏｂｌｅｍｉｓａｗｉｄｅｌｙｓ