Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Le problème de tournées de véhicules est un des problèmes d’optimisation combinatoire les plus connus et les plus difficiles. Il s’agit de déterminer les tournées optimales pour une flotte de véhicules afin de servir un ensemble donné de clients. Dans les problèmes classiques de transport, chaque client est normalement servi à partir d’un seul nœud (ou arc). Pour cela, on définit toujours un ensemble donné de nœuds (ou arcs) obligatoires à visiter ou traverser, et on recherche la solution à partir de cet ensemble de nœuds (ou arcs). Mais dans plusieurs applications réelles où un client peut être servi à partir de plus d’un nœud, (ou arc), les problèmes généralisés qui en résultent sont plus complexes. Le but principal de cette thèse est d’étudier trois problèmes généralisés de tournées de véhicules. Le premier problème de la tournée sur arcs suffisamment proche (CEARP), comporte une application réelle intéressante en routage pour le relevé des compteurs à distance ; les deux autres problèmes, problème de tournées couvrantes multi-véhicules (mCTP) et problème généralisé de tournées sur nœuds (GVRP), permettent de modéliser des problèmes de conception des réseaux de transport à deux niveaux. Pour résoudre ces problèmes, nous proposons une approche exacte ainsi que des métaheuristiques. Pour développer la méthode exacte, nous formulons chaque problème comme un programme mathématique, puis nous construisons des algorithmes de type branchement et coupes. Les métaheuristiques sont basées sur le ELS (ou Evolutionary Local Search) et sur le GRASP (ou Greedy Randomized Adaptive Search Procedure). De nombreuses expérimentations montrent la performance de nos méthodes. / The Routing Problem is one of the most popular and challenging combinatorial optimization problems. It involves finding the optimal set of routes for fleet of vehicles in order to serve a given set of customers. In the classic transportation problems, each customer is normally served by only one node (or arc). Therefore, there is always a given set of required nodes (or arcs) that have to be visited or traversed, and we just need to find the solution from this set of nodes (or arcs). But in many real applications where a customer can be served by from more than one node (or arc), the generalized resulting problems are more complex. The primary goal of this thesis is to study three generalized routing problems. The first one, the Close-Enough Arc Routing Problem(CEARP), has an interesting real-life application to routing for meter reading while the others two, the multi-vehicle Covering Tour Problem (mCTP) and the Generalized Vehicle Routing Problem(GVRP), can model problems concerned with the design of bilevel transportation networks. The problems are solved by exact methods as well as metaheuristics. To develop exact methods, we formulate each problem as a mathematical program, and then develop branch-and-cut algorithms. The metaheuristics are based on the evolutionary local search (ELS) method et on the greedy randomized adaptive search procedure (GRASP) method. The extensive computational experiments show the performance of our methods.

