A Variable Neighborhood Search algorithm for the Robust Capacitated Vehicle Routing Problem with demand uncertainty

Uncertainty generates difficulties in the industries for creation of efficient route plans to serve customers that require their services, which complicates the task of decision makers. The Vehicle Routing Problem (VRP) aims to find the set of optimal routes for customers to be served, minimizing the total cost and ensuring that all demands are satisfied, also taking into account the number of vehicles and their capacity, the distance between customers among others. However, it does not consider the possibility that uncertainty may arise in its parameters, this is how is necessary to create models for represent real industry scenarios. Some suitable examples of uncertainty in VRP are: uncertain travel and service times, dynamic presence of customers, stochasticity in customer demands. In presence of uncertain parameters, the VRP is known as Stochatic Vehicle Routing Problem (SVRP). The uncertainty in customers demands is the most studied variant in the literature and is known as Capacited Vehicle Routing Problem with Stochastic Demands (CVRPSD) where the only uncertain parameters are the customers demands. There are different methods, exact and approximate algorithms which have been used to solve this problem such as L-shaped algorithm, Tabu search, Ant Colony Optimization and several others. In this paper, we present a Variable Neighborhood Search algorithm (VNS) to solve the CVRPSD which consists of a shaking phase that is linked to identifying diversity in promising regions (diversification) and a local search phase that explores different neighborhoods with the aim of reaching a local optimum for all neighborhoods considered, expanding intensification and improving the solutions, this is known as Variable Descent Algorithm (VND) and constitutes a simple variant of VNS which the principal different is that neighborhood structures are defined in a deterministic way, so this will be used in the local search part. Our approach is to handle CVRPSD through a robust optimization, where customer demands belong to previously defined bounded and uncertain sets, which are built as deviations around an expected demand value, therefore, a customer is linked to a possible configuration of customer demands (ranges) that are identified as vector scenarios which are free to take negative values and are associated with a individually weight. Thus, the set of demands represents the linear combination of vector scenarios whose dimension is defined by the number of nodes. The expected result is that our robust solution can generate protection in case of demand dissatisfaction without the need to previously define resource actions, as uncertainty in demands deals with in other cases, as it incurs a small additional cost to that generated by the deterministic routes.