Multi-Shift Single-Vehicle Routing Problem Under Fuzzy Uncertainty During the COVID-19 Pandemic

Background: This work studies the single vehicle routing problem (VRP) with multishift and fuzzy uncertainty. In this case, a company perpetually exploits a vehicle to accomplish demand over a scheduling period of several work shifts. In our problem, a crew performs maintenance jobs at different locations. The working team operates in different shifts with a maximum duration but recurrently returns to the depot by the end of the shift to avoid overtime. Methods: The objective is to minimize the number of shifts and the completion time (makespan). In addition, we analyze the influence of uncertainty in driving and processing times on the overtime avoidance constraint in shift duration. We develop an Artificial Immune Heuristic to determine optimal solutions considering both makespan and overtime avoidance. We implement a Pareto- based framework to evaluate the impact of uncertainty. Results: We present several numerical case studies to examine the problem. In particular, we analyze different case study scenarios inferred from the environmental changes in travel and processing times observed in the Apulia region (SE Italy) during the COVID-19 lockdown periods that occurred in spring (started on March 9, 2020) and autumn (after November 6, 2020) of the year 2020). Conclusion: The work program was revised as soon as the Italian COVID-19 restrictions were implemented in the spring and autumn of 2020 due to the changing environment. Our approach allowed for the rapid release of new robust maintenance programs. Results show significant improvements with the presented approach.