Multi-Period Scheduling and Routing (MPSRP) refers to problems involving employee mobilisation to perform work-related activities at geographically dispersed customer locations over a period of several days. This problem consists of the integration of two NP-hard problems: (i) the personnel scheduling problem and (ii) the vehicle routing problem.
Each problem have been extensively studied in the literature. However, to the best of our knowledge, the integration of both of them when complicating work rules need to be included in a multi-period environment has not been previously addressed. Certain constraints in personnel scheduling such as work regulations lead to substructures of the problem including constraints on sequences of shifts. It has been shown that exploiting formal languages to model such substructures facilitates the formulation and provides models that are easier to solve. Formal languages have already been successfully used to solve personnel scheduling problems where daily shifts are modeled with context-free grammars. However, in practice, there are certain types of constraints (e.g., the total working length over the planning horizon) that are difficult to integrate with this modeling paradigm.
To address the aforementioned issue, we propose a generic approach (based on formal languages) to model and to include work regulations in MPSRP. This approach allows to incorporate a great variety of work rules. The personnel scheduling component of the problem is coupled with an extended vehicle routing problem including customers' time windows, skill requirements and a set of complex scheduling-related constraints. To evaluate the performance of our approach we compare three modeling methods on instances representing a home health care problem: (i) a classical MIP formulation, (ii) a grammar-based formulation with supplementary constraints and (iii) a new automaton-based formulation encapsulating all work rules.