The vehicle routing problem with heterogeneous locker boxes

To achieve logistic efficiency and customer convenience in last-mile delivery processes, a system with alternative delivery points in the form of locker box stations can be used. In such a system, customers can be served either at their home address within a certain time window, or at a locker box station where parcels can be picked up at any time. Customers can get a compensation payment when being served at a locker box. They can have a request of more than one parcel and the parcels can be of different sizes. At a locker box station, a limited number of slots of different sizes is available; we assume that parcels of one customer can be stored together in a slot. We consider the vehicle routing problem with heterogeneous locker boxes, where the total cost—consisting of routing and compensation costs—has to be minimized while taking into account the packing of parcels into locker boxes. We provide a mathematical formulation of the problem and propose a metaheuristic solution method. Instances and results from the literature for the problem with a single parcel and a single slot size are used to benchmark our metaheuristic solution method. For the problem with different sizes, we compare a unit-size model to a multi-size model, packing being considered in the latter. Finally, we analyze how different configurations of locker box stations work for different demand scenarios.