Problèmes tactiques et stratégiques en tournées sur arc

Cette thèse étudie des extensions d'un problème bien connu en recherche opérationnelle : le problème de tournées sur arcs (CARP). Le CARP consiste à déterminer des tournées pour servir les arcs (rues) d'un réseau. Il a de nombreuses applications telles que la collecte de déchets urbains, le salage des routes, etc, mais c'est un problème à court terme comme il concerne un horizon constitué d'un seul jour. Le CARP périodique (PCARP) est le premier problème examiné dans ce travail, il généralise le CARP à un horizon multipériode. Dans ce problème des jours de service doivent être affectés aux rues sous contraintes additionnelles avant de construire les tournées de chaque jour, pour minimiser le coût total et la taille de la flotte utilisée. Le second problème que nous avons défini et étudié dans cette thèse est dénoté CLARP (Capacitated Location Arc Routing Problem). Il concerne les niveaux de décision stratégique, tactique et opérationnel et consiste à déterminer les emplacements des dépôts à partir desquelles les tournées doivent être établies. Nous avons proposé des modèles mathématiques, bornes inférieures et heuristiques constructives pour le PCARP et CLARP. Une méthode de recherche dispersée (Scatter Search) a été conçue pour le PCARP et une méthode de descente à voisinage variable a été proposée pour le CLARP. Ces méthodes ont été validées sur de nouveaux jeux d'essaiThis thesis studies extensions of a well-known problem in operations research : the Capacitated Arc Routing Problem (CARP). The CARP involves the routing of vehicles to service a set of arcs (streets) of a network. It has many applications such as waste collection, salt gritting...etc, but it is a short-term problem since it concerns an horizon of one day. The Periodic CARP (PCARP) is the first problem investigated in this work, it extends the CARP to a multiperiod horizon. In this problem, service days must be assigned to the streets under additional constraints before building the trips in each day, to minimise the total routing cost and the fleet size. The second problem that we defined and studied in this thesis is denoted CLARP for Capacitated Location Arc Routing Problem. It involves both strategic, tactical and operational decision levels and consists of determining the positions of depots on the network, from which vehicle trips must be built. We have proposed mathematical models, lower bounds and constructive heuristics for both PCARP and CLARP. A scatter search metaheuristic is conceived for the PCARP and a variable neighbor descent method is proposed for the CLARP. These methods are validated on new benchmark instancesTROYES-SCD-UTT (103872102) / SudocSudocFranceF