Article Preview
TopIntroduction
The multi-attribute Technician Routing and Scheduling Problem (MA-TRSP), which is a special case of the TRSP, consists on routing technicians to serve customers requests taking into account different constraints. The TRSP is first considered in 1997 by Tsang and Voudouris (1997). It belongs to the Vehicle Routing Problems (VRP) and is related in particular to the VRP with Time windows. There are, however, significant differences such as large service times and parts inventory. Despite their numerous practical applications, TRSP has received limited attention in the literature compared to the VRP.
Weigel and Coo (1999) introduce the TRSP faced by a well-known retailer when providing on-site technical assistance. The proposed solution consists of assigning requests to technicians and then optimizing each route individually through Or-opt exchanges (Or, 1976). Blakeley et al. (2003) solve a periodic maintenance problem faced by the Schindler Elevator Corporation for their elevators and escalators. In this application, the technician routes must account for technician skills, travel times and working regulations. A similar application was addressed by Tang et al. (2007) with a tabu search heuristic. In 2007, the French Operations Research Society (ROADEF) initiated a challenge based on a problem encountered by France Telecom. The participants had to schedule technician tours on a multiple-day horizon. The particularity of this problem is that each task needs one or more skills with different proficiency levels, while technicians can have multiple skills. To solve this problem, teams of technicians working together must be created. However, the routing aspect of the problem is ignored. Based on this challenge, Hashimioto et al. (2011) developed a GRASP for this problem while Cordeau et al. (2010) proposed a mathematical model and a problem-solving methodology based on an adaptive large neighbourhood search (ALNS).
Bostel et al. (2008) introduce a problem faced by Veolia, a water treatment and distribution company. In this problem, technician routes must be planned over a period of one week for repair or maintenance. The tasks to be scheduled can either be known in advance (preventive maintenance) or can occur dynamically. Each task has a time window for service. The first proposed method is a memetic algorithm, which is first applied on static tasks to produce tours for every day of the week. Dynamic tasks are then integrated into the solution when they occur, still using the memetic algorithm. The second approach is based on a column generation algorithm which can only be applied to problem instances of small size.
Pillac et al. (2012) also address a TRSP in which a fraction of the tasks occur dynamically. A parallel architecture is proposed to speed up the calculations. An initial solution is first created with known tasks using a regret constructive heuristic (Potvin, 1993). This solution is then improved with ALNS (Pisinger, 2007).