ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Document Numérique

1279-5127
 

 ARTICLE VOL 19/1 - 2016  - pp.103-126  - doi:10.3166/DN.19.1.103-126
TITRE
Recommandation opportuniste de trajectoires pour l’accomplissement de tâches dans les systèmes crowdsourcing

TITLE
Recommendation of trajectories for the accomplishment of tasks in crowdsourcing

RÉSUMÉ

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



ABSTRACT

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 spatio- temporal 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.



AUTEUR(S)
André SALES FONTELES, Sylvain BOUVERET, Jérôme GENSEL

MOTS-CLÉS
ordonnancement de tâches spatio-temporelles, recommandation de tâches

KEYWORDS
spatial task assignment, task recommendation, spatial crowdsourcing.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (801 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier