Quand nous considérons les problèmes réels d'optimisation, le temps est généralement une dimension importante à prendre en compte. Cela est particulièrement le cas pour les problèmes de livraison pour lesquels le temps est fréquemment présent sous différentes formes: les temps de déplacement entre deux livraisons consécutives; les fenêtres de temps autorisées pour chaque livraison; les contraintes de précédence peuvent être ajoutées entre des livraisons. Une source supplémentaire de complexité de ces problèmes apparaît lorsque le temps de parcours entre livraisons dépend de l'heure de départ, typiquement parce que dans les zones urbaines les conditions de circulation varient beaucoup au cours de la journée. Ces types de problèmes sont appelés Problèmes d'Optimisation Dépendants du Temps.
Puisque la disponibilité d'une grande quantité de données réelles dans ce domaine est assez récente, ces problèmes n'ont pas été beaucoup étudié dans la littérature et les approches par Programmation par Contraintes (PPC) sont encore plus rares. Une des raisons pour cela est que la PPC est généralement moins efficace que la Programmation Linéaire en Nombres Entiers ou les Méta-heuristiques (Recherche Locale, Algorithmes Génétiques, Colonies de Fourmis) pour les problèmes de tournées de véhicules purs (qui ne dépendent pas du temps). D'autre part, le « Constraint-Based Scheduling », qui est l'application de la PPC aux problèmes d'ordonnancement, est l'un des plus grand succès industriels de la PPC et cela a montré que les technologies de PPC peuvent être très efficaces pour résoudre les problèmes temporels. Des nouveaux types de variables (variables d'intervalle) et de contraintes globales associées ainsi que des nouveaux algorithmes de recherche ont été développés jusqu'à récemment pour améliorer l'expressivité et l'efficacité des modèles PPC impliquant les domaines temporels.
Notre objectif est d'appliquer et d'étendre les techniques de PPC afin de concevoir des solutions pour les Problèmes d'Optimisation Dépendants du Temps, en s'appuyant sur un cas réel d'utilisation pour lequel nous avons de bonnes perspectives et des données pour valider notre approche. La mise en œuvre de notre approche sera réalisée avec ou dans le moteur CP Optimizer d'IBM ILOG CPLEX Optimization Studio. Au cours des 18 premiers mois de thèse, nous allons concentrer nos efforts sur Smart Deliveries, un module du projet Optimod'Lyon, projet qui vise à améliorer la mobilité dans la ville de Lyon . Smart Deliveries traite de l'optimisation des séquences de livraison des transporteurs en prenant les données de trafic de la ville en compte . Cela signifie que nous voulons calculer la séquence de livraisons pour un chauffeur donné de manière à minimiser le temps total nécessaire pour parcourir tous les points de livraison. Des prévisions de trafic et d'autres informations utiles de la ville seront utilisés pour estimer la durée nécessaire pour aller d'une adresse de livraison à l'autre selon le moment de la journée.