The robust pickup and delivery problem with time windows

Abstract

This study addresses the robust pickup and delivery problem with time windows (RPDPTW), in which uncertainty in demands and travel times is modelled using robust optimisation. The RPDPTW involves determining the least-cost routes to serve transportation requests from origins to destinations, while respecting vehicle capacity and time window constraints under all anticipated realisations of uncertain data. Two robust counterpart formulations are proposed. The first employs the linearisation of recursive equations to produce a compact formulation, suitable for implementation with general-purpose mixed-integer programming solvers. The second relies on a cutting-plane approach, incorporated into a tailored branch-and-cut (B&C) algorithm. Extensive computational experiments were conducted to evaluate the proposed methods across diverse instance configurations. While the compact formulation performed effectively in some cases, the B&C algorithm solved a larger number of instances to optimality and consistently provided high-quality solutions under uncertainty. Robust solutions significantly reduced the risk of infeasibility compared to deterministic solutions, with modest increases in routing costs. In addition, we provide managerial insights by analysing the results of Monte Carlo simulations across different instance characteristics.