Méthodes de résolution exactes et heuristiques pour un problème de tournées de techniciens
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.
branch-and-price Logistics technician routing and scheduling problem mixed integer linear programming branch-and-price tabu search