When we consider real world optimization problems, time is usually an important dimension to take into account. This is particularly the case for Delivery Problems for which time is typically present in different forms: travel times are associated with consecutive deliveries; time windows may be associated with deliveries; precedence constraints may be added between deliveries. An additional source of complexity in these problems is when the travel time between deliveries depends on the moment of the travel, typically because in urban areas the traffic conditions vary a lot during the day; those types of problems are called Time-Dependent Optimization Problems.

Since the availability of extensive real-world data in this area is quite recent, these problems have not been much studied in the literature and Constraint Programming (CP) approaches are even rarer. One reason for this is that CP is usually less efficient than Integer Linear Programming or Meta-heuristics (Local Search, Evolutionary Algorithms, Ant Colonies) for pure (non time-dependent) Vehicle Routing Problems. On the other hand, Constraint-Based Scheduling, that is the application of CP to scheduling problems, is one of the greatest industrial success of CP and has shown that CP technologies can be very efficient for solving temporal problems. A variety of specialized variable types (interval variables) and related global constraints and search algorithms have been developed until recently to improve the expressiveness and efficiency of CP-based models involving temporal domains.

Our goal is to apply and extend CP techniques in order to design solutions for Time-Dependent Optimization Problems, leveraging a real use case for which we have good prospects and data to validate our approach. Implementation of our approach will be performed on top of or within the CP Optimizer engine of IBM ILOG CPLEX Optimization Studio. In the first 18 months of thesis we will focus our efforts on Smart Deliveries, a work-package of Optimod'Lyon - a project that aims at improving mobility in the city of Lyon. Smart Deliveries is about optimizing transporters delivery sequences by taking the city's traffic data into account. It means that we want to schedule the sequence of deliveries for a given driver in such a way that the total time needed to go through all delivery points is minimum. Traffic predictions and other useful information from the city will be used to estimate the duration needed to go from one delivery address to another depending on the time in the day.