Pickup and delivery with lockers

We define a pickup and delivery routing problem with time windows that arises in last-mile delivery. A customer can be served either directly at home, by one of the available capacitated trucks, or via lockers, that allow a self-service option. On the same route, the couriers must deliver the parcels and collect the packages that the customers intend to return. The returned parcels can be picked up directly at the customers’ homes or at a locker. Customers can select home service, self-service at one of the nearby lockers with a discount, or let the logistics company decide. All services must be performed within a given time window. We propose three formulations, two branch-and-cut algorithms, and some valid inequalities. We also investigate the case with a single vehicle, with different types of time windows, including no time windows. Moreover, we show how to accommodate simultaneous pickup and delivery and multiple requests from a customer.