A biased random key genetic algorithm for the field technician scheduling problem

• Published in: Computers & operations research 2016-11, Vol.75, p.49-63
• Main Authors: Damm, Ricardo B., Resende, Mauricio G.C., Ronconi, Débora P.
• Format: Article
• Language: English
• Subjects: Biased random key genetic algorithm; Comparative studies; Customizing; Genetic algorithms; Heuristic; Mathematical models; Optimization; Priorities; Problem solving; Routing and scheduling technicians; Scheduling; Tasks; Technical support; Time windows
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2016.05.003

This paper addresses a problem that service companies often face: the field technician scheduling problem. The problem considers the assignment of a set of jobs or service tasks to a group of technicians. The tasks are in different locations within a city, with different time windows, priorities, and processing times. Technicians have different skills and working hours. The main objective is to maximize the sum of priority values associated with the tasks performed each day. Due to the complexity of this problem, constructive heuristics that explore specific characteristics of the problem are developed. A customized Biased Random Key Genetic Algorithm (BRKGA) is also proposed. Computational tests with 1040 instances are presented. The constructive heuristics outperformed a heuristic of the literature in 90% of the instances. In a comparative study with optimal solutions obtained for small-sized problems, the BRKGA reached 99% of the optimal values; for medium- and large-sized problems, the BRKGA provided solutions that are on average 3.6% below the upper bounds. •A problem that service companies often face is tackled: the scheduling of technicians.•The sum of priority values associated with the tasks performed each day is maximized.•A BRKGA combined with elaborated decoders and with an unusual elite set is proposed.•Numerical experiments show that the proposed methods provide high quality solutions.