Algorithms for field staff scheduling problems

Project Leader: Sophie N. Parragh
Co-Applicant: Karl F. Doerner
Funding Body: Austrian Science Fund (FWF)
Project Number: T514-N13 (Hertha Firnberg Program)
Duration: Jul 2011 – Sep 2012 and May 2014 – Jan 2016

Abstract: This research project is motivated by the problem situation faced by organizations providing mobile care or technical (maintenance) services. 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. Finally, also labor time related constraints such as maximum shift length limitations and minimum rest periods between two shifts may 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. In this project, we develop exact, metaheuristic, and hybrid algorithms addressing different aspects of this problem as well as the problem as a whole.
In reality, in particular travel and service times are hardly ever deterministic. 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 field staff scheduling problems in the area of mobile care and technical (maintenance) services shall thus be created.

Core Publications:

  1. Parragh, S.N., Doerner, K.F. (2018). Solving Routing Problems with pairwise synchronization constraints. Central European Journal of Operational Research. https://doi.org/10.1007/s10100-018-0520-4 (Open Access)
  2. Parragh, S.N., Cordeau J.-F. (2017). Branch-and-Price and Adaptive Large Neighborhood Search for the Truck and Trailer Routing Problem with Time Windows. Computers and Operations Research. http://dx.doi.org/10.1016/j.cor.2017.01.020 (Open Access)
  3. Braekers, K., Hartl, R.F., Parragh, S.N., Tricoire, F. (2016). A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience.  European Journal of Operational Research 248(2), 428-443. http://dx.doi.org/10.1016/j.ejor.2015.07.028 (Open Access)
  4. Kovacs, A.A., Golden, B., Hartl, R.F., Parragh, S.N. (2015). The generalized consistent vehicle routing problem. Transportation Science 49(4), 796-816. http://dx.doi.org/10.1287/trsc.2014.0529 (Open Access)
  5. Kovacs, A.A., Parragh, S.N., Hartl, R.F. (2015). The Multi-Objective Generalized Consistent Vehicle Routing Problem. European Journal of Operational Research 247(2), 441-458. http://dx.doi.org/10.1016/j.ejor.2015.06.030 (Open Access)
  6. Kovacs, A.A., Hartl, R.F., Parragh, S.N., Golden, B. (2014). Vehicle routing problems in which consistency considerations are important: A survey. Networks, 64(3) ,192-213. http://dx.doi.org/10.1002/net.21565 (Open Access)
  7. Kovacs, A. A., Parragh, S. N., Hartl, R. F. (2014). A template based adaptive large neighborhood search for the consistent vehicle routing problem. Networks, 63(1), 60-81. http://dx.doi.org/10.1002/net.21522, http://phaidra.univie.ac.at/o:397974 (Green Access)

Publications on Related Topics:

  1. Parragh, S.N., Pinho de Sousa, J., Almada-Lobo, B. (2015). The dial-a-ride problem with split requests and profits, Transportation Science, 49(2), 311-334. http://dx.doi.org/10.1287/trsc.2014.0520 (Open Access)
  2. Amorim, P., Parragh, S. N., Sperandio, F., Almada-Lobo, B. (2014). A rich vehicle routing problem dealing with perishable food: a case study. Top, 22(2), 489-508. http://dx.doi.org/10.1007/s11750-012-0266-4, http://phaidra.univie.ac.at/o:406859 (Green Access)
  3. Parragh, S.N. and Schmid, V. (2013). Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research 40 (1), 490-497. http://dx.doi.org/10.1016/j.cor.2012.08.004 (Open Access)

Working Papers:

  1. Parragh, S.N., Savelsbergh, M., Inter-route visit time synchronization in the presence of stochastic service time. Working paper (in preparation)

