This dissertation focuses on supply chain design and logistics problems with emphasis on biomass logistics and routing problems. In biomass logistics, we have studied problems arising in a switchgrass-based bio-ethanol supply chain encountered in the Southeast, and a corn stover harvest scheduling problem faced in the Midwest Unites States, both pertaining to the production of cellulosic ethanol. The main contributions of our work have been in introducing new problems to the literature that lie at the interface of the lot-sizing and routing problems, and in developing effective exact algorithms for their solution. In the routing area, we have addressed extensions of the well-known traveling salesman and vehicle routing problems. We have proposed new formulations and have developed exact algorithms for the single and multiple asymmetric traveling salesmen problems (ATSP and mATP), the high-multiplicity asymmetric traveling salesman problem (HMATSP) and its extensions, and the fixed-destination multi-depot traveling salesman problem with load balancing (FD-MTSPB). Furthermore, we have introduced a new strategy to reduce routing cost in the classical vehicle routing problem (VRP). / Ph. D.

Le but de ce travail de thèse réside dans la planification de la distribution urbaine des marchandises dans un système de transport collaboratif. Cette collaboration consiste à échanger les demandes de transport entre transporteurs afin d'améliorer l'efficacité de leurs opérations. Cela revient à minimiser la distance parcourue par les camions et à maximiser le profit collecté des clients, notamment en recourant à des variantes du problème de tournées de véhicules plus adaptées au contexte collaboratif. Le problème opérationnel sous-jacent est donc le problème de tournées de véhicules sélectives dans lequel le service de tous les clients n'est pas obligatoire par contre un "profit" est collecté lors du service d'un client. Dans cette thèse, nous traitons le problème de tournées de véhicules sélectives avec contraintes de temps et de capacité (Capacitated Team Orienteering Problem - CTOP). Nous proposons une métaheuristique qui alterne entre deux espaces de recherche. Des procédures de découpage optimal et de concaténation permettent de passer d'un espace à un autre. D'autre part, en considérant des demandes de collecte et de livraison, nous traitons deux variantes sélectives du problème de collecte et de livraison (Pickup and Delivery Problem - PDP) : le PDP avec fenêtres de temps et demandes obligatoires (PDPTWPR) et le PDPTWPR avec demandes groupées. La première variante consiste à choisir parmi les demandes de transport optionnelles quelles demandes à servir en plus des demandes obligatoires. Nous développons des métaheuristiques pour traiter les cas mono-objectif et multi-objectif du problème. Le PDPTWPR avec demandes groupées prend en considération les demandes de transport qui doivent être servies par un même transporteur. Finalement, nous considérons la variante sélective dans laquelle les marchandises sont distribuées d'un même dépôt vers les clients (Capacitated Profitable Tour Problem - CPTP). L'objectif est de maximiser la différence entre le coût et le profit. Pour résoudre ce problème, nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers à laquelle nous ajoutons plusieurs inégalités valides spécifiques à ce problème. Des expérimentations ont été conduites sur plusieurs classes d'instances afin de montrer l'efficacité de nos approches. / The goal of this thesis is to plan urban freight distribution in a collaborative logistic system. The collaboration consists in exchanging transportation requests between carriers to increase the efficiency of their operations. More precisely, when solving variants of the wellknown vehicle's routing problems in collaborative context, less kilometers can be driven and higher prices can be collected. The underlying operational problem is therefore the selective vehicle routing problem in which not all customers can be served, but a "profit" is gained for each served one. In this thesis, we firstly address the Capacitated Team Orienteering Problem (CTOP), a selective variant of the VRP in which capacity and travel time limitations are imposed to vehicles. We propose a variable space search metaheuristic that alternates between two different search spaces to solve CTOP. Then, we consider pickup and delivery requests to study two variants of the selective pickup and delivery problem: the PDP with Time Windows and Reserved requests (PDPTWPR) and the Clustered PDPTWPR. The first aims to choose suitable selective requests to be transported in addition to reserved ones. Metaheuristics are proposed to deal with the single-objective and the multi-objective sides of the problem. The second takes into consideration groups of requests that must be served by only one carrier. Finally, we consider the Capacitated Profitable Tour Problem (CPTP) in which goods need to be distributed from the depot to customers. We propose an exact method based on Integer Linear Programming to solve this problem. A set of cuts specific to CPTP is proposed in order to speed up the solution process. Experiments were conducted on a variety of instances of different sizes to demonstrate the effectiveness of our solution methods.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Nous nous intéressons dans cette thèse à la résolution du problème de tournées sélectives (Team Orienteering Problem - TOP) et ses variantes. Ce problème est une extension du problème de tournées de véhicules en imposan tcertaines limitations de ressources. Nous proposons un algorithme de résolution exacte basé sur la programmation linéaire en nombres entiers (PLNE) en ajoutant plusieurs inégalités valides capables d’accélérer la résolution. D’autre part, en considérant des périodes de travail strictes pour chaque véhicule durant sa tournée, nous traitons une des variantes du TOP qui est le problème de tournées sélectives multipériodique (multiperiod TOP - mTOP) pour lequel nous développons une métaheuristique basée sur l’optimisation par essaim pour le résoudre. Un découpage optimal est proposé pour extraire la solution optimale de chaque particule en considérant les tournées saturées et pseudo saturées .Finalement, afin de prendre en considération la disponibilité des clients, une fenêtre de temps est associée à chacun d’entre eux, durant laquelle ils doivent être servis. La variante qui en résulte est le problème de tournées sélectives avec fenêtres de temps (TOP with Time Windows - TOPTW). Deux algorithmes exacts sont proposés pour résoudre ce problème. Le premier est basé sur la génération de colonnes et le deuxième sur la PLNE à laquelle nous ajoutons plusieurs coupes spécifiques à ce problème. / We focus in this thesis on developing new algorithms to solve the Team Orienteering Problem (TOP) and two of its variants. This problem derives from the well-known vehicle routing problem by imposing some resource limitations .We propose an exact method based on Mixed Integer Linear Programming (MILP) to solve this problem by adding valid inequalities to speed up its solution process. Then, by considering strict working periods for each vehicle during its route, we treat one of the variants of TOP, which is the multi-period TOP (mTOP) for which we develop a metaheuristic based on the particle swarm optimization approach to solve it. An optimal split procedure is proposed to extract the optimal solution from each particle by considering saturated and pseudo-saturated routes. Finally, in order to take into consideration the availability of customers, a time window is associated with each of them, during which they must be served. The resulting variant is the TOP with Time Windows (TOPTW). Two exact algorithms are proposed to solve this problem. The first algorithm is based on column generation approach and the second one on the MILP to which we add additional cuts specific for this problem. The comparison between our exact and heuristic methods with the existing one in the literature shows the effectiveness of our approaches.

