Policies for the Generalised Capacitated Resupply Problems

In the Capacitated Resupply Problem, locations with a given demand rate should be resupplied by vehicles such that they do not run out of stock and the number of vehicles is minimised. Compared to related problems, we consider the scenario where the payload of the vehicles may not suffice to bring the stock level back to full capacity. In Wagenvoort et al. (2023), we focus on the Homogeneous Capacitated Resupply Problem where demand locations are homogeneous. We present both simple policies that provide 2-approximations and an optimal greedy policy that runs in pseudo-polynomial time. A 2-approximation algorithm can also be defined for the Capacitated Resupply Problem. We additionally define the Generalised Capacitated Resupply Problem in which the resupply operation to a location is not restricted to be unit-length. We define solution algorithms, but the approximation ratio remains an open question.

Wagenvoort, M., Van Ee, M., Bouman, P., & Malone, K.M. (2023). Simple Policies for Capacitated Resupply Problems (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik.