Exact and Approximate Linear Models for the Multi-Vehicle Probabilistic Covering Tour Problem

The Multi-Vehicle Probabilistic Covering Tour Problem aims at designing the tours of a fleet of vehicles characterized by a limited range that has to distribute goods to some distribution facilities, in order for those goods to subsequently reach the final customers. Each truck distributes directly only to the facilities, and the delivered goods reach the final customers with a given probability. The aim of the problem is to maximize the expected quantity of goods delivered to the final customers. The problem can be modeled as a mixed integer program with a non-linear objective function, as already presented in the literature together with a solving method based on a linear model with an exponential number of constraints. The contributions of the present work are a new model and two new linear approximation models able to provide tight lower and upper bounds for the optimal solution of the original problem. An extensive computational campaign on the instances available in the literature validates the new approaches we propose, providing several improved heuristic solutions and upper bounds with respect to the previous state-of-the-art. Several instances are also closed here for the first time.