4

Les systèmes de marché crowdsourcing (CMS) sont des plateformes qui permettent à une personne de publier des tâches afin qu’elles soient accomplies par d’autres. Récemment, un type de CMS est apparu dans lequel des tâches spatio-temporelles doivent être accomplies dans une fenêtre de temps et un lieu précis. Dans cet article, nous présentons le problème de recommandation de trajectoires utiles (PRTU), qui permet à une personne en situation de mobilité d’accomplir des tâches spatio-temporelles pour lesquelles elle montre une grande affinité et/ou aptitude, sans compromettre son arrivée à destination dans les temps. Nous démontrons que le PRTU est NP-complet (dans sa version décisionnelle) et proposons, pour y répondre, un algorithme exact accompagné de cinq heuristiques d’approximation. En outre, nous proposons une architecture de référence pour mettre en œuvre la recommandation de ces trajectoires dans un CMS réel. Enfin, nos expérimentations montrent que l’algorithme exact proposé peut être une solution acceptable pour certaines instances de PRTU et que les heuristiques constituent des alternatives plus performantes qui permettent d’attendre jusqu’à 77 % de rendement optimal.

Crowdsourcing market systems (CMS) are platforms that allow one to publish tasks in order to be accomplished by others. Recently, a type of CMS has appeared where spatiotemporal tasks are to be accomplished by persons at a specific time-window and location. We present the Useful Trajectories Recommendation Problem (PRTU), that allows a person to accomplish tasks he has affinity and/or ability to, without compromising his arrival in time at the destination. We prove that PRTU is NP-complet (in its decision version) and propose an exact algorithm and five heuristics for it. Further, we propose a reference architecture for the deployment of the recommendation of such trajectories in a CMS. Our experiments have shown that our algorithm can be feasible solution for some instances of PRTU and that, otherwise, the heuristics are alternatives that run faster and can provide up to 77% of the optimal utility.