In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construction and route improvement phases. Computational experiments are conducted with Solomon (1987)&rsquo / s and Homberger and Gehring (1999)&rsquo / s problem sets in order to test the performance of the proposed algorithm. From the computational results encouraging results are obtained in terms of solution quality.

This thesis identifies some problems, the genetic algorithm (GA) is facing in the area of vehicle routing and proposes various methods to address those problems. Those problems arise from the unavailability of suitable chromosomal representation and evaluation schemes of GA for the Vehicle Routing Problem (VRP). The representation and evaluation schemes already in use have problems of high computational cost, illegal chromosomes (chromosomes not representing a legal tour) and wrong fitness assignment (fitness not truly representing chromosome genetic makeup). These problems are addressed by several proposed new schemes, namely the Self Imposed Constraints Evaluation scheme, the Contour and Reverse Contour Evaluation schemes and the Order Skipping Evaluation scheme, which are specifically tailored for various objectives, problems and situations. Apart from this, a methodology, which has previously being used in other meta-heuristics, is incorporated into GA i.e., the independent application of GA on various sub-localities of the problem. We call this GA, a Localized Genetic Algorithm (LGA). LGA is an iterative procedure between optimization and controlled de-optimization. The procedure of controlled de-optimization is also novel. It brings the solution into a new search space while controlling its cost effectively. LGA is introduced with various search techniques, i.e. intensive, extensive and selective, the use of which depends on the problem size and the availability of computational resources. Furthermore, search reduction techniques (Fitness Approximation Methods) are also introduced into the LGA, which has enabled the LGA to be applied to large scale problems. Due to the implementation of those proposals, LGA is the first GA-driven approach to be applied to very large scale CVRP problems of up to 1200 customers, i.e. datasets presented by Feiyue in 2005 and large scale VRPTW problems of up to 1000 customers, datasets presented by Gehring and Homberger in 1999. Lastly, a standard unit for computational comparison, i.e., Bellman's Evaluation Units BEUs, is also introduced to facilitate computational comparisons for future researchers. LGA has shown promising results on CVRP and VRPTW problems. It is flexible and also has the potential to be extended to not only other vehicle routing problems, but also to other ordering problems.

