Abstract EN:

These last years the systems of transport used for the collecting and the distribution of goods or services were the subject of many studies in the scientific community. Nowadays, the majority of the systems of transport must be able to deal with strict temporal constraints. Indeed, the customers or partners of a company require these constraints for the quality of service to be guaranteed. Moreover, the environment in which a company must operate is very often instable and thus its reactivity is also a significant asset. This results in defining models of piloting of the systems of transport known as dynamic in which part of the data of the problem depends on the time. Our work concerns the basic Vehicle Routing Problem VRP. This problem consists of a number of distributed customers, each requiring a specified weight of goods to be delivered. Vehicles dispatched from a single depot must deliver the goods required, then return to the depot. Each vehicle can carry a limited weight and only one vehicle is allowed to visit each customer. The problem is to find a set of delivery routes satisfying these requirements and giving minimal total cost. In practice, this is often taken to be equivalent to minimise the total distance travelled, or to minimise the number of vehicles used and then minimising total distance for this number of vehicles. The work presented in this thesis deals more precisely with the resolution of the Dynamic Vehicle Routing Problem with Time Windows DVRPTW and some of its extensions. The objective of this work was double. Firstly, it was a question of proving that the evolutionary algorithms can be used within a dynamic framework. In addition, it had to be checked that the performances, of this type of approach, were comparable with those of the best techniques up to now. To achieve these goals, we used the technique of the Genetic Algorithms (GA) to define a planner driven by the events. This planner aims to dynamically optimize the problem after each significant event (“arrival of a new request” and “end of service at a customer”) occurring throughout the day of service. The genetic algorithm is based on chromosomes of variable size in time, making it possible to take into account the arrival of new customers during the effective execution of the routes by vehicles. The effectiveness of the GA approaches raises the difficult question of the tuning of certain of parameters such as crossover or mutation rates. We used a tuning “a priori” of these parameters by using the technique of the experimental designs. The last point of this thesis relates to a software platform developed in JAVA to evaluate our approach and to compare the results with those obtained by other approaches.