计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 30-38.doi: 10.11896/jsjkx.201200085

• 智能计算 • 上一篇    下一篇

基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法

赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏   

  1. 合肥工业大学管理学院 合肥230009
    过程优化与智能决策教育部重点实验室 合肥230009
  • 出版日期:2021-11-10 发布日期:2021-11-12
  • 通讯作者: 倪志伟(zhwnelson@163.com)
  • 作者简介:729805176@qq.com
  • 基金资助:
    国家自然科学基金(91546108,71521001,71901001);安徽省科技重大专项项目(201903a05020020);安徽省自然科学基金项目(1908085QG298)

Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform

ZHAO Yang, NI Zhi-wei, ZHU Xu-hui, LIU Hao, RAN Jia-min   

  1. School of Management,Hefei University of Technology,Hefei 230009,China
    Key Laboratory of Process Optimization and Intelligent Decision-Making,Ministry of Education,Hefei 230009,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:ZHAO Yang,born in 1996,postgraduate.His main research interests include spatial crowdsourcing and intelligent computing.
    NI Zhi-wei,born in 1963,Ph.D,professor,Ph.D supervisor.His main research interests include artificial intelligence,machine learning and cloud computing.
  • Supported by:
    National Natural Science Foundation of China (91546108,71521001,71901001),Science and Technology Major Special Projects of Anhui Province,China(201903a05020020) and Natural Science Foundation of Anhui Province,China(1908085QG298).

摘要: 针对面向空间众包平台的多工作者多任务路径规划问题,以求解时间成本和路程成本最小的全局最优路径规划方案为目标,提出了基于改进狮群进化算法的路径规划方法。首先,结合现实问题场景,提出带有任务开始点和结束点的路径规划模型;其次,借鉴狮群进化算法的思想,改进狮群智能行为,引入驱逐行为,针对求解问题设计染色体编码方式、交叉、变异操作等,提出了面向空间众包平台的多工作者多任务路径规划的改进狮群进化算法;最后,运用改进狮群进化算法求解面向空间众包平台的多工作者多任务路径规划模型,并根据真实数据集制作问题算例进行测试。实验结果表明了算法的可用性和有效性。

关键词: 空间众包, 路径规划, 狮群进化算法

Abstract: In order to solve the problem of multi-worker and multi-task path planning for spatial crowdsourcing platform and aiming at solving the global optimal path planning scheme with the minimum time cost and distance cost,a path planning method based on the improved lion evolutionary algorithm is proposed.Firstly,a path planning model with task start and end points is proposed based on realistic problem scenarios.Secondly,by referring to the algorithm idea of lion evolutionary algorithm,the intelligent behavior of lions is improved,the expulsion behavior is introduced,and the chromosomal coding mode,crossover,mutation operation,etc.are designed for solving the problem.An improved lion evolutionary algorithm for multi-worker and multi-task path planning based on the spatial crowdsourcing platform is proposed.Finally,the improved lion evolutionary algorithm is used to solve the multi-worker and multi-task path planning model of the spatial crowdsourcing platform,and the problem is tested by making an example based on the real data set.The experimental results show the availability and effectiveness of the algorithm.

Key words: Lion evolutionary algorithm, Path planning, Spatial crowdsourcing

中图分类号: 

  • TP182
