As a consequence of the online shopping trend, people tend to receive a lot of parcels nowadays, which brings new challenges for delivery companies. Customer convenience and logistic efficiency play a role when competitive strategies have to be found. To account for both aspects, we introduced the Vehicle Routing Problem with Locker Boxes. Customers can be serviced at their home address, but only within a certain time window. Apart from that, the parcels can also be brought to so called locker boxes, that are accessible 24/7 and close to the customer's home address or any other suitable place. The service aspect appears as a requirement on the minimum number of home deliveries. Efficiency of a routing plan is measured in terms of total travelled distance.

A collaborative hybrid solution method is developed to solve the problem. In a first step Adaptive Large Neighborhood Search is used to solve the problem as a Vehicle Routing Problem with Time Windows, where the locker box stations are neglected. Then, some customers are taken out of the pure home delivery plan, and moved to locker boxes. At the locker box stations slots of different size are available and a bin-packing model is used to decide about the assignment of parcels to slots. The current capacity requirements of the locker boxes are returned to the routing algorithm to improve the selection of the locker box customers and the resulting routing problem is re-solved in an iterative procedure. The algorithm is applied to real-world inspired instances.