The generalized vehicle routing problem with time windows
Résumé
Global e-commerce sales are estimated to hit $4.5 trillion in 2021. This poses huge challenges forlast mile delivery services. Currently deliveries are performed at customer?s home/workplacewhere customers wait to get orders. Recently, companies developed locker delivery. Customerschoose a nearby locker as their pickup location for orders. In the past two years, trunk de-livery has been proposed: orders can be delivered to the trunks of cars. Trunk delivery isdifferent 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 deliv-ery services. We call the resulting problem the generalized vehicle routing problem with timewindows (GVRPTW).We describe the GVRPTW with a set covering model. The solution is obtained by solvingthis model on a restricted route pool, subset of all feasible routes. The route pool is first filledusing construction heuristic: first pivots customers are selected, then next inserted customersare selected based on a regret paradigm. Finally routes are re-optimized with a labelingalgorithm. The route pool is iteratively enriched 1) with routes obtained by exploiting thedual 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 alocal search procedure.The algorithm is tested on benchmark instances from the literature.