A biased random key genetic algorithm for the field technician scheduling problem. (November 2016)

• Record Type: Journal Article
• Authors: Damm, Ricardo B.; Resende, Mauricio G.C.; Ronconi, Débora P.
• Is Part Of: Computers & operations research. Volume 75(2016)
• Page Start: 49
• Page End: 63
• Publication Date: 2016-11
• Subjects: Routing and scheduling technicians -- Time windows -- Heuristic -- Biased random key genetic algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.05.003
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Abstract : Highlights: 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.