New sampling-based methaeuristics for stochastic vehicle routing problems II

Stochastic Vehicle Routing Problems have received increasing attention in recent years. Those problems allow for more realistic models of real world problems by including stochastic information in their mathematical formulation. On the one hand stochastic models provide many opportunities, e.g. regarding practical applications in the f ield of transportation, on the other hand they come with some difficulties. In many cases stochastic problems are more difficult to solve than their non-stochastic counterparts. Only very small problem instances can be solved by exact approaches and the design of efficient (meta)heuristics is a great challenge. Furthermore there are several problems which have no known closed-form mathematical expression for the objective function. In that case conventional problem solving methods are of limited use. There are plenty of possibilities for research in this particular area and in the remainder of this section we depict the main goals of this project. Metaheuristics based on Monte Carlo Sampling have become state-of-the-art approaches for the Probabilistic Traveling Salesman Problem and the Probabilistic Traveling Salesman Problem with Deadlines. One of the main goals of this project is to design and analyze new metaheuristics for various other Stochastic Vehicle Routing Problems. It is very promising to obtain state-of-the-art approaches for many different Stochastic Vehicle Routing Problems in this way. One goal of this project is to discover other classes of Stochastic Vehicle Routing Problems which can be solved with metaheuristics based on Monte Carlo Sampling. For example, the class of chance-constrained Vehicle Routing Problems seems to be an interesting candidate for this research. Here the objective function is stochastic, and stochastic as well as non-stochastic constraints are used. Another goal is to detect inter dependencies between Stochastic Combinatorial Optimization, robust optimization and optimization using imprecise probabilities. All of those fields involve problems with uncertain data in their mathematical formulation and results in one of those fields could possibly be transferred to results for the other fi elds mentioned above. Last, the study of more advanced sampling techniques is yet another goal of this project.