Global e-commerce sales are estimated to hit $4.5 trillion in 2021. This poses huge challenges for last mile delivery services. Currently deliveries are performed at customer's home/workplace where customers wait to get orders. Recently, companies developed locker delivery. Customers choose a nearby locker as their pickup location for orders. In the past two years, trunk delivery has been proposed: orders can be delivered to the trunks of cars. Trunk delivery is different from the former two since the car may be in different locations during the day. Thus, synchronization between cars and couriers is required to perform the delivery.

This work studies a last-mile system that combines home/workplace, locker and trunk delivery services. We call the resulting problem the generalized vehicle routing problem with time windows (GVRPTW).

We describe the GVRPTW with a set covering model. The solution is obtained by solving this model on a restricted route pool, subset of all feasible routes. The route pool is first filled using construction heuristic: first pivots customers are selected, then next inserted customers are selected based on a regret paradigm. Finally routes are re-optimized with a labeling algorithm. The route pool is iteratively enriched 1) with routes obtained by exploiting the dual information retrieved by the resolution of the linear relaxation of the set covering model; 2) with new routes obtained by intensification of the research around feasible solutions via a local search procedure.

The algorithm is tested on benchmark instances from the literature.