Efficient algorithms for trajectory-aware mobile crowdsourcing

• Main Author: HAN, Chung-Kyun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Numerical Analysis and Scientific Computing; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/etd_coll/380; https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1378&context=etd_coll
• Institution: Singapore Management University

Mobile crowdsourcing, a subclass of crowdsourcing dealing with location-specific tasks, is prevalent in our daily life. From sensing urban environment such as noise, air pollution to package delivery, various location-specific tasks are posted on mobile crowdsourcing platforms to tap on the pool of crowdsourced workers. Many digital platforms compete with each other to expand and retain their pool of crowdsourced workers. Comparing with the traditional workforce, crowdsourced workers do not dedicate their time to do tasks fully and have strong spatiotemporal preferences. The ignorance of crowdsourced workers’ mobility patterns and the lack of personalization would lead to crowdsourced workers’ exodus, but the platform companies have overlooked those critical issues. This thesis addresses four trajectory-aware mobile crowdsourcing problems in mobile sensing and crowdsourced deliveries. The first topic introduces a mobile sensing problem. The problem utilizes smartphones carried by users as data mules that collect sensing data from Internet-of-Things (IoTs) by adjusting the transmission range of IoTs. The other three problems deal with last-mile logistics problems taking into account the crowdsourced workers’ mobility patterns. The first last-mile logistics problem addresses a single-agent orienteering problem with spatiotemporal preferences of crowdsourced workers. The second last-mile logistics topic introduces a multi-agentorienteering problem with uncertain mobility patterns. The last trajectory-aware mobile crowdsourcing problem is a variant of the team orienteering problem that utilizes the estimated and aggregated mobility patterns and suggests bundled tasks even before individual workers reveal their trajectory.This thesis has four major contributions. The first contribution is on defining all trajectory-aware mobile crowdsourcing problems formally. Because the four problems involve new mobile crowdsourcing concepts, it is necessary to put significant efforts into modeling the problems. The second is about suggesting efficient algorithms by utilizing the structure of the problems. Specifically, some optimization techniques such as Lagrangian relaxation, column generation, and cutting-plane methods are taken into account to develop efficient solution approaches. The third contribution is that the performance of the suggested algorithms is evaluated in realistic settings. Although there is a tradeoff between computation time and the solution quality, the algorithms’ performance is much better and more acceptable than baselines. The last contribution is on showing the benefits of the new mobile crowdsourcing concepts over the existing systems through simulations.