No description available.

É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.

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.

Stochastic combinatorial optimization problems are combinatorial optimization problems where part of the problem data are probabilistic. The focus of this thesis is on stochastic routing problems, a class of stochastic combinatorial optimization problems that arise in distribution management. Stochastic routing problems involve finding the best solution to distribute goods across a logistic network. In the problems we tackle, we consider a setting in which the cost of a solution is described by a random variable; the goal is to find the solution that minimizes the expected cost. Solving such stochastic routing problems is a challenging task because of two main factors. First, the number of possible solutions grows exponentially with the instance size. Second, computing the expected cost of a solution is computationally very expensive. <p><br><p>To tackle stochastic routing problems, stochastic local search algorithms such as iterative improvement algorithms and metaheuristics are quite promising because they offer effective strategies to tackle the combinatorial nature of these problems. However, a crucial factor that determines the success of these algorithms in stochastic settings is the trade-off between the computation time needed to search for high quality solutions in a large search space and the computation time spent in computing the expected cost of solutions obtained during the search. <p><br><p>To compute the expected cost of solutions in stochastic routing problems, two classes of approaches have been proposed in the literature: analytical computation and empirical estimation. The former exactly computes the expected cost using closed-form expressions; the latter estimates the expected cost through Monte Carlo simulation.<p><br><p>Many previously proposed metaheuristics for stochastic routing problems use the analytical computation approach. However, in a large number of practical stochastic routing problems, due to the presence of complex constraints, the use of the analytical computation approach is difficult, time consuming or even impossible. Even for the prototypical stochastic routing problems that we consider in this thesis, the adoption of the analytical computation approach is computationally expensive. Notwithstanding the fact that the empirical estimation approach can address the issues posed by the analytical computation approach, its adoption in metaheuristics to tackle stochastic routing problems has never been thoroughly investigated. <p><br><p>In this thesis, we study two classical stochastic routing problems: the probabilistic traveling salesman problem (PTSP) and the vehicle routing problem with stochastic demands and customers (VRPSDC). The goal of the thesis is to design, implement, and analyze effective metaheuristics that use the empirical estimation approach to tackle these two problems. The main results of this thesis are: <p>1) The empirical estimation approach is a viable alternative to the widely-adopted analytical computation approach for the PTSP and the VRPSDC; <p>2) A principled adoption of the empirical estimation approach in metaheuristics results in high performing algorithms for tackling the PTSP and the VRPSDC. The estimation-based metaheuristics developed in this thesis for these two problems define the new state-of-the-art. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

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.

[pt] Os problemas de roteamento estão entre os problemas combinatórios mais difíceis de encontrar limites melhores do que os existentes ou de provar novas soluções ótimas. Nesta tese, são abordados o Capacitated Arc Routing Problem (CARP) e o Generalized Vehicle Routing Problem (GVRP). Em ambos os problemas, existe um conjunto de clientes os quais estão espalhados por um grafo dado, onde cada cliente possui uma demanda que deve ser atendida por exatamente um veículo de um conjunto de veículos idênticos. Os custos de travessia e o vértice de depósito são dados. O objetivo é encontrar rotas que coletam todas as demandas com custo mínimo, sem exceder a capacidade de nenhum veículo. No CARP, os clientes são um subconjunto de arestas, chamadas de arestas requireds, e para o GVRP, cada cliente é um subconjunto de vértices, chamado de grupo, onde cada grupo deve ser atendido visitando-se exatamente um vértice deste grupo. Além disto, vale notar que quando cada grupo possui apenas um vértice, o problema passa a ser o Capacitated Vehicle Routing Problem (CVRP). Primeiramente, são investigados métodos para melhorar os limites inferiores de instâncias de grande porte. É proposta a exploração da velocidade de uma heurística dual ascent para gerar cortes de capacidade. Em seguida, é apresentado um algoritmo de geração de colunas com um pricing eficiente para um tipo especial de rota não-elementar. O pricing proposto combina a técnica Decremental State-Space Relaxation (DSSR) com limites de complemento. Estas técnicas permitem o fortalecimento da regra de dominância entre as rotas, reduzindo drasticamente o número total de rótulos utilizados pela programação dinâmica. Finalmente, um algoritmo de branch-cut-and-price é criado o qual usa a geração de colunas e a separação de cortes previamente apresentadas. Além disto, este branch-cut-and-price é implementado usando strong branching e fixação por custo reduzido. Ao fim de cada parte, são apresentados resultados computacionais os quais avaliam a qualidade dos algoritmos propostos, os quais obtém novos limites inferiores para um grande número de instâncias do CARP e do GVRP. / [en] Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has a demand which must be serviced by exactly one vehicle from a set of identical vehicles. The traversal costs and a depot vertex are given. The objective is to find routes that collect all the demands, without exceeding the capacity of any vehicle, at minimum cost. For the CARP, the customers are a subset of edges, called the required edges, and for the GVRP, each customer is a subset of vertices, called clusters, where each cluster must be serviced by visiting exactly one vertex of it. Furthermore, it is noteworthy that when every cluster contains just a single vertex, the problem is the Capacitated Vehicle Routing Problem (CVRP). Firstly, we investigate methods to improve lower bounds for large scale instances. We propose to explore the speed of a new dual ascent heuristic to generate capacity cuts. The quality of the cuts found is next improved with a new exact separation which is used in the linear program resolution that follows the dual heuristic. Following, we present a column generation algorithm with an efficient pricing for a special kind of non-elementary routes. The proposed pricing algorithm combines Decremental State-Space Relaxation(DSSR) technique with completion bounds. These techniques allow the strengthening of the domination rule between routes, drastically reducing the total number of labels used during the dynamic programming. Finally, we devise a branch-cut-and-price algorithm which uses the previously presented column generation and cut separation. Moreover, this branch-cutand- price is implemented using strong branching and reduced cost fixing. At the end of each part, we present computational experiments which evaluate the quality of the proposed algorithms and show new best lower bounds for a large number of CARP and GVRP instances.

No description available.