A common assumption in the models for the vehicle routing problem with stochastic demands is that all demands must be satisfied. This is achieved by including recourse actions in two-stage stochastic programming formulations or by ensuring with a high probability that all demand fits within the vehicle capacity (chance-constrained formulations). In this work, we relax the assumption of full demand satisfaction and allow partial deliveries. Practical applications of partial deliveries include humanitarian logistics and food rescue programs. To ensure a fair solution for all customers, we require that the minimum expected fill rate over all customers meets the target fill rate. We refer to the resulting problem as the fair stochastic vehicle routing problem with partial deliveries. We propose a model in which we account for uncertain customer demand by constructing routes such that the expected minimum fill rate is above a predefined threshold. To solve the problem, we develop a branch-price-and-cut algorithm capable of solving instances with up to 75 customers. Specifically, we propose problem-specific bounding techniques to enhance the performance of the solution methods for the pricing problem. Results show, among others, that with our proposed model, solutions are guaranteed to be feasible at only a marginal cost increase compared to a deterministic model with expected demands.
Article
View Fair stochastic vehicle routing with partial deliveries