Online route planning algorithm in spatial crowdsourcing
CUI Junyun1, CHEN Di1, YUAN Ye1, MA Yuliang1, WANG Guoren2
1. School of Computer Science and Engineering, Northeastern University, Shenyang 110000, China; 2. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
Abstract：Worker route planning is an important spatial crowdsourcing research topic. Previous research on route planning has mainly focused on offline situation. However, online situation are more relevant to actual needs. Therefore, this study analyzes an online route planning problem extracted from a typical spatial crowdsourcing platform involving crowdsourcing logistics and shared bus, which is called the online route planning problem with fixed endpoints in spatial crowdsourcing. The first step is to analyze the route planning in the Euclidean space using a particle swarm optimization method. The algorithm plans the route by tracking the optimal solution online. A local particle swarm optimization method for online route planning is also used based on the k nearest neighbours. The route planning algorithm is then applied to a road network using weighted shortest path boundary indexing. The effectiveness and efficiency of this algorithm are verified through extensive experiments on real datasets with the local particle swarm optimization method for online route planning showing better performance than the compared method.
[1] BAKAS I, DRAKOULIS R, FLOUDAS N, et al. A flexible transportation service for the optimization of a fixed-route public transport network[J]. Transportation Research Procedia, 2016, 14:1689-1698. [2] TONG Y X, SHE J Y, DING B L, et al. Online mobile micro-task allocation in spatial crowdsourcing[C]//Proceedings of 2016 IEEE 32nd International Conference on Data Engineering. Helsinki, Finland:IEEE, 2016:49-60. [3] TONG Y X, WANG L B, ZHOU Z M, et al. Flexible online task assignment in real-time spatial data[J]. Proceedings of the VLDB Endowment, 2017, 10(11):1334-1345. [4] TONG Y X, SHE J Y, DING B L, et al. Online minimum matching in real-time spatial data:Experiments and analysis[J]. Proceedings of the VLDB Endowment, 2016, 9(12):1053-1064. [5] SONG T S, TONG Y X, WANG L B, et al. Trichromatic online matching in real-time spatial crowdsourcing[C]//Proceedings of 2017 IEEE 33rd, International Conference on Data Engineering. San Diego, USA:IEEE, 2017:1009-1020. [6] SUN D, XU K, CHENG H, et al. Online delivery route recommendation in spatial crowdsourcing[J]. World Wide Web, 2019, 22(5):2083-2104. [7] BJELDE A, DISSER Y, HACKFELD J, et al. Tight bounds for online TSP on the line[C]//Proceedings of the Twenty-Eighth ACM-Siam Symposium on Discrete Algorithms. Barcelona, Spain:ACM, 2017:994-1005. [8] AUSIELLO G, FEUERSTEIN E, LEONARDI S, et al. Algorithms for the online-travelling salesman[J]. Algorithmica, 2001, 29(4):540-581. [9] KALYANASUNDARAM B, PRUHS K. On-line weighted matching[C]//Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco, USA:Society for Industrial and Applied Mathematics, 1991. [10] CHENG P, XIN H, CHEN L. Utility-aware ridesharing on road networks[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Chicago, USA:ACM, 2017:1197-1210. [11] TONG Y X, ZENG Y X, ZHOU Z M, et al. A unified approach to route planning for shared mobility[J]. Proceedings of the VLDB Endowment, 2018, 11(11):1633-1646. [12] HUANG L, WANG K P, ZHOU C G, et al. Particle swarm optimization for traveling salesman problems[J]. Journal of Jilin University (Science Edition), 2003, 41(4):477-480. [13] FAKCHAROENPHOL J, RAO S. Planar graphs, negative weight edges, shortest paths, and near linear time[J]. Journal of Computer and System Sciences, 2006, 72(5):868-889. [14] SAMET H, SANKARANARAYANAN J, ALBORZI H. Scalable network distance browsing in spatial databases[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Vancouver, Canada:ACM, 2008:43-54. [15] ZHANG Y F, WANG G R. SPTI:Efficient answering the shortest path query on large graphs[C]//Proceedings of 2013 IEEE International Congress on Big Data. Santa Clara, USA:IEEE, 2013:195-202. [16] LAWLER E L, LENSTRA J K, KAN A H G R, et al. The traveling salesman problem:A guided tour of combinatorial optimization[J]. Journal of the Operational Research Society, 1986, 37(5):535-536.
2020, Vol. 60 
