Distributed Approximation / The classic vehicle routing problem (VRP) is generally concerned with the optimal design of routes by a fleet of vehicles to service a set of customers by minimizing the overall cost, usually the travel distance for the whole set of routes. Although the problem has been extensively studied in the context of operations research and optimization, there is little research on solving the VRP, where distributed vehicles need to compute their respective routes in a decentralized fashion. Our first contribution is a synchronous distributed approximation algorithm that solves the VRP. Using the duality theorem of linear programming, we show that the approximation ratio of our algorithm is $O(n . (\rho)^{1/n} .log(n+m))$, where $\rho$ is the maximum cost of travel or service in the input VRP instance, $n$ is the size of the graph, and $m$ is the number of vehicles. We report results of simulations comparing our algorithm results with ILP solutions and a greedy algorithm. / Thesis / Master of Science (MSc) / The Open Multi-Depot Vehicle Routing Problem(OMDVRP) problem is solved using an synchronous distributed algorithm and the approximation ratio is found and simulation results comparing the performance of ILP , greedy and the designed algorithm is done.

Optimalizace rozvozu tiskovin na konkrétním případě z praxe. Úloha řešena rozdělením na deset samostatných úloh. Využití heuristik, které byly upraveny přímo daným požadavkům. Ve třech úlohách nebylo nalezeno optimum

Le VRP permet de modéliser la problématique du TMV. Pour autant dans sa version la plus simpliste il ne peut convenir aux nouvelles contraintes qui renforcent la complexité de l’environnement urbain tel que la congestion. Raison pour laquelle ce travail se positionne en premier sur un TDVRP (Time-Dependent-Vehicle-Routing-Problem) dans le but de représenter au mieux le contexte urbain actuel. La résolution de ces deux problèmes est efficace, entraînant une réduction du nombre de véhicules supplémentaires nécessaires en raison des retards de congestion peuvent être éliminés. Mais cette solution n’est pas sans conséquence pour les clients finaux puisque son but est d’éviter le passage aux heures de pointes et cela peut engendrer des retards de livraison. Pour cette raison nous voulons proposer une nouvelle solution qui permet de résoudre le problème du chemin le plus court et en intégrant la dépendance au temps (TDVRP). Cette solution se repose sur une meilleure exploitation des véhicules, en premier lieu, pour réduire le nombre de véhicule sur la route. Ce problème s’appelle MT-VRP (Multi-Trip VRP) qui a été évoqué en 2007 par (Azi, et al. 2007). Dans un deuxième temps nous voulons proposer un MT VRP qui utilise différents types de véhicule en termes de capacité de chargement. Dans cette optique vient notre travail qui propose une nouvelle solution de MTTDVRP (TW avec fenêtres de temps) en testant une nouvelle solution en utilisant un véhicule léger de faible capacité de chargement (type tricycle) dans un but de réduire les nuisances liés au TMV. / The VRP makes it possible to model the problem of TMV. However, in its most simplistic version it cannot be adapted to the new constraints which reinforce the complexity of the urban environment such as congestion. This is why this work is placed first on a TDVRP (Time-dependent-Vehicle-Routing-Problem) in order to best represent the current urban context. The resolution of these two problems is effective; resulting in a reduction in the number of additional vehicles needed due to congestion delays can be eliminated. But this solution is not without consequences for end customers since its goal is to avoid the switch to peak hours and this can lead to delivery delays. For this reason we want to propose a new solution that solves the problem of the shortest path and integrating time dependency (TDVRP). This solution relies on better operation of vehicles, in the first place, to reduce the number of vehicles on the road. This problem is called MT-VRP (Multi-Trip VRP) which was raised in 2007 by (Azi, et al. 2007). In a second step we want to propose a MT VRP that uses different types of vehicle in terms of loading capacity. In this perspective comes our work that proposes a new solution of MTTDVRP (TW with time windows) by testing a new solution using a light vehicle of low load capacity (tricycle type) in order to reduce the nuisance associated with TMV.

This paper deals with optimal distribution issues. One may find listed problems of real life linked to distribution. Moreover, there are explained travelling salesman problem, vehicle routing problem and its variants. This work brings an overview of different ways how to solve vehicle routing problem. In practical part, there is an analysis of distribution of real company. The concept of application is presented in the second part of this paper. This concept could reduce costs of distribution in analyzed company. Testing is aimed mainly on the variant VRPCL (Vehicle Routing Problem with Continuos Loading).

