Pickup and Delivery with Lockers

In this paper we define pickup and delivery routing problems that arise in last-mile delivery of parcels where customers can be served either directly at home, by one or more capacitated trucks, or via lockers. During the same route, the couriers must also collect the parcels returned by the customers, that can be picked up directly at the customers' homes or at a locker. Customers can select home service, self-service at a nearby lockers with a discount, or let the logistics company decide between a set of possible options.In this paper we investigate several formulations and branch-and-cut algorithms for the single and multiple vehicle versions of the problems with or without time windows.