Méthodes de résolution exactes et heuristiques pour un problème de tournées de techniciens

Abstract

Les problèmes de tournées de techniciens (TRSPs pour Technician Routing and Scheduling Problems) consistent à planifier les routes d’un groupe de techniciens afin de servir des requêtes de clients à moindre coût. Ce sont des problème d’optimisation NP-difficiles rencontrés dans plusieurs domaines d’application, tels que les télécommunications, les services publics et les opérations de maintenance. Chaque application a ses propres attributs, contraintes et objectifs. Malgré la place qu’occupent les TRSPs dans l’industrie, ils n’ont pas été beaucoup étudié par les chercheurs. En effet, modéliser et résoudre de tels problèmes pour des entreprises posent d’importants défis. Cette thèse s’intéresse ainsi à la modélisation et à la résolution d’un TRSP multi-attributs (MATRSP) motivé par une application où différents types d’équipements permettant de réaliser des transactions électroniques doivent être servis par des techniciens. Il s’agit de répartir et ordonnancer les appels de service pour la maintenance de ces systèmes, en tenant compte de différents attributs, soit les compétences des techniciens, les priorités des tâches, les fenêtres de temps multiples pour le service, l’inventaire des pièces de rechange, ainsi que les pauses et les heures supplémentaires des techniciens. Nous présentons tout d’abord un modèle de programmation linéaire en nombres entiers mixtes pour ce problème, qui est ensuite résolu avec un solveur commercial. Puis, un algorithme exact de branch-and-price est proposé pour traiter des problèmes de plus grande taille. Enfin, une méta-heuristique est développée combinant des idées provenant de différentes sources et intégrant en particulier une recherche tabou, une mémoire adaptative et une évaluation des solutions basée sur leur coût et leur contribution à la diversité des solutions dans la mémoire.

Technician Routing and Scheduling problems (TRSPs) involve the routing and scheduling of a group of technicians in order to serve requests at minimum cost. These NP-Hard problems are encountered in different domains, like telecommunications, public services, maintenance operations and many others. Each application brings its own attributes, constraints and objectives. Despite the importance of TRSPs in practice, they have not received much attention from researchers, because modeling and solving these problems pose important challenges. This thesis is about modeling and solving a multi-attribute TRSP (MATRSP) motivated from an application in which various types of electronic transaction equipments must be serviced by technicians. This problem consists of routing technicians to serve maintenance requests, while taking into account many attributes like technician skills, task priorities, multiple time windows, parts inventory, breaks and overtime. We first develop a mixed integer linear programming model (MIP) for this problem which is then solved directly with a commercial solver. Then, medium-sized problem instances are tackled through a column generation scheme embedded in a branch-and-price algorithm. For instances of practical size, we finally propose a metaheuristic approach that combines ideas from several sources, including a tabu search, an adaptive memory and a solution evaluation based on its cost and its contribution to the memory diversity.