[1]GAO D,TONG Y,SHE J,et al.Top-k Team Recommendation and Its Variants in Spatial Crowdsourcing[J].Data Science and Engineering,2017,2(2):136-150.
[2]ZHANG C,GUO Y C,LIN P G,et al.Location prediction-based task assignment in spatial crowdsourcing[J].Journal of Nanjing University(Natural Science),2018,54(2):471-480.
[3]TONG Y X,YUAN Y,CHENG Y R,et al.Survey on Spatiotemporal Crowdsourced Data Management Techniques[J].Journal of Software,2017,28(1):35-58.
[4]TO H,SHAHABI C,KAZEMI L.A Server-Assigned SpatialCrowdsourcing Framework[J].ACM Transactions on Spatial Algorithms & Systems,2015,1(1):1-28.
[5]DENG D,SHAHABI C,DEMIRYUREK U.Maximizing theNumber of Worker's Self-Selected Tasks in Spatial Crowd-sourcing[C]//ACM Sigspatial International Conference on Advances in Geographic Information Systems.New York:Association for Computing Machinery,2013:324-333.
[6]ZHAO T H,TU W,LUAN Z L,et al.Dynamic Task Schedule Algorithm of Spatial Crowdsourcing for the Worker[J].2019,44(2):41-44.
[7]NIE X C,ZHANG Y,YU D H,et al.Spatial Crowdsourcingtask allocation algorithm for global optimization[J].Journal of Computer Applications,2020,40(7):1950-1958.
[8]TONG Y,ZHOU Z,ZENG Y,et al.Spatial crowdsourcing:asurvey[J].The VLDB Journal,2020,29(1):217-250.
[9]COSTA C F,NASCIMENTO M A.In-Route Task Selection in Crowdsourcing[C]//Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York,NY,USA:Association for Computing Machinery,2018:524-527.
[10]CUI J Y,CHEN D,YUAN Y,et al.Online route planning algorithm in spatial crowdsourcing[J].Journal of Tsinghua University(Science and Technology),2020,60(8):672-682.
[11]SHE J,TONG Y,CHEN L.Utility-aware social event-participant planning[C]//Proceedings of the 2015 ACM International Conference on Management of Data.2015:1629-1643.
[12]MA S,ZHENG Y,WOLFSON O.T-share:A large-scale dynamictaxi ridesharing service[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE).IEEE,2013:410-421.
[13]MENG F,ZHANG S,ZHENG X,et al.Task AssignmentMethod in Spatial Crowdsourcing Based on Graph Search[C]//2019 IEEE 21st International Conference on High Performance Computing and Communications;IEEE 17th International Conference on Smart City;IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS).IEEE,2019:2623-2629.
[14]TAO Q,ZENG Y,ZHOU Z,et al.Multi-Worker-Aware TaskPlanning inReal-Time Spatial Crowdsourcing[M]//Database Systems for Advanced Applications.Cham:Springer,2018:301-317.
[15]GAO D,TONG Y,JI Y,et al.Team-Oriented Task Planning in Spatial Crowdsourcing[C]//Asiapacific Web.Cham:Springer,2017:41-56.
[16]AN Y,QIN K,LUO G C.Survey on location privacy preservation technology in spatial crowdsourcing[J].Application Research of Computers,2018,35(8):2241-2244,2264.
[17]LI Y,JIA M D,YANG W Y,et al.Optimal Task Assignment Algorithm Based on Tree-Decouple in Spatial Crowdsourcing[J].Journal of Software,2018,29(3):824-838.
[18]SONG T S,TONG Y X,WANG L B,et al.Online Task Assignment for Three Types of Objects under Spatial Crowdsourcing Environment[J].Journal of Software,2017,28(3):611-630.
[19]ZHANG Y Z,XU T Z,ZHENG J S,et al.Solving Emergency Logistics Problem with Uncertain Urgency Based on a Hybrid Genetic Algorithm[J].Journal of Systems Science and Mathematical Sciences,2020,40(4):714-728.
[20]RAJAKUMAR B R.The Lion's Algorithm:A New Nature-Inspired Search Algorithm[J].Procedia Technology,2012,6:126-135.
[21]TONG R.Study on takeaway distribution routing optimization based on crowdsourcing mode[D].Xi'an:Xi'an University of Technology,2019.
[22]HARVEY I.The Microbial Genetic Algorithm[C]//EuropeanConference on Artificial Life.Berlin:Springer,2009:126-133.
[1] 王兵, 吴洪亮, 牛新征.
基于改进势场法的机器人路径规划
Robot Path Planning Based on Improved Potential Field Method
计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[2] 杨浩雄, 高晶, 邵恩露.
考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题
Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery
计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[3] 谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生.
海上风电场通用运维路径规划模型优化及仿真
Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms
计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300
[4] 沈彪, 沈立炜, 李弋.
空间众包任务的路径动态调度方法
Dynamic Task Scheduling Method for Space Crowdsourcing
计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[5] 陈镜宇, 郭志军, 尹亚昆.
基于混合算法的智能割草机全遍历路径规划及其系统设计
Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm
计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002
[6] 杜婉茹, 王潇茵, 田涛, 张越.
面向未知环境及动态障碍的人工势场路径规划算法
Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles
计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170
[7] 郭启程, 杜晓玉, 张延宇, 周毅.
基于改进鲸鱼算法的无人机三维路径规划
Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm
计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[8] 曹波, 陈锋, 成静, 李华, 李永乐.
基于全向路口模型的非结构化道路重复节点路径规划
Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search
计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193
[9] 陈继清, 谭成志, 莫荣现, 王志奎, 吴家华, 赵超阳.
基于人工势场的A*算法的移动机器人路径规划
Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field
计算机科学, 2021, 48(11): 327-333. https://doi.org/10.11896/jsjkx.200900170
[10] 赵晓薇, 朱小军, 韩周卿.
面向定位应用的无人机的悬停位置和飞行路径优化
Hover Location Selection and Flight Path Optimization for UAV for Localization Applications
计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105
[11] 王梓强, 胡晓光, 李晓筱, 杜卓群.
移动机器人全局路径规划算法综述
Overview of Global Path Planning Algorithms for Mobile Robots
计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114
[12] 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊.
智能3D打印路径规划算法
Intelligent 3D Printing Path Planning Algorithm
计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[13] 姜辰凯, 李智, 盘书宝, 王勇军.
基于改进Dijkstra算法的AGVs无碰撞路径规划
Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm
计算机科学, 2020, 47(8): 272-277. https://doi.org/10.11896/jsjkx.190700138
[14] 曾伟良, 吴淼森, 孙为军, 谢胜利.
自动驾驶出租车调度系统研究综述
Comprehensive Review of Autonomous Taxi Dispatching Systems
计算机科学, 2020, 47(5): 181-189. https://doi.org/10.11896/jsjkx.190400031
[15] 王伟光, 尹健, 钱祥利, 周子航.
基于动态系统的多障碍实时规避算法
Realtime Multi-obstacle Avoidance Algorithm Based on Dynamic System
计算机科学, 2020, 47(11A): 111-115. https://doi.org/10.11896/jsjkx.200800068
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!