基于0-1型整数规划的任务打包方案研究

宋凯鲲，唐 璇，孙至宾

（1. 华北理工大学机械工程学院，河北 唐山 063200；2. 华北理工大学管理学院，河北 唐山 063200；3. 华北理工大学以升创新基地，河北 唐山 063200）

0 引言

“拍照赚钱”APP是一种典型的基于移动互联网的自助式劳务众包平台[1-5]，为企业提供各种商业检查和信息搜集，相比传统的市场调查方式可以大大节省调查成本，而且有效地保证了调查数据真实性，缩短了调查的周期。在实际情况下，多个任务可能因为位置比较集中，导致用户会争相选择，一种考虑是将这些任务联合在一起打包发布。在这种考虑下，就需要修改原本的定价模型。首先经过将会员的注册信息的经纬度地点导入 XGeocoding[6-8]软件中进行地点的分析，将具有偶然性和没有代表性的点去掉，然后将会员注册的信息与任务地点的信息在散点图中进行对照，分成任务未完成点，任务完成点和会员注册点。由于数据庞大，便只选择了4个具有代表性的地点，最后将定价的合理性和不合理性分别对应二进制数中的1,0，使用0-1型整数规划模型建立其相应的模型，并利用lingo软件求出最优解，定出最终的打包任务的方案。

1 数据处理

将会员的注册信息的经纬度地点导入 XGeocoding软件中进行地点并进行数据分析，将具有偶然性和没有代表性的点去掉，比如会员注册地点离任务地点距离较远的点，会员分布状况稀疏的点。然后将会员注册的信息与任务地点的信息在散点图中进行对照，分成任务未完成点，任务完成点和会员注册点，由于数据量庞大，便只选取广州，深圳，佛山，东莞四处地点作为代表性地点。

2 建立模型

“拍照赚钱”APP的任务打包的选择是由会员所得的佣金、时间的耗费和路程的远近所决定的。而任务打包选择为双向选择，会员是否抢单成功是由会员的信誉值和任务选择的限额决定的，只有双方对应条件双向满足才能下单成功。筛选距离最近的点打包，将完成任务点与未完成任务点就近打包，尽可能让会员注册信息点覆盖打包后的任务点。以就近原则，吸引更多的会员抢单，此“拍照赚钱”APP的根本目的是要将任务全部分配出去，用合理的定价更高效的完成任务，从而进行线性规划，得出最优解的范围。其中两层目标函数的约束函数都为会员的信誉程度和所选任务的限额。

2.1 第一层目标函数，更注重定价的合理性

将定价的合理性和不合理性分别对应二进制数中的 1，0，使用 0-1型整数规划模型[9-11]建立其相应的模型。

2.2 第二层目标函数，更注重任务的完成率

将完成率的高和低分别对应二进制数中的1，0，使用0-1型整数规划模型建立其相应的模型。

利用lingo软件求出最优解，定出最终的打包任务的方案。

东莞市情况较为特殊，在当地注册的会员较多，且任务完成率达到了100%，任意任务打包都会促进“拍照赚钱”APP在当地的推广，所以在对东莞市任务定价时可以考虑打包降低一定的佣金。将由于降低佣金而剩余的本金用于别的地方提高定价。

通过任务打包，将以前没有完成任务的点全部覆盖，促使会员选择这些未完成的任务。通过这种方法，我们不需要改变原有的定价模型[12-15]，但是在定价时，打包任务的佣金不仅仅是简单的打包的所有任务的佣金相加，而是根据一个打包任务中完成任务点和未完成任务点的比例来计算最终的佣金，最后将佣金浮动范围控制在70%到130%之间。

图1 完成的任务，未完成的任务和会员注册信息的散点图Fig.1 complete tasks, unfinished tasks and a scatter plot of member registration information

表1 广州市任务打包方案Tab.1 Guangzhou mission package

表2 深圳市任务打包方案Tab.2 Shenzhen mission package

表3 佛山市任务打包方案Tab.3 Foshan mission package

3 结论

本文将会员的注册信息的经纬度地点导入XGeocoding软件中进行地点分析，将具有偶然性和没有代表性的点去掉，然后将会员注册的信息与任务地点的信息在散点图中进行对照，分成任务未完成点，任务完成点和会员注册点。将定价的合理性和不合理性分别对应二进制数中的1,0，使用0-1型整数规划模型建立其相应的模型，并利用lingo软件求出最优解，定出最终的打包任务的方案，通过打包任务这种方式，能够激发会员完成任务的积极性，能够覆盖以前没有完成任务的点，能够促进任务完成的效率，对“拍照赚钱”APP的推广也有很大帮助。

[1] 钟耕深. 基于众包的商业模式优化[A]. 中国管理现代化研究会. 第五届(2010)中国管理学年会——组织与战略分会场论文集[C]. 中国管理现代化研究会, 2010: 6.

[2] 孟韬, 张媛, 董大海. 基于威客模式的众包参与行为影响因素研究[J]. 中国软科学, 2014, (12): 112-123.

[3] 解倩男. 基于价值网的众包商业模式评价体系研究[D].西安电子科技大学, 2015.

[4] 张志强, 逄居升, 谢晓芹, 周永. 众包质量控制策略及评估算法研究[J]. 计算机学报, 2013, 36(8): 1636-1649.

[5] 陈家银. 猪八戒众包平台数据分析与众包模式设计[D].大连理工大学, 2016.

[6] 龚峰. 基于Geocoding和瓦片地图引擎的生活信息服务系统的开发[D]. 上海交通大学, 2012.

[7] 马云强, 张军. 基于Web Geocoding的三维GIS快速定位方法研究[J]. 云南地理环境研究, 2009, 21(6): 93-97.

[8] 江洲, 李琦. 地理编码(Geocoding)的应用研究[J]. 地理与地理信息科学, 2003(3): 22-25.

[9] 李艳艳, 李兴斯. 求解线性0-1规划的一种连续化方法[J].大连理工大学学报, 2009, 49(2): 299-302.

[10] 王军, 李端. 多项式0-1规划中隐枚举算法的改进及应用[J]. 系统工程理论与实践, 2007(3): 21-27+35.

[11] 王智, 朱凤书. 灌溉渠系流量最优调配的0-1规划模型[J].灌溉排水, 1992(3): 8-13.

[12] 李倩. 资产定价理论模型分析及中国的应用研究[D]. 华中科技大学, 2015.

[13] 吴熠. 条件资产定价模型与定价因子的研究[D]. 浙江工商大学, 2012.

[14] 纪键. 权证定价模型有效性检验[D]. 对外经济贸易大学, 2006.

[15] 车雯雯. 电子商务C2C平台定价模型及盈利影响因素研究[D]. 上海交通大学, 2010.