Hybrid Sampling-based metaheuristics for Stochastic Optimization Problems with Deadlines

In recent years, there has been an increasing interest for Stochastic Combinatorial Problems (SCOPs). In contrast to the traditional approach of Combinatorial Optimization Problems, such as Vehicle Routing, SCOPs encompass stochastic information about the problem. This results to more realistic models as in reality many events or quantities can be approximated probabilistically more accurately (e.g. travel times) due to unpredictable factors such as traffic or weather conditions. In this work, we focus mainly on Stochastic Combinatorial problems that encompass some type of a deadline. Examples of this type of problems arise often in Vehicle Routing or Scheduling. Examples from the Vehicle Routing literature are the Orienteering Problem with Stochastic Travel and Service Times (OPSTS) and the Probabilistic Traveling Salesman Problem with Deadlines (PTSPD). In the OPSTS, a company has to select a subset of customers to serve before a global deadline while in the PTSPD, a company has to serve customers and each one has a deadline after of which a penalty is incurred. Also, each customer will be served or not in each tour with some probability. Another example from scheduling is the Resource-Constrained project scheduling problem. Stochasticity makes the problem models more difficult to solve than its non-stochastic counterparts. Exact methods for solving them work only for very small problem instances and designing efficient (meta)heuristics for these problems is also a challenge. One of the challenging aspects can also be the computation of the objective function of the problem as there are several problems with no known closed-form expression or hard-to-compute objective functions. One of the ways to deal with such objective functions is to approximate them using Monte Carlo sampling. Metaheuristics based on Monte Carlo Sampling have become state-of-the-art approaches for the Probabilistic Traveling Salesman Problem (PTSP), the Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) and the Orienteering Problem with Stochastic Travel and Service Times (OPSTS). However, because of the way Monte Carlo sampling works, in the solution areas around the deadline is probable to occur, larger errors occur that then propagate to the rest of the solution, with a deterioration of the overall solution cost estimation. This can be mitigated by mixing different objective functions (e.g. exact methods) along with sampling-based methods in order to compute the objective value. In this project, we study which methods to use and how to combine them in order to minimize the total error while preserving or even enhancing the performance of sampling-based metaheuristics, leading to sampling-based hybrid methods. One other goal of this project is to discover other classes of Stochastic Vehicle Routing Problems which can be solved with metaheuristics based on hybrid 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. The study of more advanced sampling techniques is yet another goal of this project. While the current approaches mainly use basic sampling techniques, more advanced and elaborate techniques can lead to further improvements of those approaches. A final target is the investigation of the use of GPGPUs. Coupling this technology with sampling-based methods appears to be very promising since the calculation of many samples (without jumps or branches) in parallel is the situation where GPGPUs perform best, and accidentally this is exactly what happens with sampling-based methods.