L'efficacité du transport des marchandises en ville est un sujet complexe préoccupant les autorités locales depuis de nombreuses années. Les enjeux sont immenses, une meilleure organisation du trafic devant permettre d'augmenter la sécurité, réduire les nuisances, minimiser les coûts. La Logistique Urbaine vise à concevoir des systèmes de distribution des marchandises en ville permettant d'acheminer les flux dans les meilleures conditions à la fois pour la communauté et les transporteurs. Cette thèse se deroule dans le cadre du projet ANR MODUM qui propose un système basé sur un anneau de Centres de Distribution Urbains (CDU) situés autour d'une ville. La première partie étudie ce système d'un point de vue stratégique et tactique. Le Multicommodity-Ring Location Routing Problem aborde les décisions concernants l'installation et la connexion en anneau des CDU en simplifiant les détails plus tactiques. Trois méthodes ont été developpées et testées sur un jeu d'instances exhaustif se révélant très efficaces. The Multicommodity-Ring Vehicle Routing Problem est le problème dérivé que l'on obtient quand l'anneau est fixé. Une approche de type Branch&Price est proposée pour ce problème. La deuxième partie porte sur le Vehicle Routing Problem with Intermediate Replenishment Facilities, un problème plus tactique qui se produit dans un système logistique lorsque les véhicules peuvent se recharger auprès des points de remplissage et effectuer plusieurs tournées lors d'une même journée. Plusieurs algorithmes exacts ont été developpés et testés. Les résultats obtenus sur des jeux d'instances tirés de la littérature sont prometteurs. / Urban freight transport is a matter of increasing concern in the economic, commercial, social and environmental operations of our cities, due to the constantly increasing growth and urbanization of the civilization. An improved managem ent of the traffic related to the freight transport can have a positive impact in many respects : security, congestion of the road network, noise and air pollution, costs. City Logistics studies the dynamic management of urban freight transport in order to deliver distribution systems solutions that may be suitable for both the community and freight carriers. This thesis originates from the ANR Project MODUM, which proposes a freight distribution system based on a ring of Urban Distribution Centers (UDCs) located in the outskirts of a city. In the first part, this system is studied from both a strategic and a tactical point of view. The Multicommodity-Ring Location Routing Problem (MRLRP) considers long-term decisions, i.e. the installation of the UDCs and the ring connection, without disregarding more tactical aspects. The MRLRP has been tackled by three solution methods, which proved effective on a large set of test instances. In the second part of the thesis, the Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is studied. The VRPIRF is a more tactical problem that arises in City Logistics each time both the multi-trip and the multi-depot features, i.e. the possibility for a vehicle to be reloaded at one of a set of facilities, are present. Several exact algorithms, namely two of type Branch&Cut and two of type Branch& Price, have been developed for this problem. computational experiments on benchmark instances taken from the literature have been conducted to assess their performance, leading to very promising results.

L'objet de notre projet de recherche est le développement d'un modèle de conception d'un réseau de distribution composé de trois niveaux : les usines, les centres de distribution (CD) et les clients. Nous supposons que le nombre et la localisation des usines ainsi que le nombre et la localisation des clients sont connus. Etant donné la demande des clients et une liste de CD potentiels, l'objectif est de déterminer la localisation des CD à ouvrir et d'y affecter les clients de manière à minimiser le coût total. En termes de modélisation, nous considérons divers aspects opérationnels qui sont inspirés d'une étude de cas dans l'industrie automobile. Ces aspect ont été pris en compte séparément dans la littérature mais jamais combinés dans un même modèle. Plus particulièrement, nous introduisons un " clustering " en prétraitement afin de modéliser les tournées de camions. Nous intégrons également des contraintes de volume minimum sur les axes de transport, des contraintes de volume minimum et de capacité maximale sur les centres de distribution, des contraintes de distance de couverture maximale et des contraintes d'uni-affectation. Par ailleurs, nous étudions une extension multi-périodes du problème en utilisant un " clustering " dynamique pour modéliser des tournées de camions multi-périodes. En termes de résolution, comme le problème étudié est NP-difficile au sens fort, nous proposons différentes méthodes heuristiques performantes basées sur la relaxation linéaire. A travers les tests effectués, nous montrons que ces méthodes fournissent des solutions proches de l'optimale en moins de temps de calcul que l'application directe d'un solveur linéaire. Nous analysons également la structure des réseaux de distribution obtenus et nous comparons les résultats issus de plusieurs versions du modèle afin de montrer la valeur ajoutée du " clustering " ainsi que de l'approche multi-périodes.

L’objet de notre projet de recherche est le développement d’un modèle de conception d’un réseau de distribution composé de trois niveaux : les usines, les centres de distribution (CD) et les clients. Nous supposons que le nombre et la localisation des usines ainsi que le nombre et la localisation des clients sont connus. Etant donné la demande des clients et une liste de CD potentiels, l’objectif est de déterminer la localisation des CD à ouvrir et d’y affecter les clients de manière à minimiser le coût total. En termes de modélisation, nous considérons divers aspects opérationnels qui sont inspirés d’une étude de cas dans l’industrie automobile. Ces aspect ont été pris en compte séparément dans la littérature mais jamais combinés dans un même modèle. Plus particulièrement, nous introduisons un « clustering » en prétraitement afin de modéliser les tournées de camions. Nous intégrons également des contraintes de volume minimum sur les axes de transport, des contraintes de volume minimum et de capacité maximale sur les centres de distribution, des contraintes de distance de couverture maximale et des contraintes d’uni-affectation. Par ailleurs, nous étudions une extension multi-périodes du problème en utilisant un « clustering » dynamique pour modéliser des tournées de camions multi-périodes. En termes de résolution, comme le problème étudié est NP-difficile au sens fort, nous proposons différentes méthodes heuristiques performantes basées sur la relaxation linéaire. A travers les tests effectués, nous montrons que ces méthodes fournissent des solutions proches de l’optimale en moins de temps de calcul que l’application directe d’un solveur linéaire. Nous analysons également la structure des réseaux de distribution obtenus et nous comparons les résultats issus de plusieurs versions du modèle afin de montrer la valeur ajoutée du « clustering » ainsi que de l’approche multi-périodes. / The purpose of our research project is to develop a distribution network design model taking into account many realistic features arising from a case-study in the field of car distribution. The overall network structure consists of three levels: plants, distribution centres (DCs) and customers. We assume that the number and location of the plants as well as the number and location of the customers are fixed. Given the demand of customers and a list of potential DCs, our main concern is to locate DCs and to assign customers to them in such a way as to minimize the total distribution costs. In terms of problem modeling, we integrate various operational features that were considered separately in the literature but have never been combined in a same model. Namely, we introduce a clustering-based approach to model vehicle routing, minimum volume constraints to ensure full truckload transport, minimum and maximum throughput constraints on DCs, maximum covering distance constraints and single sourcing restrictions. Furthermore, we study a multi-period extension of the problem using an original dynamic clustering to model multi-period vehicle routing. In terms of solution method, as the problem we study is NP-hard in the strong sense, we propose efficient heuristic procedures based on various types of linear relaxation. Through our numerical experiments, we show that the implemented heuristics offer near-optimal solutions with less computational effort than applying an exact MIP solver. We also analyze the structure of the obtained networks and compare the results of several versions of the model, highlighting the value of integrating a pre-processing clustering step and of using a multi-period approach.