Les problèmes de tournées de véhicules sont des problèmes d’optimisation combinatoire épineux avec des enjeux économiques et environnementaux importants au sein de la chaîne logistique. Le problème fondamental est de desservir des clients avec un ensemble de véhicules de façon à minimiser la distance totale parcourue. En pratique, il y a une grande variété d’objectifs et de contraintes additionnelles, liées à la législation et à la diversité des domaines d’applications. Ces problèmes de tournées sont très fréquents pour de nombreuses industries et la conception d’approches de résolution génériques est devenue une question de recherche importante.Cette thèse porte sur la conception et le développement d’un nouveau moteur de résolution pour les logiciels de tournées de véhicules proposés par l’entreprise GEOCONCEPT. Le solveur mis au point s’appuie sur la programmation par contraintes (PPC) pour améliorer la flexibilité (prise en compte de contraintes additionnelles), la déclarativité et la maintenance qui sont les limites des solveurs actuels de GEOCONCEPT fondés sur la recherche locale.Dans un premier temps, un modèle de graphe est établi pour la représentation unifiée des données et de nombreuses contraintes métiers. La résolution s’effectue par des approches à base de voisinage large disponibles dans les solveurs de PPC modernes. On peut ainsi traiter des instances de très grandes tailles efficacement tout en conservant une approche déclarative pour exprimer une classe très large de problèmes de tournées de véhicules. Dans un second temps, des modèles PPC s’appuyant sur des représentations redondantes du problème sont proposés afin de renforcer le filtrage. Nous nous intéressons en détails aux mécanismes de filtrage c’est-à-dire aux processus d’élimination des valeurs infaisables ou sous-optimales dans les domaines des variables. Ces algorithmes permettent de simplifier rapidement le problème et de fournir des bornes inférieures afin d’évaluer la qualité des solutions obtenues. Les bornes inférieures sont obtenues en résolvant des relaxations du plus célèbre des problèmes de la Recherche Opérationnelle : le problème du voyageur de commerce (TSP). Ce problème est le cœur de la contrainte globale weightedcircuit permettant de modéliser les problèmes de tournées en PPC. Nous proposons de nouveaux mécanismes de filtrage pour cette contrainte s’appuyant sur trois relaxations du TSP. Ces relaxations sont comparées sur les plans théorique et expérimental. L’originalité de ce travail est de proposer un nouvel algorithme de filtrage permettant de raisonner à la fois sur les successeurs directs d’un client et sur sa position dans la tournée. Ces raisonnements sont particulièrement utiles en présence de contraintes de fenêtres de temps, très communes dans les problèmes industriels.Le nouveau moteur de résolution offre d’excellentes performances sur des problèmes académiques et industriels tout en proposant des bornes inférieures informatives à des problèmes industriels réels. / Vehicle routing problems are very hard combinatorial optimization problems with significant economic and environmental challenges. The fundamental problem is to visit a set of customers with a given fleet of vehicles in order to minimize the total distance travelled. Moreover, these problems arise with a wide variety of objectives and additional constraints, related to the legislation and the diversity of industrial sectors. They are very common for many industries and the design of generic solvers has become an important research issue.This thesis focuses on the design and implementation of a new solver for the vehicle routing services offered by the company GEOCONCEPT. The proposed solver is based on constraint programming (CP) to improve flexibility (ability to take additional constraints into account), declarative modelling and maintenance, which are the limits of current GEOCONCEPT solvers based on local search.Firstly, a graph model is established to provide a common representation of the input-data and the numerous business constraints. The resolution is performed using large neighbourhood search methods available in modern CP solvers. It is thus possible to deal with large instances efficiently with a declarative approach where a broad class of vehicle routing problems can be modelled. Secondly, several CP models based on redundant views of the problem are proposed to strengthen the filtering. We focus on the filtering mechanisms for removing infeasible or suboptimal values in the domains of the variables. These algorithms can quickly simplify the problem and derive lower bounds to assert the quality of the solutions found. The lower bounds are obtained by solving relaxations of the most famous problem in Operations Research: the Traveling Salesman Problem (TSP). This problem is the core of the global constraint WEIGTEHDCIRCUIT for modelling routing problems in CP. We propose new filtering algorithms for this constraint based on three relaxations of the TSP. These relaxations are compared theoretically and experimentally. The originality of this work is to propose a new filtering algorithm for reasoning on the direct successors of a customer as well as his position in the tour. It is particularly useful in the presence of time window constraints, which are very common in industrial problems.The new solver shows excellent performance on academic and industrial problems and can compute informative lower bounds for real-life problems.

Control of complex systems satisfying rich temporal specification has become an increasingly important research area in fields such as robotics, control, automotive, and manufacturing. Popular specification languages include temporal logics, such as Linear Temporal Logic (LTL) and Computational Tree Logic (CTL), which extend propositional logic to capture the temporal sequencing of system properties. The focus of this dissertation is on the control of high-dimensional systems and on timed specifications that impose explicit time bounds on the satisfaction of tasks. This work proposes and evaluates methods and algorithms for synthesizing provably correct control policies that deal with the scalability problems. Ideas and tools from formal verification, graph theory, and incremental computing are used to synthesize satisfying control strategies. Finite abstractions of the systems are generated, and then composed with automata encoding the specifications. The first part of this dissertation introduces a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The specification has two parts: (1) a global specification given as an LTL formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula, and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The second part of the dissertation focuses on stochastic systems with temporal and uncertainty constraints. A specification language called Gaussian Distribution Temporal Logic is introduced as an extension of Boolean logic that incorporates temporal evolution and noise mitigation directly into the task specifications. A sampling-based algorithm to synthesize control policies is presented that generates a transition system in the belief space and uses local feedback controllers to break the curse of history associated with belief space planning. Switching control policies are then computed using a product Markov Decision Process between the transition system and the Rabin automaton encoding the specification.The approach is evaluated in experiments using a camera network and ground robot. The third part of this dissertation focuses on control of multi-vehicle systems with timed specifications and charging constraints. A rich expressivity language called Time Window Temporal Logic (TWTL) that describes time bounded specifications is introduced. The temporal relaxation of TWTL formulae with respect to the deadlines of tasks is also discussed. The key ingredient of the solution is an algorithm to translate a TWTL formula to an annotated finite state automaton that encodes all possible temporal relaxations of the given formula. The annotated automata are composed with transition systems encoding the motion of all vehicles, and with charging models to produce control strategies for all vehicles such that the overall system satisfies the mission specification. The methods are evaluated in simulation and experimental trials with quadrotors and charging stations.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

