The multi-type carrier pickup and delivery problem with time windows

This paper introduces a novel variant of the Vehicle Routeing Problem with Time Windows (VRPTW) in last-mile logistics. Distinct from the existing literature, our problem formulation innovatively incorporates the collaborative routeing of a heterogeneous fleet comprising a truck, a drone, and an autonomous ground vehicle (AGV). The objective is to minimise the total operational cost while serving customers with simultaneous pickup and delivery demands. The optimisation is subject to the specific payload and operational constraints of each vehicle type. To address this problem, we first present a mathematical model. We then propose a tailored hybrid Particle Swarm Optimisation algorithm, which is specifically designed to handle the problem's inherent complexities, such as its hierarchical decision structure, heterogeneous vehicle constraints, and tight spatio-temporal coupling. The algorithm integrates an adaptive perturbation strategy with a local search mechanism inspired by Variable Neighbourhood Descent, and it is enhanced with several problem-specific operators, including a time-window repair strategy and a cross-carrier task-swapping procedure. Computational experiments demonstrate that the proposed collaborative system achieves an average cost reduction of 36.52% compared to a traditional truck-only system.