Robust policies for a multi-period fleet sizing problem with demand uncertainty

Motivated by an on-demand waste collection service offered by an Italian company, we investigate a multi-period fleet sizing problem with demand uncertainty. In a stochastic dynamic setting of several days, we consider a set of customers, each placing exactly one order on a known day. Future request demand is unknown, but all orders must be fulfilled. Customers have day windows that can be extended with early or late deliveries by paying a penalty when there is some flexibility. At the end of each day, we decide which pending orders to serve on the next day with a heterogeneous fleet of vehicles. The objective is to minimize total costs due to fleet sizing, staffing, and customer inconvenience. After describing the problem and its uncertainty model, we first provide lower-bounding and upper-bounding formulations for its static multi-period counterpart by employing robust optimization techniques. Then, we model it as a Markov Decision Process and present a solution method exploiting Approximate Dynamic Programming. We design myopic, policy function approximation, and innovative robust look-ahead approximation policies based on the static formulations provided and apply them in a folding-horizon fashion. Through an experimental evaluation of synthetic and realistic instances, we perform a computational analysis of the price of robustness varying the degree of uncertainty and maximum demand. Then, we provide managerial insights to suggest which policies to use and when. We show that applying robust optimization in a dynamic setting can partially overcome its conservative features at a small-medium price when uncertainty increases while guaranteeing feasibility.