[pt] Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of several problems related to this area seggests integer programming as a natural approach to solve them. Nevertheless, there are many cases in which instances of reasonable size are still beyond the resolution capability of the algotithms presented in the literature. The sucess of the known algotithms have therefore been limited partly to the fact that most of them have not incorporated any recent relevant advances in the combinatorial optimization field. Some of these new techniques and their applications are the main subject of this dissertation. Firstly, basic decomposition techniques for linear and integer programming problems, as well as the relates column generation approach are addressed. This is followed by the presentation of a reformulation technique for linear and integer programming, which is alternative to the well known Dantzig-Wolfe master program. The new possibilities arousing from this approach are explored and the resulting consequences to the standard branch-and-bound algotithm and its variations branch-and- cut, branch-and-prince and branch-and-cut-and-price are presented. Later, routing problems where this methodology was applied were addressed with the capacitated vehicle routing problems - CVRP and followed by vehicle routing problems with time windows and heterogeneous fleet. For each problem, it is described how the techniques mentioned above were reported. Finally, in the last time windows and heterogeneous fleet, which is the case of a newspaper distribution in a major communication company in Rio de Janeiro.

O presente trabalho aborda o sistema logístico usualmente denominado Vendor Managed Inventory (VMI), no qual o fornecedor controla e coordena as decisões de reabastecimento, sendo responsável por manter os estoques de seus clientes dentro de limites fixados de antemão. O modelo proposto incorpora ainda as decisões relativas à produção e manutenção de estoque por parte do fornecedor, além da utilização de frota heterogênea na distribuição, e busca a minimização dos custos totais do sistema. Quatro heurísticas de duas etapas são propostas para a resolução do problema abordado. A primeira etapa, comum a todas as heurísticas, baseia-se em uma heurística recentemente publicada na literatura e fornece uma solução inicial viável, utilizada como ponto de partida para a etapa de melhoria subsequente, na qual é utilizada a metaheurística busca tabu ou busca em vizinhança variável. As heurísticas propostas foram avaliadas em um conjunto de teste, sendo obtidos resultados melhores que os reportados na literatura em todas as instâncias testadas. Dentre as estratégias de solução avaliadas, destaca-se a heurística baseada em busca tabu com diversificação, que demonstrou ser superior às demais heurísticas propostas. Os resultados obtidos indicam ainda que, no caso da frota disponível ser heterogênea, é vantajosa a utilização de uma adaptação do procedimento de obtenção da solução inicial, como forma de privilegiar a utilização de veículos de maior eficiência. / This thesis deals with the logistic system usually called Vendor Managed Inventory (VMI). In this system the supplier controls and coordinates the supply decisions and is responsible for keeping the inventory of each of his clients within predetermined minimum and maximum levels. Heterogeneous fleet and production/stocking decisions at the supplier are considered as well, and the proposed model seeks to minimize the total system cost. Four two-stage heuristics are proposed for this problem. The first stage consists in an adaptation of a heuristic found in the bibliography, which provides an initial viable solution that will be improved in the second stage by means of the metaheuristics tabu search or variable neighborhood search. The proposed heuristics were tested on a set of benchmark instances with improvements found on the best known results in all of the tested instances. The obtained results indicate that the tabu search based heuristic with diversification strategy is clearly superior to the other proposed heuristics and that a better fleet utilization can be obtained in the case of heterogeneous fleet by a simple improvement in the first stage, that favors the selection of more efficient vehicles.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.