工作者的路径规划问题是空间众包中一个重要的研究内容。当前路径规划问题的研究主要集中在离线情形下，然而在线情形下的路径规划更符合现实需求。因此，该文从众包物流和共享巴士等典型空间众包平台中提取出了一个在线路径规划问题——空间众包中终点固定的在线路径规划问题。首先研究了Euclidean空间上的路径规划问题，提出了基于粒子群的在线粒子群路径规划算法，该算法通过在线追踪最优解来进行路径规划，同时，提出了基于k近邻的在线局部粒子群路径规划算法。还研究了面向路网的路径规划问题，提出了加权最短路径边界索引和路网上的在线局部粒子群路径规划算法。最后，通过真实数据上的大量实验验证了上述算法的有效性和高效性，其中在线局部粒子群路径规划算法拥有更好的效果。
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.
