Reproduction de : Thèse de doctorat : Automatique et informatique industrielle : Villeneuve d'Ascq, Ecole centrale de Lille : 2006. / Titre provenant de la page de titre du document numérisé. Bibliogr. p. 183-194. Index.

De nos jours, les services de livraison à domicile deviennent de plus en plus sollicités an de répondre aux besoins des clients qui cherchent à recevoir leurs produits dans les plus brefs délais et avec des coûts raisonnables. Les entreprises œuvrant dans le domaine de la livraison à domicile ont différentes manières de proposer des fenêtres de temps à leurs clients. Certains, comme les bannières à rabais, ont comme objectif d'offrir des solutions de transport au coût minimal. Ces entreprises offrent très peu de flexibilité à leurs clients quant aux modalités de livraison. Ainsi, certains clients pourraient faire leurs achats chez d'autres détaillants qui offrent un meilleur service. D'autres entreprises offrent plus de flexibilité aux clients en mettant à leur disposition un large éventail de fenêtres de temps où pourrait avoir lieu leur livraison. Cette manière de procéder engendre forcément des coûts additionnels, car les conducteurs feront des livraisons dans leurs secteurs plusieurs fois par semaine. Ces coûts seront alors transférés dans les prix de vente de l'entreprise. Ces deux exemples constituent deux méthodes extrêmes pour planifier les livraisons. L'un priorise davantage les coûts au détriment de la satisfaction des clients. Le deuxième effectue le contraire en misant davantage sur la satisfaction des clients au prix d'avoir des coûts de transport plus élevés. Ce mémoire a pour objectif de proposer de nouvelles techniques pour offrir un compromis entre ces deux extrémités. Ces techniques auront pour but d'offrir plusieurs de choix aux clients tout en essayant de maintenir des coûts de livraison qui sont bas. Notre schéma de résolution s'effectue en deux temps : 1. Nous utiliserons des heuristiques pour générer des calendriers de livraison, 2. Nous simulerons des arrivées de clients desquels nous calculerons différentes valeurs pour mesurer la satisfaction du client avec les coûts de transport. Les résultats seront interprétés de manière à regarder tous les aspects techniques et comparer la satisfaction avec les coûts de transport. Mots clés : Livraison à domicile, satisfaction client, tournée de véhicules, offre de fenêtres de temps. / Nowadays, home delivery services have become more and more requested in order to respond to the needs of customers seeking to receive their products as quickly as possible and at a reasonable cost. Home delivery companies have di erent ways of offering time windows to their customers. Some, such as discount banners, aim to provide transportation solutions at minimal cost. These companies offer very little exibility to their customers regarding delivery terms. That's why, some customers could shop at other retailers who offer better service. Other companies offer customers more exibility by providing a wide range of time windows where their delivery could take place. This way of doing things inevitably entails additional costs, since drivers will make deliveries to their zones several times a week. These costs will then be transferred to the sales prices of the company. These two examples are two extreme methods for scheduling deliveries. One prioritizes costs at the expense of customer satisfaction. The second is doing the opposite by focusing more on customer satisfaction at the cost of higher transportation costs. This thesis has as objective to propose new techniques to offer a compromise between these two ends. These techniques will aim to offer many choices to customers while trying to keep shipping costs low. Our resolution scheme is done in two stages: 1. We will use heuristics to generate delivery schedules, 2. We will simulate customer arrivals from which we will calculate different values to measure customer satisfaction with transportation costs. The results will be interpreted in a way that looks at all technical aspects and compares satisfaction with transportation costs. Keywords: Home delivery, customer satisfaction, vehicle routing problem, time windows offer.

