Abstract
The pandemic caused by the corona virus SARS-CoV-2 raised many new challenges for humanity. For instance, governments imposed regulations such as lockdowns, resulting in supply chain shocks at different tiers. Additionally, delivery services reached their capacity limits because the demand for mail orders soared temporarily during the lockdowns. We argue that one option to support supply chain viability at the last-mile delivery tier is to use (outdoor) parcel lockers through which customers can collect their orderings 24/7 while ensuring physical distancing. The location planning of such lockers is known to be of utmost importance for their success. Another important topic to address is that the design of the compartment structure of the parcel lockers should meet the (uncertain) customer demand for different commodities. Both of the latter planning issues are combined into one optimization problem in this article. The objective is to maximize a linear function (e.g., expected profits) of the covered demand, given a budget an operator is willing to invest. An integer linear programming formulation is proposed, and a reformulation based on Benders decomposition is derived. It is shown that the Benders cuts can be separated in linear time. The developed algorithms enable solving of large-scale problem instances demonstrated by a performance analysis of computational experiments. The impact of different problem parameters on the obtained solutions is demonstrated by a sensitivity analysis. A case study based on real-world data from Austria is presented. The results show that using parcel lockers can support supply chain viability at the last-mile delivery tier. Moreover, the relatively small investment cost yields promising returns. The results further indicate that small-sized and medium-sized compartments should be preferred over large and x-large ones in the parcel locker compartment design.