Western Canada is in a post Canadian Wheat Board single-desk market, in which grain handlers face policy, allocation, and logistical changes to the transportation of grains. This research looks at the rails transportation problem for allocating wheat from Prairie to port position, offering a new allocation system that fits the evolving environment of Western Canada’s grain market. Optimization and analysis of the transport of wheat by railroads is performed using geographic information system software as well as spatial and historical data. The studied transportation problem searches to minimize the costs of time rather than look purely at locational costs or closest proximity to port. Through optimization three major bottlenecks are found to constrain the transportation problem; 1) an allocation preference towards Thunder Bay and Vancouver ports, 2) small capacity train inefficiency, and 3) a mismatched distribution of supply and demand between the Class 1 railway firms. Through analysis of counterfactual policies and a scaled sensitivity analysis of the transportation problem, the grains transport system of railroads is found to be dynamic and time efficient; specifically when utilizing larger train capacities, offering open access to rail, and under times of increased availability of supplies. Even under the current circumstances of reduced grain movement and inefficiencies, there are policies and logistics that can be implemented to offer grain handlers in Western Canada with the transportation needed to fulfill their export demands.

The Gram-negative pathogen Vibrio cholerae uses variety of regulatory molecules to modulate expression of virulence factors. One important regulatory element of microorganisms is small non-coding RNAs (sRNAs), which control various cell functions such as expression of cell membrane proteins, mRNA decay and riboswitches. In this thesis studies, we demonstrated the roles of the sRNAs VrrA in regulation of outer membrane protein expression, biofilm formation and expression of ribosome binding proteins. In addition, we showed that VrrB, a newly discovered sRNA, played a role in amino acid dependent starvation survival of V. cholerae and might functioned as a riboswitch. VrrA, a 140-nt sRNAs in V. cholerae, was controlled by the alternative sigma factor σE. The outer membrane protein, OmpT is known to be regulated by environmental signals such as pH and temperature via the ToxR regulon and carbon source signals via the cAMP–CRP complex. Our studies provide new insight into the regulation of OmpT by signals received via the σE regulon through VrrA. We demonstrated that VrrA down-regulate ompT translation by base-pairing with the 5′ region of the ompT mRNA in a Hfq (RNA chaperone protein) dependent manner. V. cholerae biofilms contain three matrix proteins—RbmA, RbmC and Bap1—and exopolysaccharide. While much is known about exopolysaccharide regulation, little is known about the mechanisms by which the matrix protein components of biofilms are regulated. In our studies, we demonstrated that VrrA negatively regulated rbmC translation by pairing to the 5' untranslated region of the rbmC transcript and that this regulation was not stringently dependent on Hfq. In V. cholerae, VC0706 (Vrp) and VC2530 proteins are homologous to ribosome-associated inhibitor A (RaiA) and hibernation promoting factor (HPF) of Escherichia coli, respectively. HPF facilitates stationary phase survival through ribosome hibernation. We showed that VrrA repressed Vrp protein expression by base-pairing to the 5´ region of vrp mRNA and that this regulation required Hfq. We also showed that Vrp was highly expressed during stationary phase growth and associated with the ribosomes of V. cholerae. We further demonstrated that Vrp and VC2530 were important for V. cholerae starvation survival under nutrient-deficient conditions. While VC2530 was down-regulated in bacterial cells lacking vrrA, mutation of vrp resulted in increased expression of VC2530. Riboswitches are an important class of regulators in bacteria, which are most often located in the 5' untranslated region (5´ UTR) of bacterial mRNA. In this study, we discovered the novel non-coding sRNA, VrrB located at the 5´ UTR of a downstream gene encoding Vibrio auxotropic factor A (VafA) for phenylalanine. In V. cholerae, reduced production of VafA was observed in the presence of phenylalanine and phenylpyruvate in the culture media. Some analogs of phenylalanine and phenylpyruvate could also modulate the expression of VafA. Furthermore, bacterial cells lacking the vrrB gene exhibited high production of VafA, suggesting that VrrB might function as a riboswitch that controls VafA expression.

