409. Policies for the Generalised Capacitated Resupply Problem
Invited abstract in session WB-20: Complexity and Approximation, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Mette Wagenvoort
|
| Econometric Institute, Erasmus University Rotterdam | |
| 2. | Paul Bouman
|
| Econometric Institute, Erasmus University Rotterdam | |
| 3. | Martijn van Ee
|
| Faculty of Military Sciences, Den Helder, Netherlands Defence Academy | |
| 4. | Kerry Malone
|
| Military Operations, TNO |
Abstract
We consider the Generalised Capacitated Resupply Problem (GCRP) in which locations with a given capacity and 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 addition to the GCRP, we consider three variants of the problem in which the capacities and demand rates and/or the resupply times are homogeneous. We prove that the GCRP is NP-hard, even on one vehicle and with homogeneous capacities, and present policies to solve the different variants of the problem and provide corresponding approximation guarantees.
Keywords
- Complexity and Approximation
Status: accepted
Back to the list of papers