No description available.

Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes de tournées de véhicules. Nous avons exploité des travaux menés sur les graphes d'intervalles et des propriétés de dominance relatives aux tournées saturées pour traiter les problèmes de tournées sélectives plus efficacement. Des approches basées sur un algorithme d'optimisation par essaim particulaire et un algorithme mémétique ont été proposées. Les métaheuristiques développées font appel à un ensemble de techniques particulièrement efficaces telles que le découpage optimal, les opérateurs de croisement génétiques ainsi que des méthodes de recherches locales. Nous nous sommes intéressés également aux problèmes de tournées classiques avec fenêtres de temps. Différents prétraitements ont été introduits pour obtenir des bornes inférieures sur le nombre de véhicules. Ces prétraitements s'inspirent de méthodes issues de modèles de graphes, de problème d'ordonnancement et de problèmes de bin packing avec conflits. Nous avons montré également l'utilité des méthodes développées dans un contexte industriel à travers la réalisation d'un portail de services mobilité. / In this thesis, we focused on the development of heuristic approaches for solvingvehicle routing problems. We exploited researches conducted on interval graphsand dominance properties of saturated tours to deal more efficiently with selectivevehicle routing problems. An adaptation of a particle swarm optimization algorithmand a memetic algorithm is proposed. The metaheuristics that we developed arebased on effective techniques such as optimal split, genetic crossover operatorsand local searches. We are also interested in classical vehicle problems with timewindows. Various pre-processing methods are introduced to obtain lower boundson the number of vehicles. These methods are based on many approaches usinggraph models, scheduling problems and bin packing problems with conflicts. Wealso showed the effectiveness of the developed methods with an industrial applicationby implementing a portal of mobility services.

This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle. This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing. / Master of Science

Étant donné leur faible impact environnemental, l’utilisation des véhicules électriques dans les activités de service a beaucoup augmenté depuis quelques années. Cependant, leur déploiement est freiné par des contraintes techniques telles qu’une autonomie limitée et de longs temps de charge des batteries. La prise en compte de ces contraintes a mené à l’apparition de nouveaux problèmes de tournées de véhicules pour lesquels, en plus d’organiser les tournées,il faut décider où et de combien charger les batteries. Dans cette thèse nous nous intéressons à ces problèmes au travers de quatre études. La première concerne le développement d’une métaheuristique en deux phases simple mais performante pour résoudre un problème particulier appelé "Green VRP”. Dans la seconde, nous nous concentrons sur la modélisation d’un aspect essentiel dans ces problèmes : le processus de chargement des batteries. Nous étudions différentes stratégies pour modéliser ce processus et montrons l’importance de considérer la nature non linéaire des fonctions de chargement. Dans la troisième étude nous proposons une recherche locale itérative pour résoudre des problèmes avec des fonctions de chargement non linéaires. Nous introduisons un voisinage dédié aux décisions de chargement basé sur un nouveau problème de chargement sur une tournée fixée. Dans la dernière étude, nous traitons un problème réel de tournées de techniciens avec des véhicules classiques et électriques. Ce problème est résolu par une métaheuristique qui décompose le problème en plusieurs sous-problèmes plus simples résolus en parallèle, puis qui assemble des parties des solutions trouvées pour construire la solution finale. / Electric vehicles (evs) are one of the most promising technologies to reduce the greenhouse gas emissions. For this reason, the use of evs in service operations has dramatically increased in recent years. Despite their environmental benefits, evs still face technical constraints such as short autonomy and long charging times. Taking into account these constraints when planning ev operations leads to a new breed of vehicle routing problems (vrps), known as electricVrps (evrps). In addition, to the standard routing decisions, evrps are concerned with charging decisions: where and how much to charge. In this ph. D thesis, we address evrps through 4 different studies. In the first study, we tackle the green vehicle routing problem. To solve the problem, we propose a simple, yet effective, two-phase matheuristic. In the second study, we focus a key modelling aspects in evrps: the battery charging process. We study different strategies to model this process and show the importance of considering the nonlinear nature of the battery charging functions. InThe third study, we propose an iterated local search to tackle evrp with non-linear charging functions. We introduce a particular local search operator for the charging decisions based on a new fixedroute charging problem. The fourth and last study considers a real technician routing problem with conventional and electric vehicles (trp-cev). To tackle this problem, we propose a parallel matheuristic that decomposes the problem into a set of easier-to-solve subproblemsThat are solved in parallel processors. Then the approach uses parts of the solutions found to the subproblems to assemble final solution to the trp-cev.