Le problème de tournée de véhicules (VRP) est un problème classique d'optimisation en recherche opérationnelle et logistique. Il consiste à concevoir des itinéraires efficaces pour une flotte de véhicules afin de desservir plusieurs clients tout en minimisant les coûts de transport et en respectant la capacité des véhicules. Dans le monde réel, les entreprises font face à des problèmes plus complexes qui nécessitent la résolution de problèmes de tournée de véhicules riches. Ces problèmes sont des variantes du VRP qui intègrent des modèles et des approches de solution adaptés aux contraintes et caractéristiques spécifiques à chaque entreprise. Cependant, la complexité de ces variantes riches augmente significativement par rapport aux VRP traditionnels, ce qui peut entraîner des coûts élevés en termes de puissance de calcul et de temps d'exécution. Il est donc crucial pour les entreprises de logistique d'optimiser efficacement leurs opérations de livraison, de ramassage ou de transport, tout en tenant compte de leurs contraintes spécifiques. Cela nécessite des investissements dans des méthodes avancées d'optimisation pour trouver un compromis acceptable entre l'efficacité opérationnelle, les économies de coûts, la satisfaction client et la réduction de l'impact environnemental. Cette thèse s'intéresse à trois variantes distinctes du problème de tournée de véhicules et propose des modèles mathématiques et des approches de solution utilisant des techniques de recherche opérationnelle. La motivation de cette recherche découle d'une collaboration avec des partenaires industriels et de l'identification de certains aspects à explorer dans la littérature existante. Le premier chapitre de la thèse traite de la résolution d'un problème rencontré par les entreprises de distribution de meubles et d'électronique qui offrent des services d'installation à leurs clients. Ce problème est un problème de tournée de véhicules avec des fenêtres de temps et des contraintes de synchronisation entre deux flottes distinctes de livreurs et d'installateurs. Pour le résoudre, nous avons développé un modèle de programmation linéaire en nombres entiers mixtes et utilisé un algorithme de branch-and-bound ainsi qu'une heuristique de recherche à grand voisinage pour trouver des solutions quasi-optimales. Des expérimentations numériques ont fourni des informations précieuses sur la manière dont une entreprise peut réduire ses coûts liés à son offre de service d'installation tout en minimisant la distance parcourue. De plus, nous avons généralisé deux problèmes existants dans la littérature sur le VRP avec la nouvelle variante étudiée. Cela nous a permis d'utiliser nos algorithmes développés pour résoudre ces problèmes et d'établir de nouvelles bornes inférieures et supérieures pour leurs solutions. Le second chapitre aborde la planification efficace de bétonnières livrant du béton prêt à l'emploi sur des chantiers de construction. Le problème implique de concilier des objectifs contradictoires tels que la minimisation des coûts de transport, la maximisation de la satisfaction du client et le respect des horaires des conducteurs. Il faut également prendre en compte des contraintes réalistes telles que les quarts de travail des conducteurs, les heures minimales de travail et les pénalités pour heures supplémentaires. De plus, la planification devient plus complexe lorsque les clients demandent la livraison de plusieurs types de béton dans la même fenêtre de temps. Pour résoudre ce problème rencontré par un partenaire industriel au Québec, nous proposons une formulation mathématique et une approche de solution heuristique. Nous évaluons notre heuristique en utilisant des données spécifiquement générées pour le problème ainsi que des données de référence d'une autre variante connexe. Le dernier chapitre de la thèse aborde un problème de conception de réseaux de distribution en se concentrant sur le problème de localisation et de tournée de véhicules à deux échelons, en tenant compte de l'incertitude de la demande. Nous concevons un réseau de distribution à deux échelons avec des dépôts et des satellites capables d'accommoder des demandes incertaines des clients. Simultanément, nous nous assurons que les itinéraires planifiés restent réalisables pour toutes les valeurs futures de la demande qui seront à l'intérieur d'un ensemble d'incertitude en utilisant des techniques d'optimisation robuste. Pour résoudre ce problème, nous introduisons une formulation robuste pour un modèle mathématique intégré, et utilisons une heuristique de recherche à grand voisinage ainsi qu'un algorithme de branch-and-cut. De plus, nous proposons quatre approches de solution non intégrées basées sur des formulations robustes des problèmes de tournée de véhicules, de localisation de sites, de localisation et de routage, et de localisation de site à deux échelons. Nous comparons l'approche intégrée aux méthodes non intégrées et évaluons le coût de la robustesse ainsi que le compromis entre des solutions robustes plus conservatrices et plus risquées en effectuant des simulations Monte Carlo. En résumé, cette étude enrichit la littérature sur les problèmes de tournées de véhicules, de livraison de béton, de localisation et de tournées de véhicules à deux échelons, ainsi que sur l'optimisation robuste, en proposant des algorithmes efficaces pour résoudre des problèmes ayant des applications pratiques dans les secteurs de la logistique et de la construction. / The Vehicle Routing Problem (VRP) is a classic optimization problem in operations research and logistics. It involves designing efficient routes for a fleet of vehicles to serve multiple customers while minimizing transportation costs and respecting vehicle capacities. In the real world, companies face more complex issues that require solving rich VRPs. These problems are variants of the VRP that incorporate models and solution approaches tailored to the constraints and specific characteristics of each company. However, the complexity of these rich variants increases significantly compared to traditional VRPs, resulting in high computational cost and execution time. Therefore, it is critical for logistics companies to optimize their delivery, pickup, or transportation operations while taking into account their specific constraints. This requires investing in advanced optimization methods to find an acceptable trade-off between operational efficiency, cost savings, customer satisfaction, and reduced environmental impact. In this thesis, we focus on addressing three distinct variants of the Rich VRP and providing models and solutions using operations research techniques. Our research was motivated by our collaboration with industrial companies and the identification of gaps in the existing literature. We first study a real-world problem faced by companies that provide installation services when distributing furniture and electronics. This problem is a VRP with time windows and synchronization constraints between two distinct delivery and installation fleets. To solve this problem, we develop a mixed-integer linear programming model and employ a branch-and-bound algorithm and adaptive large neighborhood search metaheuristic to find near-optimal solutions. Extensive computational experiments provide valuable insights into how a company can reduce its costs related to its installation service while minimizing the total distance traveled. The variant we studied is a generalization of two existing problems in the VRP literature, so we applied our developed algorithms to solve these problems and provided new lower and upper bounds for their solutions. Next, we address the problem of efficiently scheduling concrete mixers to deliver ready-mixed concrete to construction sites. The problem involves balancing conflicting objectives: minimizing transportation costs, maximizing customer satisfaction, while respecting driver schedules. Realistic constraints must be considered, including driver work shifts, minimum working hours, and overtime penalties. Additionally, scheduling becomes more complex when customers request multiple types of concrete to be delivered within the same time window. To solve this concrete delivery problem faced ivby an industrial partner in Quebec, we propose a mathematical formulation and a heuristic solution approach. We evaluate our proposed heuristic using instances specifically generated for the problem, as well as benchmark instances from another related variant. Finally, we study a problem in the design of distribution networks: the two-echelon capacitated location routing problem under demand uncertainty. We design a distribution network with open depots and satellites capable of accommodating uncertain customer demands at the second echelon. Simultaneously, we ensure that planned routes remain feasible for all values within an uncertainty set using the robust optimization methodology. To solve this uncertain problem, we introduce a robust counterpart for an integrated model and employ an adaptive large neighborhood search and branch-and-cut algorithms to find near-optimal solutions. Additionally, we propose four non-integrated solution approaches based on robust counterparts for the VRP, facility location problem, location routing problem, and two-echelon facility location problem. We compare the integrated approach to non-integrated methods and evaluate the cost of robustness and the trade-off between conservative and riskier robust solutions using Monte Carlo simulations. Overall, this thesis provides valuable contributions to the fields of VRP, Concrete Delivery Problem, Two-Echelon Location Routing Problem, and Robust Optimization by developing efficient algorithms for solving real-world problems with practical applications in the logistics and construction industries.