Dynamic and Stochastic Vehicle Routing Problem with Time Windows : comparison between state-of-the-art methods

Vehicle routing is a common challenge in our everyday life that aims at optimizing the displacement of a given fleet of vehicles, in order to serve a given set of requests arriving from customers. The scientific community proposed numerous models for this problem as well as approaches to provide solutions respecting the needs and desires of the users. The methods proposed in the literature evolved over time such that the most recent techniques use representations that are different from older ones. The goal of this master thesis is to create a framework using a unique representation for some state-of-the-art techniques proposed by Russel Bent and Pascal Van Hentenryck tackling the dynamic vehicle routing problem with time windows. This variant of the vehicle routing problem has a set of requests that grows over time as customers are allowed to request service during the journey of the fleet, which brings the difficulty to determine if arriving requests may be included in the existing solution(s) during the operations. This variant also contains limitations in the time each request is allowed to be serviced because each of them is associated with a service time window. Our framework implements two major solution techniques that try to maximize the number of served customers for this variant of the vehicle routing problem: the Multiple Plan Approach and its extension using stochastic information, the Multiple Scenario Approach. In the framework we developed, we give to both of these techniques the possibility to use the 'Consensus' or the 'Regrets' approaches to take decisions during the dynamic phase of the problem. We also give the possibility to Multiple Scenario Approach to apply two improving strategies that are expected to provide better results by increasing the number of serviced requests per instance. These strategies, named 'Waiting' and 'Relocation' strategies, aim at increasing the number of served customers further by taking advantage of stochastic information some more. To describe the design we developed, we start from the original algorithms given in the literature and then expose the modifications we bring to them to reach our final product. Finally, we validate our framework by reproducing experiments done in the literature to verify the consistency of our results with those found in previous works, and point out parts of our framework that could be improved in further work.Master [120] : ingénieur civil en informatique, Université catholique de Louvain, 201