A metaheuristic based on tabu search for solving a technician routing and scheduling problem. (January 2021)

• Record Type: Journal Article
• Authors: Mathlouthi, Ines; Gendreau, Michel; Potvin, Jean-Yves
• Is Part Of: Computers & operations research. Volume 125(2021)
• Publication Date: 2021-01
• Subjects: Technician routing and scheduling -- Tabu search -- Adaptive memory -- Biased fitness; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105079
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A technician routing and scheduling problem is solved with a tabu search-based metaheuristic. The problem has specific features like parts inventory and multiple time windows. The tabu search uses an adaptive memory that accounts for solution quality and diversity. Results are reported on problem instances with up to 200 tasks. A comparison with a branch-and-price algorithm is reported on small instances. Abstract: This paper addresses a technician routing and scheduling problem motivated by an application for the repair and maintenance of electronic transactions equipment. The problem exhibits many special features like multiple time windows for service, an inventory of spare parts carried by each technician and tasks that may require a special part to be performed. A problem-solving methodology based on tabu search, coupled with an adaptive memory, is proposed. The inclusion of solutions (local minima) in the adaptive memory takes into account both quality and diversity. Results are reported on test instances with up to 200 tasks. A comparison with a previously developed branch-and-price algorithm is also reported on instances of small size.