Abstract: In this article, we define a new routing problem that arises in the last-mile delivery of parcels, in which customers can be served either directly at home by a capacitated truck, or possibly with a drone carried on the truck, or in a self-service mode using one of the available lockers. We investigate four different formulations, and for one of them, we propose a branch-and-cut approach. We also discuss some possible variants of the original problem. In the computational experiments, we analyze and compare the performance of the four formulations for the problem and its variants, and we provide some useful managerial insights.
