Méthodes de résolution exactes et heuristiques pour un problème de tournées de techniciens
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.
Logistique problème de tournées de techniciens programmation linéaire en nombres entiers mixtes branch-and-price recherche tabou branch-and-price