基于经纬度范围的多点任务打包算法

朱亚强

摘 要：本文以拍照赚钱任务为例，研究了一种基于经纬度范围的多点任务打包算法。在解决“拍照赚钱”任务的定价问题时，只要给该算法提供任务的位置信息、任务包中的任务数和任务包筛选范围，便能自动生成满足限定条件的打包方案，其中包含有任务包内各个任务的具体位置，具有执行速度快、计算结果准确的优点。该算法的思想可以作为解决与大量详细位置信息有关问题的雏形，推广至外卖配送、快递员送件等行业。

关键词：数据处理 算法 打包 位置 经纬度

中图分类号：TP319 文献标识码：A 文章编号：1672-3791（2018）04（a）-0022-02

1 问题背景

“拍照赚钱”是一种基于Internet的自助劳务众包平台，能够满足公司对信息收集的需求。该平台的用户通过拍取公司需要的照片获取报酬。平台中的任务定价是核心因素。而将一定区域内的任务打包发布，在一定程度上能提升用户接受任务的积极性以及降低任务的执行难度。

2 模型的建立

实际生活中，若多个任务的位置相对集中，可以考虑将这些任务联合在一起打包发布。

众包平台将任务进行打包，首先对会员的任务限额有一定要求，新会员起初只具有一次任务限额，随着会员完成任务的增多，信誉值会提高，任务预定限额也有所增加，且任务可预定时间提前。只有任务限额大于等于任务包中任务数量的会员才有可能接受任务包。同时，考虑到会员若在领取任务包后没有完成任务，会对众包平台造成巨大经济损失与时间浪费，故众包平台基于各会员信誉值必然会设定一定的门槛，规避相对不讲信誉的会员，以减少任务未完成的可能性。

3 会员与任务点的平均距离的确定

由于任务打包的前提是各任务的位置相对集中，以此作为任务包。我们可以以一个任务点为中心划定边长为3.22km的正方形区域来研究任务包的所在位置。若该正方形区域内存在至少5个任务，则可以认为该区域任务的位置相对集中，可以作为任务包。将上述条件作为标准，使用Matlab对附件一中每一个任务点进行筛选，从第一个任务点开始进行方形区域的划分，如果满足在方形区域内包括中心任务点有不少于5个任务点，则根据纬度与中心任务点相差的大小进行打包，如果打包成功，那么算法到达任务包内其余任务的数据时会自动跳过，继续寻找下一个符合条件的任务包。

对于已结束任务，通过长度换算与地图比例尺转换，在误差允许范围内，认为可以在一个任务位置纬度值加减0.015°、经度值加减0.015°的近似方形区域内来研究任务包的所在位置。利用任务包算法打包后用欧几里得距离公式求出具有领取任务包资格的会员中5个任务的平均位置与任务包中心任务位置的平均距离，作为打包模式下会员与任务的平均距离 。

4 任务包定价的确定

众包平台提供打包任务，不仅仅为了方便会员的任务接受，同时也为提高自身的利润。由于对于会员而言，完成任务包所付出的劳动成本比一个个完成任务所付出的劳动成本降低，所以众包平台设定的任务包定价会略小于各任务单价之和，即牺牲一定的任务单价，来提高任务完成数，从而获得更高的利润。任务包的定价，可以由各任务单价之和，经过任务数目修正系数修正而得到。

5 任务包算法

根据运算原理写出了一个Matlab算法。算法的具体实现思路如下：每个任务数据有两个默认为0标志位A和B，A表征该任务是否被选中（包含在某个打包组中或无法打包自成一组），在某任务选择打包对象时依靠这个指标判断是否可以将该对象纳入打包组，程序完成后所有任务该标志位都应为1；B表征该任务是否被打包，若被打包则将该任务折叠，不参与后续计算。算法采用两层嵌套循环，第一层循环根据A判断是否进行第二层循环来形成打包组，若A位为0则进行第二层循环，A位为1则跳过该任务，继续判断后面的任务是否满足条件。在生成以某个任务为队头的打包组时，队头任务的A位置1，循环该任务之后所有任务，A位为0且满足范围条件的任务即被选入该打包组，被选中的任务A、B位置1，一旦该打包组中的任务数达到规定数量，跳出循环，继续生成下一个打包组。若循环完成后打包组内的任务数没有达到规定的数目，则将被选中的任务A、B位置0。无论是否形成打包组，该队头任务A位置回0。算法生成的最终结果中，所有任务的A位均为1，B位为1表示该任务参与以其他任务为队头的打包组，将被折叠，不参与后续计算，B位为0的数据为打包队头任务（即代表一个打包组）或不参与任何打包组的任务。

6 考虑打包模式后的任务完成情况

已知任务完成情况可以通过任务定价和会员与任务点之间的距离利用Logistic回归模型进行估计分析。不考虑任务打包时，任务定价指的是各个任务的单价，各个任务的对于会员也没有门槛要求，每个会员可以任意接各个任务。但是，当我们考虑到任务打包发布时，首先就对任务进行了分类：可打包的任务以及不可打包的任务。不可打包的任务依旧按照原本的单价进行发布，而可以打包的任务将进行处理后以任务包定价发布。

除了打包后任务的定价发生了变化，任务也提高了对会员的要求，打包发布的任务包任务限额小于5的会员将没有领取资格，相应数据舍弃，假定信誉值50为众包平台对低信誉会员设定的门槛，则信誉值在50以下的会员也没有资格领取任务包，相应数据舍弃。

在综合考虑任务（包）定价、会员能否接受任务包和打包模式下会员与任务的平均距离后，通过Logistic回归模型的预测，我们发现优化定价模型下的任务完成度达到了91.86%，高于原本定价下以及优化定价但不打包时的任务完成度。

7 结语

当实施任务打包策略时，由于任务包所包含的各个任务之间的距离很近，并且多个任务合并发布具有更高的任务定价，所以，这两点可以对会员接受任务产生正向激励，会员会更愿意去接受高回报的打包任务，这样就提高了任务的完成度。任务包的对会员设定的门槛使得只有那些信誉良好的会员能够申请任务包，同样会得到更好的任务完成情况。由此看来，任务打包发布后的估测结果与实际情况是相符合的。

参考文献

[1] 司守奎，孙璽菁，数学建模算法与应用[M].北京：国防工业出版社，2008.

[2] K-means聚类算法[EB/OL]，https：//wenku.baidu.com/view/cdfc8e84a8114431b80dd88a.html？qq-pf-to=pcqq.group，2017.9.16.

[3] 王千，王成，冯振元，等.K-means聚类算法研究综述[J].电子设计工程，2012，20（7）：21-24.

[4] 根据两点经纬度计算距离[EB/OL]，http：//blog.csdn.net/yl2isoft/article/details/16367901，2017.9.16.

[5] 黎珍惜，黎家勋.基于经纬度快速计算两点间距离及测量误差[J].测绘与空间地理信息，2013，36（11）：235-237.

[6] 黄兴柱.基于多元logistic回归模型的房地产预警研究[D].济南大学，2012.

[7] Logistic回归原理及公式推导[EB/OL]，http：//blog.csdn.net/ariessurfer/article/details/41310525，2017.9.16.

[8] 模糊综合评价模型[EB/OL]，http：//www.doc88.com/p-99853 6159065.html，2017.9.17.