The growth of e-commerce is stressing last-mile delivery services. Some solutions are being developed to avoid delivery failures. Classically, parcels are delivered into mailboxes. They can also be delivered in shared locations such as shops or lockers boxes. During worktime, packages can also be delivered at work in some companies. We define the Vehicle Routing Problem with Delivery Options, which generalizes the VRP with time windows, integrating several delivery locations per request. Each location can be associated with a time window and a priority level, and called a delivery option. We consider several types of delivery locations, including lockers which may introduce some synchronization between routes due to their limited capacities. An overall service level is defined based on prorities. Consequently, the set of routes must serve all clients through exactly one option, respect the time windows and the synchronized resources constraints.

To solve this problem, we design a LNS coupled with a set partitionning formulation. It integrates specific operators as well as operators adapted from the VRPTW. The method is evaluated on randomly generated instances and on the VRPTW benchmarks.