SMF-GA: Optimized Multitask Allocation Algorithm in Urban Crowdsourced Transportation. (17th March 2019)

• Record Type: Journal Article
• Authors: Wang, Pengfei; Yu, Ruiyun
• Other Names: Luo Tony T. Academic Editor.
• Is Part Of: Wireless communications and mobile computing. Volume 2019(2019)
• Publication Date: 2019-03-17
• Subjects: Wireless communication systems -- Periodicals; Mobile communication systems -- Periodicals; 621.38205
• DOI: 10.1155/2019/8035167
• Languages: English
• ISSNs: 1530-8669

Abstract

Abstract : Urban crowdsourced transportation, which can solve traffic problem within city, is a new scenario where citizens share vehicles to take passengers and packages while driving. Differing from the traditional location based crowdsourcing system (e.g., crowdsensing system), the task has to be completed with visiting two different locations (i.e., start and end points), so task allocation algorithms in crowdsensing cannot be leveraged in urban crowdsourced transportation directly. To solve this problem, we first prove that maximizing the crowdsourcing system's profit (i.e., maximizing the total saved distance) is an NP-hard problem. We propose a heuristic greedy algorithm called Saving Most First (SMF) which is simple and effective in assigning tasks. Then, an optimized SMF based genetic algorithm (SMF-GA) is devised to jump out of the local optimal result. Finally, we demonstrate the performance of SMF and SMF-GA with extensive evaluations, based on a large scale real vehicle traces. The evaluation with large scale real dataset indicates that both SMF and SMF-GA algorithms outperform other benchmark algorithms in terms of saved distance, participant profits, etc.