Hoy en día, de los costos de logística de las empresas, más de la mitad corresponden a costos de transporte, siendo uno de los problemas importantes a resolver el del ruteo de vehículos (VRP), que consiste en determinar las mejores rutas para entregar – desde una bodega - productos o servicios a los clientes quienes están dispersos geográficamente. Existen muchos programas comerciales que lo resuelven, pero son de un alto precio, sobre todo para las pymes. Es así que se hace necesario entregar una solución de bajo costo, por ejemplo a través del reuso de componentes de software. Uno de los enfoques más usados son los frameworks, que son una arquitectura de software incompleta que el desarrollador adapta a las necesidades del problema específico. En este trabajo se desarrolló un framework orientado a objetos para el problema de ruteo de vehículos, a partir de diversos esquemas UML que se implementaron. El mecanismo de desarrollo fue similar al de un software sólo que siempre había que tener en mente que se debía abstraer a un problema VRP lo más genérico posible. En específico se desarrolló un completo diagrama de clases del problema, que comprende los métodos de resolución del problema. En esta tesis se estudiaron en específico las heurísticas que son el enfoque más difundido. También se desarrolló un mecanismo de mapeo entre métodos de solución y problemas, que permite asociar un problema específico con una heurística específica que lo resuelve. Para comprobar el funcionamiento del framework se desarrolló un software que lo instanciara. Con este software se realizaron algunas pruebas con problemas aleatorios e instancias conocidas del VRP, obteniendo buenos resultados. Finalmente se hizo un análisis costo-beneficio que mostró que el reuso de software es una alternativa viable económicamente, en comparación con desarrollar múltiples programas. Como trabajo futuro queda comprobar que otros desarrolladores puedan usar el framework de manera fácil, y para el dominio que aquí se definió. Por otro lado sería interesante desarrollar frameworks para otros problemas de gestión de operaciones como: asignación de tripulación o ubicación de instalaciones.

The purpose of this thesis is to investigate how tractor swapping can be implemented in Vehicle Routing Problems (VRP) with electric heavy goods vehicles, and to evaluate how a model that allows for tractor swapping performs, in terms of schedule cost, against a model that does not. Hence, this thesis introduces a new rich VRP variant which includes tractor swapping, as well as time windows, pickup and delivery, and electric vehicles. The model is named Electric Tractor Swap Vehicle Routing Problem (E-TSVRP) and is formulated as a mixed integer linear program. As for the solver, Gurobi is used. The results show that utilizing tractor swapping can reduce the total cost of serving customers significantly by reducing en-route charging and utilizing drivers more efficiently. Specifically, it is shown that the cost reduction comes mainly from reducing driver work time. By demonstrating how tractor swapping works and how the results can be visualized on smaller cases, this thesis aims to serve as a foundation for future research within the field. To be able to fully implement the model for large logistics problem instances however, alternative solution methods such as heuristics or metaheuristics should be developed so that the problems can be solved in a reasonable amount of time. / Syftet med denna uppsats är att undersöka hur traktorbyten kan implementeras i "Vehicle Routing Problem" (VRP) med tunga, elektriska lastfordon, och att utvärdera hur en modell som tillåter traktorbyten presterar mot en modell som inte tillåter det, med avseende på den totala schemakostnaden. I uppsatsen introduceras därför en ny och generell VRP som har stöd för traktorbyten, men som också modellerar energikonsumtion och laddning av elektriska lastbilar, samt tillåter tidsfönster för när leveranser kan levereras och hämtas upp på godtyckliga platser. Modellen kallas för "Electric Tractor Swap Vehicle Routing Problem" (E-TSVRP) och formuleras som ett linjärt, blandat heltalsprogram. Programmet löses sedan med lösaren Gurobi. Resultaten visar att utnyttjandet av traktorbyten kan märkbart minska den totala kostnaden av att leverera varor till kunder genom att minska tiden som föraren väntar på att traktorn laddar. Mer specifikt tillåts möjligheten att byta till en ny traktor när den tidigare får slut på energi, vilket möjliggör en högre utnyttjandegrad av förarna, och den fakturerade tiden associerad till förarna kan minskas. Detta sker genom en avvägning mellan å ena sidan högre hårdvarukostnader för fler traktorer och å andra sidan lägre förarkostnader. Genom att demonstrera hur traktorbyten fungerar och hur resultaten kan visualiseras på mindre transportproblem, strävar denna uppsats efter att verka som en grund för framtida forskning. För att modellen ska kunna användas för stora logistikproblem bör dock alternativa lösningsmetoder som till exempel lösningsheuristiker eller metaheuristiker utvecklas så att problemen kan lösas inom en rimlig tid.

