ELITE NETZWERK BAYERN

English  Sprachen Icon  |  Gebärdensprache  |  Leichte Sprache  |  Kontakt


Forschungsarbeit

Conception, implementation and comparison of heuristics to solve the Field Force Scheduling Problem

By Ioannis Petrakis (28.08.2011)

There have been a number of initiatives recently in industry and academia to focus on innovation in the service sector, which is the largest sector of the economy in most industrialized nations (Spohrer, et al. 2007). Arguably, one of the biggest challenges in many large service organizations is the allocation of employees to tasks.

In this thesis, we focus on a particular task assignment problem, which arises when mobile workforce has to finish tasks with priorities that are spatially distributed. As a real-world example, we focus on the daily planning problem of a European mobile phone provider. The operator has almost 20,000 mobile phone base stations, which need maintenance, irregular upgrades, or need to be repaired immediately in case of a failure. The tasks are carried out by several hundred engineers (Figure 1). Each day, the engineers start at their home location, complete three to five maintenance or repair tasks, and return to their home again within eight hours. Each task requires a specific set of skills, and each engineer possesses a number of skills. Tasks also have priorities which depend on the nature of the task (i.e. service affecting disturbances have high priority) and their due date. Every morning the scheduler assigns tasks to field engineers and suggests a route for the day. The schedules are subject to change if important tasks arrive dynamically during the day and need immediate treatment. We will refer to the problem as field service scheduling with priorities (FSSP). While we draw on real data from the mobile phone operator, similar problems can be found in other industries with distributed repair and maintenance tasks such as in the energy or utilities industry.

 

Figure 1: The FSSP: 20,000 mobile phone base stations (blue) have to be maintained and repaired by 200 engineers (red).[Bildunterschrift / Subline]: Figure 1: The FSSP: 20,000 mobile phone base stations (blue) have to be maintained and repaired by 200 engineers (red).

The FSSP has similarities with different types of vehicle routing problems (VRP), such as the Multi-Depot Vehicle Routing Problem (MDVRP). These problems are NP-hard and can only be solved exactly for rather small instances, as has been shown in experimental analyses (Cordeau, Gendreau and Laporte 1997), (Scheurer 2004). But the FSSP has also a number of notable differences. For example, in each depot only one engineer is located; the problem is defined over several periods (days) and the same vehicle (engineer) must be routed on each day resulting in multiple routes for each vehicle; the tasks have deadlines and associated deadline penalties, rather than time windows; there are no truck load capacities that need to be considered for each vehicle, but service times need to be considered, not only travel times. Some of these differences have a profound impact on the design of specific heuristics and exact algorithms to solve the problem.

Priorities and time limits do not only influence the design of an algorithm for the planning stage each morning. Urgent tasks arising during the day need to be allocated to a field engineer as soon as possible, which causes deviations from the planned schedule. Also, routes might have to be rescheduled in response to interruptions due to traffic delays or weather conditions, which can lead to significant deviations from plans. Overall, the computational complexity of the planning problem and the stochastic nature of travel and service times for individual tasks remained a barrier for the application of advanced algorithmic solutions and respective decision support systems in industry. Stochastic versions of VRPs have been analyzed in the literature, but not yet used widely in practice, possibly due to the distributional assumptions a planner needs to make.

In summary, the contributions of this work are three-fold: We will first provide a mixed-integer program and provide a succinct formal problem description of the FSSP. Unfortunately, standard branch-and-bound or branch-and-cut approaches can only solve very small instances of the problem, as will be shown. Therefore, we will suggest heuristics for the FSSP that can be used to solve the problem statically every morning or dynamically throughout the day, if the tasks are not known a priori. Finally, we will provide the results of an experimental evaluation, in which we compare offline, dynamic and hybrid scheduling approaches. The results have managerial impact, as they help to explain the benefits of dynamic scheduling as compared to traditional daily offline planning, as well as the relative advantages of different algorithms.

 


Stationen
  • Seit 02/2010
  • Technische Universität München, Lst. Decision Sciences and Systems (Prof.Dr.Bichler), Wissenschaftlicher Mitarbeiter
  • 2007 - 2010
  • Universität Augsburg und TU München, Elite Graduate Program Finance & Information Management
  • 01/2008 - 03/2008
  • o2 Germany, München, Operations Support Systeme
  • 12/2003 - 11/2004
  • Siemens AG, Athen, Programmierung von Simulationen von Telefonanrufen
  • 2001 - 2006
  • National Technical University of Athens, Studium der Elektrotechnik und Informatik