Dans cette thèse, nous nous intéressons à la gestion des flux de marchandises en zone urbaine aussi appelée logistique du dernier kilomètre, et associée à divers enjeux d’actualité : économique, environnemental, et sociétal. Quatre principaux acteurs sont concernés par ces enjeux : chargeurs, clients, transporteurs et collectivités, ayant chacun des priorités différentes (amélioration de la qualité de service, minimisation de la distance parcourue, réduction des émissions de gaz à effet de serre, …). Face à ces défis dans la ville, un levier d’action possible consiste à optimiser les tournées effectuées pour la livraison et/ou la collecte des marchandises. Trois types de flux urbains sont considérés : en provenance ou à destination de la ville, et intra-urbains. Pour les flux sortants et entrants dans la ville, les marchandises sont d’abord regroupées dans un entrepôt situé en périphérie urbaine. S’il existe plusieurs entrepôts, le problème de planification associé est de type Location Routing Problem (LRP). Nous en étudions une de ses variantes appelée Capacitated Location Routing Problem (CLRP). Dans cette dernière, en respectant la contrainte de capacité imposée sur les véhicules et les dépôts, la localisation des dépôts et la planification des tournées sont considérées en même temps. L’objectif est de minimiser le coût total qui est constitué du coût d’ouverture des dépôts, du coût d’utilisation des véhicules, et du coût de la distance parcourue. Pour tous les flux, nous cherchons également à résoudre un problème de tournées de type Pickup and Delivery Problem (PDP), dans lequel une flotte de véhicules effectue simultanément des opérations de collecte et de livraison. Nous nous sommes focalisés sur deux de ses variantes : la variante sélective où toutes les demandes ne sont pas toujours satisfaites, dans un contexte de demandes appairées et de sites contraints par des horaires d’ouverture et fermeture (Selective Pickup and Delivery Problem with Time Windows and Paired Demands, ou SPDPTWPD). La seconde variante étudiée est l’extension de la première en ajoutant la possibilité d’effectuer les transports en plusieurs étapes par l’introduction d’opérations d’échanges des marchandises entre véhicules en des sites de transfert (Selective Pickup and Delivery with Transfers ou SPDPT). Les objectifs considérés pour ces deux variantes de PDP sont de maximiser le profit et de minimiser la distance. Chaque problème étudié fait l’objet d’une description formelle, d’une modélisation mathématique sous forme de programme linéaire, puis d’une résolution par des méthodes exactes, heuristiques et/ou métaheuristiques. En particulier nous avons développé des algorithmes basés sur une métaheuristique appelée Particle Swarm Optimization, que nous avons hybridée avec de la recherche locale. Les approches sont validées sur des instances de différentes tailles issues de la littérature et/ou que nous avons générées. Les résultats sont analysés de façon critique pour mettre en évidence les avantages et inconvénients de chaque méthode. / In this thesis, we are interested in the management of goods flows in urban areas, also called last mile logistics, and associated with various current issues: economic, environmental, and societal. Four main stakeholders are involved by these challenges: shippers, customers, carriers and local authorities, each with different priorities (improving service quality, minimizing the travelling distance, reducing greenhouse gas emissions, etc.). Faced with these challenges in the city, one possible action lever is to optimize the routes for the pickup and/or delivery of goods. Three types of urban flows are considered: from or to the city, and intra-urban. For outgoing and incoming flows into the city, the goods are first grouped in a warehouse located on the suburban area of the city. If there are several warehouses, the associated planning problem is the Location Routing Problem (LRP). We are studying one of its variants called the Capacitated Location Routing Problem (CLRP). In this problem, by respecting the capacity constraint on vehicles and depots, the location of depots and route planning are considered at the same time. The objective is to minimize the total cost, which consists of the cost of opening depots, the cost of using vehicles, and the cost of the travelling distance. For all flows, we are also looking to solve a Pickup and Delivery Problem (PDP), in which a fleet of vehicles simultaneously carries out pickup and delivery operations. We focus on two of its variants: the selective variant where not all requests are satisfied, in a context of paired demands and time windows on sites (Selective Pickup and Delivery Problem with Time Windows and Paired Demands, or SPDPTWPD). The second studied variant is the extension of the first one by adding the possibility of carrying out transport in several stages by introducing operations for the exchange of goods between vehicles at transfer sites (Selective Pickup and Delivery with Transfers or SPDPT). The considered objectives for these two variants of PDP are to maximize profit and to minimize distance. Each studied problem is formally described, mathematically modelled as a linear program and then solved by exact, heuristic and/or metaheuristic methods. In particular, we have developed algorithms based on a metaheuristic called Particle Swarm Optimization, which we have hybridized with local search operators. The approaches are validated on instances of different sizes from the literature and/or on instances that we have generated. The results are critically analyzed to highlight the advantages and drawbacks of each method.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique. / The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming.

Les entreprises de transport et de distribution sont confrontées à des difficultés d'exploitation liées à la taille et à la complexité de leur processus de livraison. Dans cette problématique, nous proposons une approche globale du Problème Général de Livraison (PGL).Au niveau méthodologique, c'est une approche hiérarchique (stratégique, tactique, opérationnelle) et structurée. Il s'agit de concevoir et d'exploiter un PGL en le décomposant en problèmes de livraisons élémentaires identifiés et le plus possible indépendants les uns des autres (problèmes de transport, de hubs, d'agences, de tournées...).Au niveau algorithmique, des modèles et algorithmes de résolution ont été proposés pour résoudre ces problèmes élémentaires de livraison dans la phase opérationnelle en tenant compte, en particulier, du nombre et de la capacité limités des moyens de transport.Au niveau applicatif, deux exemples réels sont traités : le système de livraison d'une entreprise de Vente à Distance et le système de livraison des casernes de pompiers du Nord de la France à partir de la pharmacie centrale de Lille

Nous étudions dans cette thèse un problème de construction de tournées de véhicules pour le transport de personnes à la demande (TAD) qui, combinant la souplesse des taxis à la capacité de regroupement des transports en commun, est une voie pour repenser nos pratiques en terme de mobilité. Après avoir défini puis classé plusieurs critères de qualité de service, nous en sélectionnons trois pour leur représentativité : la minimisation de la distance totale parcourue, la maximisation du taux de remplissage des véhicules et la minimisation du temps perdu en transport. La méthode d'optimisation utilisée est basée sur une approche par décomposition appelée génération de colonnes. Nous nous plaçons dans le cas statique où toutes les demandes sont connues par avance. L'adaptation de cette méthode exacte aux trois critères choisis induit des développements originaux, comme la modélisation du réseau par un p-graphe ou l'optimisation d'une fonction objectif fractionnaire. Cette étude est intégrée à un projet pluridisciplinaire piloté par des géographes qui a pour sujet d'expérimentation la mise en place d'un TAD opérationnel dans le Pays du Doubs Central (France). Un algorithme de résolution heuristique spécifique a été développé pour cette application. L'intégration des résultats des deux algorithmes à un Système d'Information Géographique permet une analyse des critères de qualité de service et de leurs interactions avec le territoire d'un point de vue géomatique. Il en découle une étude sur la forme des tournées et plus particulièrement sur différentes mesures de leur sinuosité.