New sampling-based methaeuristics for stochastic vehicle routing problems

Metaheuristics are general algorithmic frameworks, often nature-inspired, designed to solve complex optimization problems, and they are a growing research area since a few decades. In recent years, metaheuristics are emerging as successful alternatives to more classical approaches also for solving optimization problems that include in their mathematical formulation uncertain, stochastic, and dynamic information. An important feature often encountered in stochastic problems that is also very common in real-world contexts, is the lack of a closed-form or mathematical expression for the objective function. In these situations, the objective function must be estimated by sampling or simulation, and its estimated value is always an approximation. The main goal of this project is to design and experimentally analyze sampling-based extensions of some well known metaheuristics such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, and Tabu Search, and apply them to both academic and real-world stochastic vehicle routing problems, where the objective function is estimated by sampling or simulation. When extending a metaheuristic from its original version designed for deterministic problems to the sampling-based version for stochastic problems, the main difference is that, in the second-mentioned case, it is not possible to decide with certainty whether a solution is better than another one. This can only be tested by statistical sampling, obtaining a correct comparison result only with a certain probability. Thus, the way simulation approximation is used in metaheuristics largely depends on the way solutions are compared and the best solution among a set of other solutions is selected (`selection-of-the-best´ method). This project gives great importance to the analysis of the impact of different selection-of-the-best methods on the performance of sampling-based metaheuristics. The project focuses also on other two key aspects in solving stochastic vehicle routing problems with sampling-based metaheuristics: the analysis of the structure of good solutions, and the design of hybrid metaheuristics. The analysis of the structure of good solutions has a practical importance, particularly because it could allow a logistic planner to construct a solution incrementally, first selecting good components on the base of a-priori optimization, and then adding new components as information on previously uncertain data is revealed. The design of hybrid metaheuristics based on the combination of a metaheuristic with other algorithms is an important part of this project, that has the aim to obtain to state-of-the art algorithms for the selected problems. The last goal of this project is to propose and investigate a new modeling approach for stochastic problems based on imprecise probabilities. The imprecise probabilities formulation is new to the optimization field, and is quite general. Its main advantage is that it makes realistic assumptions on the stochasticity of the problem data, and may cope with real data limitations such as poorly known or unknown dependencies, small sample sizes, inconsistencies in the quality of input data, non-constant distributions. Moreover, some common modeling approaches (such as stochastic routing problems or routing with interval data) may be seen as particular cases of the one based on imprecise probabilities.