Online route planning algorithm in spatial crowdsourcing

doi:10.16511/j.cnki.qhdxxb.2020.26.009

Abstract
Figures/Tables
References
Related Articles
Metrics

Download: PDF(2560 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords spatial crowdsourcing online route planning particle swarm optimization road network

Issue Date: 17 June 2020

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	CUI Junyun
	CHEN Di
	YUAN Ye
	MA Yuliang
	WANG Guoren

Cite this article:

CUI Junyun,CHEN Di,YUAN Ye, et al. Online route planning algorithm in spatial crowdsourcing[J]. Journal of Tsinghua University(Science and Technology), 2020, 60(8): 672-682.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2020.26.009 OR http://jst.tsinghuajournals.com/EN/Y2020/V60/I8/672

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

[1]	WANG Xin, LIN Peng, HUANG Haodong, YUAN Jing, QIU Xu, LIU Xin. Scour dynamic properties and online monitoring of offshore wind power foundation[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(7): 1087-1094.
[2]	AN Ruinan, LIN Peng, CHEN Daoxiang, AN Bang, LU Guannan, LIN Zhitao. Temperature gradient monitoring and thermal evolution of a super mass concrete structure[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(7): 1050-1059.
[3]	ZHOU Yingqian, FENG Xiao, YANG Minbo. Synthesis of refinery hydrogen networks considering compressor types[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(5): 723-729.
[4]	WANG Hongping, HU Yanzhu, ZHANG Yufeng, WANG Song. Analyzing the vulnerability of electrified transportation road networks[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(10): 1584-1597.
[5]	LUO Sida, LI Xiangyu, WU Xianyu, YIN Zhiwei, XU Shuai, KANG Liujiang. Modeling resident choices of residence, work locations and commutes in a two-city system for optimal urban design[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(7): 1186-1194.
[6]	YANG Jianfeng, ZHAN Hui, CHEN Liangchao, DOU Zhan. Planning of emergency evacuation routes in densely populated urban areas during earthquakes[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(1): 70-76.
[7]	LIU Huasen, CHEN Ken, WANG Guolei. Optimization of transfer station parameters of a laser tracker based on the particle swarm algorithm for a large part experiencing 3D deformation[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(9): 979-985.
[8]	WANG Feng, ZHOU Yihong, ZHAO Chunju, ZHOU Huawei, CHEN Wenfu, TAN Yaosheng, LIANG Zhipeng, PAN Zhiguo, WANG Fang. Thermal parameter inversion for various materials of super high arch dams based on the hybrid particle swarm optimization method[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(7): 747-755.
[9]	KONG Xiao, LIU Naijia, ZHANG Menghao, XU Mingwei. Analysis of online college teaching data before and after the COVID-19 epidemic[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(2): 104-116.
[10]	DU Xiaochuang, TU Hongbing, LI Ke, ZHANG Jie, WANG Kang, LIU Hemin, LIANG Manchun, WANG Xiangwei. Radionuclide identification method based on a gamma-spectra template library simulated by radial basis function neural networks[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(11): 1308-1315.
[11]	Dingkun YIN,Zhengxia CHEN,Qian LI,Haifeng JIA,Zhengquan LIU,Lei SHEN,Shakeel AHMAD. Influence of rainfall characteristics on runoff control of a sponge reconstructed community in a rainy city[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(1): 50-56.
[12]	SUI Liqi, TIAN Feng, LI Bo, ZENG Yuanfan, TIAN Guangyu, CHEN Hongxu. Nonlinear dynamics analyses of gear shifting with gear vibrations[J]. Journal of Tsinghua University(Science and Technology), 2020, 60(2): 109-116.
[13]	CHAI Yueting, YU Xiao, LIU Zhenming. Design and implement of a public service platform for e-commerce credible transaction guarantee[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(9): 802-807,820.
[14]	FU Xiaodong, LI Jun, LIU Li, YUE Kun, FENG Yong, LIU Lijun. Evaluating online services based on a ranked pairs social choice function[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(8): 715-724.
[15]	LI Shengqiang, TAN Ming, ZHANG Zhanbo. An optimization method of brachistochrone problem with viscous friction and its application in ADS design[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(6): 563-569.

Viewed

Full text

Abstract

Cited

Shared

Discussed