Two-echelon vehicle routing problem with time windows and mobile satellites

To tackle the logistics challenges faced by enterprises using unmanned aerial vehicles (UAV) with human-driven vans for parcel deliveries, we introduce the two-echelon vehicle routing problem with time windows and mobile satellites (2E-VRP-TM), which, when solved, optimizes delivery routes for a fleet of van-UAV combinations. Typically, one van carries several UAVs. The first echelon involves time-window-driven parcel deliveries using vans from a distribution center (DC) to customers. The second echelon involves UAVs being dispatched from mobile-satellite vans to serve customers with time windows and directly delivering parcels from the DC. When the first-echelon vehicles park at customer locations and wait for second-echelon vehicle departures and returns, the first-echelon vehicles are used as mobile satellites. We develop a vehicle-flow formulation, in which the mobile-satellite synchronization constraints are included to ensure the echelon interaction. We provide an adaptive large neighborhood search heuristic. Computational experiments evaluate the validity of the 2E-VRP-TM formulation and the effectiveness of the heuristic.