Online Many-to-One Task Assignment with Enhanced HST over Time-Dependent Road Networks

With the widespread adoption of dynamic task assignment in sharing economy applications, the online task assignment problem has attracted more and more research attention. Minimizing the total travel distance is a key objective in online task assignment problems. However, real-world ridesharing problems introduce two major challenges: (1) Many-to-One Assignments, where multiple tasks are assigned to a single worker; and (2) Time-Dependent Road Networks, where task assignments must consider dynamic spatiotemporal factors like traffic and route updates. Existing research has not simultaneously addressed both challenges. In this paper, we propose the OMoTA-TD problem. Specifically, given a set of workers and a set of tasks who dynamically appear one by one on time-dependent road networks, the OMoTA-TD problem is to find the assignment with minimum total travel cost following that once a task appears, it must be immediately matched to a worker whose capacity is not yet full. We prove the problem is NP-hard and there is no polynomial-time algorithm with constant competitive ratio for the OMoTA-TD problem. Then, we propose a greedy baseline solution and an enhanced version of HST, called HST-TD, which simultaneously handles time-dependent road networks and many-to-one assignment scenarios. Subsequently, we propose an efficient heuristic algorithm based on HST-TD. Finally, extensive experiments on real datasets demonstrate that our proposed solutions significantly outperform both the baseline algorithm and the existing state-of-the-art algorithm in efficiency while ensuring effectiveness.