An Exact Model for the Vehicle Routing Problem with Delivery Options

This work addresses the Vehicle Routing Problem with Delivery Options, which captures key aspects of last-mile distribution, such as delivery flexibility and the use of shared delivery locations among customers. The problem formulation includes vehicle and location capacity constraints, time windows, and a global customer satisfaction index. To solve this rich and challenging problem, we propose a branch-and-cut-and-price algorithm, which can be applied both directly and iteratively. Both approaches were tested on benchmark instances from the literature. The results show a superior performance compared to the best exact algorithm available to date, in terms of both solution quality and computational time.