A Vehicle Routing Problem with Time Windows and Workload Balancing for COVID-19 Testers: A Case Study

Due to the COVID-19 pandemic, laboratories have faced unprecedented demand for in-home delivery test services. This drastic demand increase requires a rapid reaction from laboratories to manage their testers in order to respond to the high demand volume and avoid unnecessary costs. This study provides an optimization model based on the vehicle routing problem with time windows by considering the testers’ workload balancing to improve laboratories’ assignment and routing policies. A medical lab that has faced this situation for its in-home test services is taken as a real-world case in the current study. A mixed-integer programming model is solved for small instances using the CPLEX solver, and an adaptive large neighborhood search algorithm is implemented for large instances. Ultimately, the obtained solutions are compared to the real-world implementation of the lab on a dataset of six consecutive days, and the results are further discussed.