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

作者：Damm Ricardo B; Resende Mauricio G C; Ronconi Debora P^*

来源：Computers & Operations Research, 2016, 75: 49-63.

DOI：10.1016/j.cor.2016.05.003

• Routing and scheduling technicians
• Time windows
• Heuristic
• Biased random key genetic algorithm

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.

• 出版日期2016-11