Problème
Vous êtes le responsable des sports d’une chaine de télévision. À l’approche d’une grande compétition sportive, vous souhaitez couvrir l’ensemble des épreuves de cette compétition avec un minimum de journalistes.
Vous connaissez les emplacements des sites où ont lieu les épreuves, les temps de trajet et les distances entre les sites, ainsi que les dates et heures de début et de fin des épreuves (pour plus d’infos : cf. article « EURODECISION se prend aux jeux », ou nous contacter pour obtenir les données).
Combien allez-vous envoyer de journalistes sur le terrain pour couvrir l’intégralité des épreuves ?
Pour répondre à cette question, vous pourrez :
- Proposer une modélisation sous la forme d’un problème d’optimisation. (Indice : plusieurs problèmes d’optimisation connus peuvent être utilisés)
- Proposer un algorithme de résolution efficace.
- Bonus : Une fois le nombre de journalistes à envoyer connu, vous souhaitez minimiser la distance totale parcourue par les journalistes. Adapter l’algorithme proposé en conséquence.
NB : Vous ne savez pas modéliser mais souhaitez participer ? Répondez à la question suivante : pourquoi la réponse à ce casse-tête est-elle forcément supérieure à 25 journalistes ?
Méthodes de résolution
Méthode n°1 : Résolution avec LP-Scheduler
Ce problème peut être assimilé à un problème d’affectation de ressources à des tâches. Chaque tâche est une épreuve, on impose les instants où les tâches doivent être effectuées et on prend en compte les temps de trajets entre les différentes tâches. L’objectif est de minimiser le nombre de ressources nécessaires pour réaliser toutes les tâches. Nous avons utilisé notre outil d’optimisation de planification de tâches LP-Scheduler.
Dans cette modélisation, un journaliste correspond à une ressource et on obtient avec LP-Scheduler une solution où 29 journalistes sont nécessaires pour couvrir l’ensemble des épreuves.
Méthode n°2 : Résolution avec SCOP Routing
Il est également possible de modéliser ce problème sous la forme d’un problème de tournées de véhicules avec fenêtres de temps (VRPTW). Dans cette modélisation, un véhicule correspond à un journaliste, un site à visiter correspond à une épreuve sportive, la fenêtre de temps pour l’arrivée à chaque site représente le moment du début de l’épreuve associée, enfin, le temps de service à chaque site est la durée de l’épreuve associée. Minimiser le nombre de journalistes à envoyer revient donc à minimiser le nombre de véhicules dans le VRPTW (ainsi que la distance totale parcourue).
Nous avons utilisé notre composant SCOP Routing, permettant de résoudre le problème modélisé sous la forme d’un VRPTW. On obtient également une solution dans laquelle 29 journalistes sont nécessaires pour couvrir toutes les épreuves.
Bonus : borne inférieure pour le nombre de journalistes
Tout simplement en analysant les données, i.e. le planning des épreuves, on peut s’apercevoir qu’il existe un instant où 25 épreuves sont en cours. On en déduit qu’il faudra 25 journalistes assistant à une épreuve à cet instant, et donc au moins 25 pour couvrir toutes les épreuves.