Algorithms for field staff scheduling problems

This research project is motivated by the problem situation faced by organizations providing mobile care or technical (maintenance) services. The kernel of the problem consists in assigning a given number of service or care tasks to a given number of employees. Each employee is characterized by certain skills at different levels, availability periods, a per km distance-based cost (depending on the vehicle associated with the employee), and wage costs of different heights. Each task is associated with a time window, has to be carried out within a given time period, which spans from one day up to a couple of weeks, and demands an employee who meets given skill- level requirements. In some cases, a task demands two field employees to be completed. Finally, also labor time related constraints, such as maximum shift length limitations and minimum rest periods between two shifts, have to be considered in the planning. The general objective is to generate least cost routing and scheduling plans, considering travel-based, labor-based, and client as well as employee-satisfaction-based cost terms. Client- satisfaction is, e.g., linked to consistency. This means that the number of different field employees serving the same client should be as low as possible. Until now, problems of this kind have mostly been solved by means of heuristic algorithms. They generate good solutions within acceptable run time. Exact algorithms, which compute the guaranteed optimum, but usually have exponential run times, have barely been investigated for problems of this kind. Therefore, in the first part of this project, exact algorithms for solving the deterministic problem will be developed. Branch-and-cut and branch-and- cut-and-price algorithms are among the most promising candidates. We, however, do not expect to solve problem instances of realistic size with exact algorithms. Therefore, we also plan to design heuristic solution procedures, based on the large neighborhood search paradigm. The development of hybrid methods, at the intersection of heuristic and exact methods, is also planned. In reality, in particular travel and service times are hardly ever deterministic. Only little research addresses the reasonable integration of uncertainty regarding travel and service times in the presence of time windows. Therefore, in the second part of this project, we plan to develop, analyze and compare problem formulations of the stochastic programming field and of the robust optimization domain, which are based on different uncertainty assumptions; in order to determine their advantages as well as their limitations in theory and practice. The different approaches will also be used as a basis for the development of according heuristic solution methods. In this project, a broad theoretical basis for both modeling and solving the generic field staff scheduling problem in the area of mobile care and technical (maintenance) services shall thus be created.

In this research project, optimization algorithms for field workforce routing and scheduling in the area of mobile care and technical (maintenance) services have been developed. The kernel of these problems consists in assigning a given number of service or care tasks to a given number of employees. Each employee may be characterized by certain skills at different levels, availability periods, distance-based cost (depending on the vehicle associated with the employee), and wage costs. Each task may be associated with a time window, has to be carried out within a given time period, which may span from one day up to a couple of weeks, and demands an employee who meets the given skill level requirements. In some cases, a task may demand two field employees to be completed. This aspect requires synchronizing the routes of two or more staff members. Also labor time related constraints such as maximum shift length limitations may have to be considered in the planning. The objective is to generate least cost routing and scheduling plans considering travel based, labor based, as well as client satisfaction or quality of service related cost terms. Client satisfaction is commonly linked to consistency. Consistency means that the number of different field employees serving the same client should be as low as possible and that the timing of recurrent visits to the same client should be similar over the planing horizon. Other complicating aspects involve the planning of walking subroutes in pedestrian zones (the car has to be left at a parking location and one or more clients have to be visited on foot), and considerable uncertainty with respect to the length of the service times. In this project, we have developed new concepts for dealing with these complicating aspects in the context of exact and heuristic optimization algorithms. Exact optimization algorithms compute the proven optimal solution to a certain problem while heuristic methods use search strategies that do not allow to prove optimality of the obtained plan but strive for good solutions within short computation times. Therefore, exact methods are used to compute optimal solutions for instances of reduced size to validate the performance of the developed heuristic methods. In this project, we developed exact methods that rely on the so-called branch-and-price and branch-and-cut concepts and that are able to address synchronization and subroute planning requirements. We also developed efficient heuristic components that can be used within the so- called large neighborhood search paradigm, and also in other heuristic search strategies, in order to address the different complicating aspects encountered in field workforce scheduling. Moreover, we obtained valuable insights into the trade-off relationship of client-oriented and cost-oriented objectives and we could show that improvements in terms of quality of service can often be achieved at only little additional costs. The algorithmic concepts developed in this project can be and are used as the basis for decision support software tools for field workforce planning.