Show item record

dc.contributor.advisorPotvin, Jean-Yves
dc.contributor.advisorGendreau, Michel
dc.contributor.authorMathlouthi, Ines
dc.date.accessioned2018-06-11T15:37:06Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2018-06-11T15:37:06Z
dc.date.issued2018-05-10
dc.date.submitted2017-12
dc.identifier.urihttp://hdl.handle.net/1866/20484
dc.subjectLogistiquefr
dc.subjectproblème de tournées de techniciensfr
dc.subjectprogrammation linéaire en nombres entiers mixtesfr
dc.subjectbranch-and-pricefr
dc.subjectrecherche taboufr
dc.subjectLogisticsfr
dc.subjecttechnician routing and scheduling problemfr
dc.subjectmixed integer linear programmingfr
dc.subjectbranch-and-pricefr
dc.subjecttabu searchfr
dc.subject.otherApplied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)fr
dc.titleMéthodes de résolution exactes et heuristiques pour un problème de tournées de techniciensfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelDoctorat / Doctoralfr
etd.degree.namePh. D.fr
dcterms.abstractLes 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.fr
dcterms.abstractTechnician 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.fr
dcterms.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record