The COVID-19 pandemic has presented tremendous challenges to the world, one of which is the management of infectious waste generated by healthcare activities. Finding cost-efficient services with minimum threats to public health has become a top priority. The pandemic has induced extreme uncertainties, not only in the amount of generated waste, but also in the associated service times. With this in mind, the present study develops a mixed-integer linear programming (MILP) model for the location-routing problem with time windows (LRPTW). To handle the uncertainty in the amount of generated waste, three scenarios are defined respectively reflecting different severity levels of a pandemic. Furthermore, chance constraints are applied to deal with the variation of the service times at small generation nodes, and time windows at the transfer facilities. The complexity of the resulting mathematical model motivated the application of a branch-and-price (B&P) algorithm along with an ɛ-constraint technique. A case study of the situation of Wuhan, China, during the initial COVID-19 outbreak is employed to examine the performance and applicability of the proposed model. Our numerical tests indicate that the B&P algorithm outperforms CPLEX in the computational times by more than 83% in small-sized problem instances and reduces the gaps by at least 70% in large-scale ones. Through a comparison with the current and deterministic systems, our proposed stochastic system can timely adjust itself to fulfill nearly four times the demand of other systems in an extreme pandemic scenario, while maintaining a cost-efficient operation with no outbreak.