An Efficient VNS Algorithm to Solve the Multi-Attribute Technician Routing and Scheduling Problem

An Efficient VNS Algorithm to Solve the Multi-Attribute Technician Routing and Scheduling Problem

Sana Frifita (Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems (MODILS), Sfax, Tunisia), Ines Mathlouthi (Department of Computer Science and Operations Research, University of Montreal, Canada) and Abdelaziz Dammak (Laboratory of Modeling and Optimization for Decisional, Industrial and Logistic Systems (MODILS), Sfax, Tunisia)
Copyright: © 2020 |Pages: 13
DOI: 10.4018/IJAMC.2020010102


This article addresses a technician routing and scheduling problem inspired from an application for the repair of electronic transactions equipment. It consists of designing routes for staff to perform requests while considering certain constraints and resources. The objective is to minimize a linear combination of total weighted distance, overtime, and maximize the served requests. An efficient meta-heuristic algorithm based on variable neighborhood search with an adaptive memory and advanced diversity management method is proposed. Numerical results show that the meta-heuristic outperforms the best existing algorithm from the literature which is a Tabu Search.
Article Preview


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).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing