Impact de la granularité spatio-temporelle des données sur l'optimisation des tournées de livraison en ville *

National audienceL'optimisation des tournées de livraisons se ramène essentiellement à un problème de voyageur de commerce (TSP) dans un graphe où les sommets correspondent aux points à livrer, et les coûts des arcs aux temps de trajet entre deux points. Le TSP dépendant du temps (TD-TSP) est une extension du TSP dans laquelle le coût d'un arc dépend de l'heure de départ du noeud d'origine. Cette extension est particulièrement pertinente dans un contexte urbain, car les vitesses de déplacement varient en fonction de l'heure de la journée. Les fonctions de coût dépendantes du temps sont construites à partir de données issues de capteurs, et nous pouvons considérer pour cela différents niveaux de granularité temporelle (fréquence des mesures considérée) et spatiale (nombre et positionnement des capteurs dans le réseau routier). L'objectif de cet article est d'étudier l'impact de la gra-nularité spatio-temporelle des fonctions de coût sur la qualité des tournées calculées ainsi que sur les temps de calcul. Pour cela, nous avons généré différents jeux de données en utilisant un logiciel de micro-simulation du trafic urbain, permettant d'obtenir des données très réa-listes à différents niveaux de granularité spatio-temporelle. Nous considérons également différentes approches de ré-solution exactes (programmation linéaire en nombres entiers, Branch&Bound et programmation dynamique) et heuristiques (programmation dynamique restreinte et limited discrepancy search)