Cette thèse, présente des contributions à la résolution (sur les GPUs) de problèmes d'optimisations réels de grandes tailles. Les problèmes de tournées de véhicules (VRP) et ceux de localisation des hubs (HLP) sont traités. Diverses approches et leur implémentions sur GPU pour résoudre des variantes du VRP sont présentées. Un algorithme génétique (GA) parallèle sur GPU est proposé pour résoudre différentes variantes du HLP. Le GA adapte son codage, sa solution initiale, ses opérateurs génétiques et son implémentation à chacune des variantes traitées. Enfin, nous avons utilisé le GA pour résoudre le HLP avec des incertitudes sur les données.Les tests numériques montrent que les approches proposées exploitent efficacement la puissance de calcul du GPU et ont permis de résoudre de larges instances jusqu'à 6000 nœuds. / This thesis presents contributions to the resolution (on GPUs) of real optimization problems of large sizes. The vehicle routing problems (VRP) and the hub location problems (HLP) are treated. Various approaches implemented on GPU to solve variants of the VRP. A parallel genetic algorithm (GA) on GPU is proposed to solve different variants of the HLP. The proposed GA adapts its encoding, initial solution, genetic operators and its implementation to each of the variants treated. Finally, we used the GA to solve the HLP with uncertainties on the data.The numerical tests show that the proposed approaches effectively exploit the computing power of the GPU and have made it possible to resolve large instances up to 6000 nodes.

La capacité à gagner du temps et à diminuer ses efforts est l'une des qualités de l'être humain, qui a conduit à exercer la pensée depuis l'Antiquité jusqu'à ces dernières décennies, caractérisées par l'émergence du mélange entre la rapidité des calculs et la précision des résultats, et ce dans plusieurs domaines. Le problème des tournées de véhicules et ses extensions sont, pour les théoriciens de ces utilités, d'une réelle importance quant aux applications du monde réel. Des recherches récentes dans ce domaine ont permis des avancées significatives dans la formulation des problèmes ainsi que dans la conception et l'analyse d'algorithmes. Dans cette étude, nous nous intéressons au problème de la logistique. Notre attention se porte en particulier sur un cas des réseaux de télécommunication, 2ECON-NDPR, et sur la façon de créer des designs d'une manière intelligente pour assurer la vitalité et la durabilité de la circulation de l'information. En outre. Nous choisissons les variantes problème de tournées de véhicules avec fenêtres de temps et problème de tournées de véhicules sélectives des familles VRP et OP respectivement. C'est dans ce cadre que s'inscrit cette thèse. La conception des solutions pour ces problèmes fait appel à la technique de programmation approchée connue pour sa rapidité de calcul. Il s’agit de Beam-search et de la recherche locale à grand voisinage. Nous présentons tout d’abord une étude détaillée des dernières problématiques précitées ainsi que différents types de méthodes de résolutions. Puis, nous exposons une méthode de recherche locale à grand voisinage adaptée pour la conception de réseau de survie avec relais, une proposition d’un algorithme de résolution approchée à trois phases pour le CVRPTW et, enfin, une proposition d'un algorithme de résolution approchée hybride pour le TOP. / The need to save time as well as minimize effort is part of the human condition and it has driven our though s from antiquity until these last few decades, now characterized by the emergence of a mix in all fields between rapidity of calculation and precision in the result. The vehicle routing problem and its extensions are an important field for theorists of these utilities for real-world applications. Recent research in the field has led to significant advantages in problem formulation and designing algorithm analyses. This study considers logistics problems. A particular locus was given to a certain case of telecommunications networks 2ECONNDPR, as well as the method of intelligently creating designs to ensure vitality and durability in information circulation. Furthermore, the study considered vehicle routing problems, with time windows and orienteering problems from the VRP and OP families, respectively. This is the framework for this thesis. Solutions to these problems use programming techniques known for their calculation speed, i .e ., Beam-search and very large-scale neighborhood searching. First, a detailed study is presented of these above mentioned problems, along with the various types or resolution methods. Next, a very large-scale neighborhood search method is presented, suited to the design of a survivable network with relay, a proposition for a three-stage heuristic for the capacitated vehicle routing problem with time windows and, finally, a proposition for a hybrid heuristic for the team orienteering problem.