OPTIMIZATION OF MIXED VEHICLE-DRONE ROUTING WITH TIME WINDOWS FOR LAST-MILE DELIVERY
Abstract
The growth of e-commerce and the demand for ever shorter delivery lead times put considerable pressure on last-mile logistics operators. This article proposes a unified mixed-integer linear programming (MILP) model for mixed vehicle-drone routing with time windows (VRPTW-D). A conventional vehicle may, at each of its stops, launch a drone that serves a customer on its own and is then recovered by the vehicle, either at the same stop or at a later stop. The compact formulation relies on ternary flight variables, continuous time variables and an exact linearization of the vehicle-drone synchronization; it embeds valid inequalities (Dantzig - Fulkerson - Johnson subtour elimination and use - flow linking) that strengthen the continuous relaxation. For larger instances, we develop an ALNS (Adaptive Large Neighborhood Search) heuristic calibrated against the exact solutions. The exact model proves optimality on small instances (n - 10) and, beyond, provides feasible solutions together with bounds; the ALNS is the practical solution method for large instances. A reproducible instance set, generated in the style of Solomon (classes C1, R1 and RC1) with an extension of the time windows to drones, allows us to measure precisely the contribution of the drones, the value of the relaxation and the comparative performance of the exact model and the ALNS, complemented by a sensitivity analysis (drone endurance, relative speed, time-window width).