科研之友
微信
新浪微博
Facebook
分享链接
摘要
作为空间众包研究的核心问题之一，大多数任务分配工作仅仅针对用户和工人两类对象进行匹配，而忽视了任务点位置对分配结果会产生的影响。同时最新的三类对象分配工作都基于欧式空间，和现实路网中的路径计算存在较大误差。因此本文研究面向路网的任务点选址问题，通过给工人和用户指定任务点，在节约工人旅行成本的同时减少用户等待时间。为解决该问题，本文将任务点容量充足时的原问题规约到二分图最大匹配问题并使用KM算法求解；并在不足时规约到最大三维匹配问题并提出分块贪心算法。此外还提出两种优化算法，分别用于快速筛选可用三维匹配对和计算多点对之间的最短路径长度。最后，通过在真实数据集上的实验验证了本文方法的高效性。
- 单位
