In this work we study a variant of the Routing-Scheduling Problem in which autonomous devices are used for last-mile delivery. The problem aims at finding an optimal route for a vehicle carrying customer parcels from a central depot to selected facilities, from where autonomous devices like robots or drones are launched to perform last-mile deliveries. The objective is to minimize a lateness indicator, given customer delivery due dates. Depending on the preferences of the decision maker, three key objective functions are considered: min-max, min-sum and min-num, referring to minimizing the maximum tardiness, the total tardiness, and the number of late deliveries, respectively.
After providing a formal definition of the problem for various objective functions measuring lateness, we investigate their complexity and devise a (generic) Mixed Integer Programming (MIP) formulation based on multi-commodity network flows.
To deal with instances of realistic size, we propose a Benders Decomposition approach that can be implemented in a generic way for all three problem variants. Furthermore, we show how Benders cuts can be generated without resorting to linear programming to solve the Benders subproblems, and use a combinatorial approach instead.
Three variants of the proposed Benders decomposition are implemented and their performance is analyzed using adapted instances from the literature.
Numerical results show that the Benders approach with a tailored combinatorial algorithm for generating Benders cuts largely outperforms all other tested approaches.