Presentations at scientific conferences:

  1. S.N. Parragh, K. Braekers, A.A. Kovacs, R.F. Hartl, F. Tricoire, Evaluating the trade-off between cost and service-oriented objectives in routing and scheduling problems OR 2015, Vienna, Austria, September 2015.
    Abstract: In many routing and scheduling problems besides cost also service-oriented objectives are of concern. In order to shed some light on their trade-off relationship, we introduce separate service-oriented objectives into the generalized consistent vehicle routing problem (GenConVRP) and into the home care routing and scheduling problem (HCRSP). In the resulting multi-objective GenConVRP we concurrently optimize routing costs and two service-oriented objectives. The first accounts for the maximum number of different drivers visiting a given customer (known as driver consistency) and the second for the maximum arrival time difference during the planning horizon (known as arrival time consistency). Frequent customers have demands on several days in the planning horizon while non-frequent customers require a service only once. Each customer is associated with an AM or a PM time window and waiting along the route is not allowed. In the bi-objective HCRSP we minimize routing and overtime costs and we maximize the service level with respect to preferences for visit times and nurses. Overtime costs in combination with interval preferences on preferred visit times results in a scheduling problem for each route that is a bi-objective problem in itself, which is a distinctive characteristic of the bi-objective HCRSP. Furthermore, each client is associated with a time window and waiting within the time window to improve service levels is not allowed. For both problems we solve small instances to optimality using the epsilon-constraint scheme. To solve larger (real world) instances we devise algorithms combining large neighborhood search and multi-directional local search. We can show that a considerable trade-off between cost and client-oriented objectives exists. However, our results also reveal that, using the minimum cost solution as a basis, the considered service levels may be improved drastically with only small additional costs; and that in the GenConVRP, in several cases, arrival time consistency and driver consistency can be improved simultaneously.
  2.  S. N. Parragh, Cordeau, J.-F., Column generation for the truck and trailer routing problem with time windows VeRoLog 2015, Vienna, Austria, June 2015.
  3. S. N. Parragh, Cordeau, J.-F., Column generation for the truck and trailer routing problem with time windows. Odysseus 2015, Ajaccio, France, June 2015. http://odysseus2015.sciencesconf.org
    Abstract: Motivated by the field staff routing and scheduling problem of an Austrian infrastructure service provider, which involves the planning of subroutes, we study the truck and trailer routing problem with time windows (TTRPTW). In the TTRPTW a fleet of trucks and trailers is routed in such a way that customers are visited within their time windows at minimum routing costs. Each customer has a certain demand and capacity limits of trucks as well as trailers have to be respected. Furthermore, certain accessibility restrictions apply: some customers can only be visited by a truck alone while others may be visited by a truck towing a trailer. At each of the latter customers, the trailer may be parked and a truck only subroute may be started. A customer serving as such a temporary depot may either be served before or after the subroute, whichever of the two is more advantageous in terms of the given time windows. We devise a path based formulation for the TTRPTW whose linear relaxation is solved by means of column generation. The resulting pricing subproblem corresponds to an elementary shortest path problem with resource constraints for which a dynamic programming based labeling algorithm is designed. Within the labeling algorithm certain problem properties, such as in which cases subroutes should be generated, are exploited. In addition to the exact labeling algorithm, we also use heuristic pricing schemes that rely on sets of promising, pre-computed subroutes and on ideas from large neighborhood search. The proposed column generation algorithm is applied to instances from the literature as well as to additional instances of reduced size. We are able to solve some with up to 50 customers.
  4. S. N. Parragh, Cordeau, J.-F., Column generation for the truck and trailer routing problem with time windows EULOG 2014, Vienna, Austria, November 2014.
    Abstract: In the truck and trailer routing problem with time windows (TTRPTW) a fleet of trucks and trailers is routed in such a way that customers are visited within their time windows at minimum routing costs. Each customer has a certain demand and capacity limits of trucks as well as trailers have to be respected. Furthermore, certain accessibility restrictions apply: some customers can only be visited by a truck alone while others may be visited by a truck towing a trailer. At each of the latter customers, the trailer may be parked and a truck only subtour may be started. A trailer customer serving as such a temporary depot may either be served before or after the subtour, whichever of the two is more advantageous in terms of the given time windows. We devise a path based formulation for the TTRPTW whose linear relaxation is solved by means of column generation. The resulting pricing subproblem corresponds to an elementary shortest path problem with resource constraints for which a dynamic programming based labeling algorithm is designed. Within the labeling algorithm certain problem properties, such as in which cases subtours should be generated, are exploited. In addition to the exact labeling algorithm, we also use heuristic pricing schemes. The proposed column generation algorithm is applied to instances from the literature of reduced size. We are able to solve some with up to 50 customers.
  5. S. N. Parragh, K. F. Doerner, R. F. Hartl. Service Technician Routing and Scheduling, VeRoLog 2014, Oslo, Norway, June 2014.
    Abstract: In field staff routing and scheduling, a given number of tasks have to be completed by a given number of field employees. Each field employee disposes of a given set of skills at a certain level and each task requires an employee with a given set of skills of at least a certain level. Some or all of the tasks have time windows and working time restrictions limit the maximum duration of an employee’s tour. The aim is to construct minimum cost routing and scheduling plans. The considered cost may be only routing cost or like in the case of the infrastructure service provider we were working with, also working time costs and outsourcing costs. In a first step, a large neighborhood search algorithm was developed for a simplified problem. This algorithm is now extended and adapted to deal with several additional requirements. These requirements involve, e.g., route synchronization constraints for tasks that require more than one technician, precedence relationships between the different tasks, and walking only subtours in large residential areas and pedestrian zones with no or only limited vehicle access. Each aspect is first treated individually and then integrated into the existing algorithm.
  6. S. N. Parragh, B. Almada-Lobo, Solving the dial-a-ride problem with split requests and profits. CO 2012, Oxford, UK, September 2012.
  7. S. N. Parragh, K. F. Doerner, .Hybridization strategies for routing problems with pairwise synchronization constraints, VeRoLog 2012, Bologna, Italy, June
  8. S. N. Parragh, J. Pinho de Sousa, B. Almada-Lobo, The dial-a-ride problem with split requests and profits, ODYSSEUS 2012, Mikonos, Greece, May 2012.
    Abstract:In the dial-a-ride problem with split requests and profits (DARPSRP), users place transportation requests, specifying a pickup location, a delivery location, and a time window for either of the two. Based on maximum user ride time considerations the second time window is generated. A given fleet of vehicles is available to serve these requests. Capacity as well as maximum route duration constraints have to be respected. Each request is associated with a revenue and the objective is to maximize the total profit, that is, the total revenue minus the total costs. Transportation requests involving several persons may be split if it is beneficial to do so. We formulate the DARPSRP as a mixed integer program and we propose several families of valid inequalities. Small instances can be solved to optimality with a commercial MIP solver. Additional instances are solved by means of a branch and price algorithm and for the solution of larger instances, a variable neighborhood search algorithm is proposed. We investigate the impact of different revenue schemes and of request splitting under different geographical settings.
  9. S. N. Parragh, Wenn zwei Servicetechniker sich treffen sollten: Tourenplanung mit Synchronisierungsnebenbedingungen Entscheidungsunterstützung in der Logistik, Salzburg, Austria, April 2012.
    Abstract: ServicetechnikerInnen wie auch HauskrankenpflegerInnen sind zumeist alleine unterwegs. Bestimmte Tätigkeiten können jedoch nur zu zweit ausgeführt werden. Für die Tourenplanung bedeutet dies, dass eine unabhängige Betrachtung einzelner Touren nicht mehr möglich ist: Es muss gewährleistet werden, dass für die Ausführung jener Tätigkeiten, die nur von zwei Personen gemeinsam erledigt werden können, beide Personen zum selben Zeitpunkt am selben Ort sind. Eine naive Vorgehensweise besteht darin für solche Tätigkeiten bestimmte Zeitpunkte vorzugeben. Allerdings, in Abhängigkeit von der Wahl dieser Zeitpunkte und der Anzahl der Tätigkeiten, die eine Synchronisierung zweier Touren verlangen, kann dies den Lösungsraum stark einschränken und so zu Tourenplänen von unnötig schlechter Qualität führen. Unter der Annahme, dass für das Basisproblem ohne Synchronisierungsnebenbedingungen bereits ein Lösungsverfahren existiert, entwickeln wir ein eigenständiges Modul, dass für zwei gegebene Touren den optimalen Einfügepunkt für eine zu synchronisierende Tätigkeit identifiziert. Im existierenden Lösungsverfahren werden zu synchronisierende Tätigkeiten mit einem fixen Zeitpunkt versehen. Das existierende Verfahren wird in festgelegten Abständen unterbrochen und Zeitpunkt und Einfügeposition jeder zu synchronisierenden Tätigkeiten wird ähnlich wie in einer lokalen Suche im Synchronisierungsmodul verbessert und an das existierende Verfahren zurück geliefert. In unserem Fall basiert das bestehende Lösungsverfahren auf dem Prinzip des Adaptive Large Neighborhood Search. Im entwickelten Modul wird das Synchronisierungssubproblem mittels dynamischer Programmierung optimal gelöst. Dieser Lösungsansatz wird einem naiven Ansatz und einem Ansatz mit zusätzlichen Modifikationen am metaheuristischen Lösungsverfahren gegenübergestellt. Die Vorteile des entwickelten Moduls aber auch seine Grenzen werden aufgezeigt.
  10. S. N. Parragh, B. Almada-Lobo, J. Pinho de Sousa, The dial-a-ride problem with split requests and profits. OR 2011, Zurich, Switzerland, Aug 30 – Sep 2, 2011.
    Abstract: In the dial-a-ride problem with split requests and profits (DARPSRP), each request is associated with a revenue and the objective is to maximize the total profit, that is, the total revenue minus the total (routing) costs. Users place transportation requests in advance of the planning. For each request a pickup and a delivery location are specified. Both locations are associated with time windows. A vehicle fleet of fixed size is used to serve these requests. Each vehicle has a given capacity and each route may not exceed a given route duration limit. Transportation requests involving several persons may be split if it is beneficial to do so. Problems of this type are encountered by taxi companies providing pooled transportation services in rural areas. We formulate the DARPSRP in terms of a mixed integer program and we propose several families of valid inequalities. Different problem properties are discussed and small problem instances are solved with CPLEX. For the solution of larger instances a variable neighborhood search (VNS) algorithm is developed.
    The shaking phase of the proposed VNS relies on three classes of neighborhoods that relocate sets of requests to different routes. Request selection is incorporated into two of them and request splitting is performed during request insertion. A local search heuristic is employed after each shaking step. It allows for request rejoining in the case where the locally optimized positioning of two request parts suggests this to be beneficial. The decision whether to move to a newly generated solution or not follows a simulated annealing type acceptance scheme. We propose a set of benchmark instances and we investigate the impact of different revenue schemes and of request splitting.
  11. S. N. Parragh, K. F. Doerner, Hybridization strategies for routing problems with synchronization constraints. MIC 2011, Udine, Italy, July 2011.
    Abstract: Route synchronization is an issue encountered in several different real life scenarios. However, the literature addressing route synchronization issues is relatively scarce. In this paper, we propose three hybridization strategies to deal with pairwise route synchronization constraints in the presence of time windows