A Two-Echelon Vehicle Routing Problem with Mobile Satellites and Multiple Commodities

This paper extends the two-echelon vehicle routing problem (2E-VRP) by considering multiple commodities, multiple depots, and mobile satellites (i.e., the so-called 3M-2E-VRP). This problem also accommodates flexible last-mile delivery strategies by allowing direct deliveries via first-echelon vehicles (mobile satellites) and indirect deliveries through goods exchanges at meeting points, such as parking lots or customer locations. We first model the problem as a mixed-integer linear programming (MILP); and then develop an innovative metaheuristic algorithm to solve medium and large problem instances. The proposed metaheuristic (the so-called AS-LNS) combines an innovative Approximate Scheduling (AS) approach with Large Neighborhood Search (LNS). Computational experiments validate the 3M-2E-VRP formulation and demonstrate the effectiveness of the proposed AS-LNS algorithm. Key managerial insights are further presented through a comprehensive sensitivity analysis, wherein the impact of key parameters, such as fuel consumption and wage costs, and comparison of different problem variants, is investigated on last-mile delivery strategies.