Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (11A): 30-38.doi: 10.11896/jsjkx.201200085

• Intelligent Computing • Previous Articles     Next Articles

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).

PDF (PC)

797

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

CLC Number: 

  • 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] WANG Bing, WU Hong-liang, NIU Xin-zheng. Robot Path Planning Based on Improved Potential Field Method [J]. Computer Science, 2022, 49(7): 196-203.
[2] TAN Ren-shen, XU Long-bo, ZHOU Bing, JING Zhao-xia, HUANG Xiang-sheng. Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms [J]. Computer Science, 2022, 49(6A): 795-801.
[3] CHEN Jing-yu, GUO Zhi-jun, YIN Ya-kun. Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm [J]. Computer Science, 2021, 48(6A): 633-637.
[4] DU Wan-ru, WANG Xiao-yin, TIAN Tao, ZHANG Yue. Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles [J]. Computer Science, 2021, 48(2): 250-256.
[5] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[6] CHEN Ji-qing, TAN Cheng-zhi, MO Rong-xian, WANG Zhi-kui, WU Jia-hua, ZHAO Chao-yang. Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field [J]. Computer Science, 2021, 48(11): 327-333.
[7] ZHAO Xiao-wei, ZHU Xiao-jun, HAN Zhou-qing. Hover Location Selection and Flight Path Optimization for UAV for Localization Applications [J]. Computer Science, 2021, 48(11): 345-355.
[8] WANG Zi-qiang, HU Xiao-guang, LI Xiao-xiao, DU Zhuo-qun. Overview of Global Path Planning Algorithms for Mobile Robots [J]. Computer Science, 2021, 48(10): 19-29.
[9] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[10] JIANG Chen-kai, LI Zhi, PAN Shu-bao, WANG Yong-jun. Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm [J]. Computer Science, 2020, 47(8): 272-277.
[11] ZHOU Jun and WANG Tian-qi. Single Departure and Arrival Procedure Optimization in Airport Terminal Area Based on Branch and Bound Method [J]. Computer Science, 2020, 47(6A): 552-555.
[12] ZENG Wei-liang, WU Miao-sen, SUN Wei-jun, XIE Sheng-li. Comprehensive Review of Autonomous Taxi Dispatching Systems [J]. Computer Science, 2020, 47(5): 181-189.
[13] WANG Wei-guang, YIN Jian, QIAN Xiang-li, ZHOU Zi-hang. Realtime Multi-obstacle Avoidance Algorithm Based on Dynamic System [J]. Computer Science, 2020, 47(11A): 111-115.
[14] ZHOU Xin-yue, QIAN Li-ping, HUANG Yu-pin, WU Yuan. Optimization Method of Electric Vehicles Charging Scheduling Based on Ant Colony [J]. Computer Science, 2020, 47(11): 280-285.
[15] SUN Ming-xuan,WENG Ding-en,ZHANG Yu. Time-variant Neurocomputing with Finite-value Terminal Recurrent Neural Networks [J]. Computer Science, 2020, 47(1): 212-218.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.