This diploma thesis describes a logistic problem of the company JACER-CZ Ltd. The main focus is on identifying optimal routes about the Euro pallets distribution. The Euro pallets are standardized at length replaceable transport pallets which are in Europe. The aim of this thesis is to find a solution which will meet requirements of all thirteen customers and simultaneously a total route length of all vans will be minimalized. At first there is the mathematical model about the delivery assignment with the split delivery vehicle calculated by solvers CPLEX and Gurobi. Then the original and the modified example is solved manually by heuristic algorithms. It is concerned the nearest neighbour algorithm, savings algorithm, the insertion algorithm and the heuristic method for the split delivery vehicle routing problem.

Unternehmen der Transportbranche müssen gerade im operativen Tagesgeschäft bei der Tourenplanung und Transportdisposition Planungsprobleme lösen, die ein hohes Maß an Dynamik aufweisen. Speziell die Inputfaktoren der Tourenplanung sind größtenteils dynamisch und stochastisch. Aus Sicht des Autors kann die Qualität von Tourplanungsergebnissen durch die zeitnahe Berücksichtigung unvorhergesehener Ereignisse nachhaltig verbessert werden. Jedoch findet diese zunehmend erfolgskritische Funktionalität in der Literatur bisher nur unzureichend Beachtung, obwohl das Tourenplanungsproblem (Vehicle Routing Problem (VRP)) eines der wichtigsten und am meisten erforschten kombinatorischen Optimierungsprobleme ist. Verfahren für kapazitierte dynamische Tourenplanungsproblemstellungen sind in der Literatur kaum zu finden. Speziell im Bereich der Algorithmen, die eine große Lösungsgeschwindigkeit, eine leichte Verständlichkeit, eine aus praktischer Sicht akzeptable Lösungsgüte aufweisen und die Möglichkeit besitzen, die aktuellen Routenpläne der Fahrzeuge ausgehend von der momentanen geographischen Position real-time zu verändern, besteht Forschungsbedarf. Die Arbeit geht daher der Forschungsfrage nach, wie ein Verfahren für die dynamische Tourenplanung zu konstruieren ist, welches das kapazitierte dynamische Tourenplanungsproblem mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges unter Einhaltung sehr kurzer Rechenzeiten bei größtmöglicher Verständlichkeit löst. Durch die genannten Kriterien wird im Rahmen der Arbeit der Schwerpunkt auf die Modifikation von klassischen heuristischen Verfahren für die Lösung von dynamischen Tourenplanungsproblemen gelegt. Die Arbeit befasst sich sowohl mit dem Gesamtkonzept zur Disposition dynamischer Kunden als auch mit konkreten Modellen und Verfahren zur Lösung von Subproblemen innerhalb des Gesamtkonzeptes. Ferner erfolgt die Präsentation von umfangreichen Simulationsergebnissen, die auf der durchgeführten softwaretechnischen Implementierung der entwickelten Verfahren basieren. Die gute Anwendbarkeit der neuen Verfahren in der Praxis wird gezeigt. Zwecks der möglichst ganzheitlichen Betrachtung des Themengebietes erfolgt in der Arbeit zum einen sowohl die Erörterung von quantitativen als auch von qualitativen Aspekten der dynamischen Tourenplanung und zum anderen die Analyse von Schnittstellen zwischen der dynamischen Tourenplanung und eng damit verbundenen Bereichen wie Flottenmanagement oder Auftragseingang bzw. -disposition. Hierzu werden die Informationsflüsse zwischen den beteiligten Elementen im Rahmen des dynamischen Dispositionsprozesses aufgezeigt, telematische Komponenten zur Unterstützung des Informationsmanagements und der Informationsübertragung vorgestellt sowie die benötigten Inputdaten erläutert. Den Schwerpunkt der Arbeit stellt jedoch die Entwicklung von neuen quantitativen Methoden zur dynamischen Tourenplanung dar.

Background Efficient underwater operations with autonomous underwater vehicles (AUVs) relying on several factors for a mission to be successful, such as operation time, distance covered, and waiting times. Today’s methods and processes for AUVs often struggle with inefficiencies and lack of route optimization. These challenges can result in increased operational costs and suboptimal performance. Minimizing operation time and utilizing route planning algorithms enables adaptation to operational challenges, potentially resulting in cost savings. Objectives This thesis aims to identify an efficient and practical solutions that will improve the operations for AUVs and the objective is to optimize the diving process through suboptimal routing algorithms in a predefined scenario. The study addresses one primary question to achive the aim. The question were: How can routing algorithms be implemented to improve the efficiency and reduce the operation time of Autonomous Underwater Vehicles? Methods The method describes three heuristic algorithms for optimizing the operations of AUVs. The first algorithm, the nearest neighbor heuristic (NNH) aims to minimize the distance an AUV needs to travel to recover and deploy ocean bottom nodes (OBN) within a cluster. The second algorithm, inspired by railway traffic, tries to prevent overlaps and minimizing the waiting times at the depot station. The third algorithm is highlighted as a local optimization algorithm that prioritizes the shortest waiting time over the nearest distance, adapting dynamically to available depot stations. Results The results in this thesis are derived from numerous simulations from different scenarios. The relationship between operations time and waiting time for different scenarios was obtained. The first algorithm proved to work for this type of situation. The second algorithm demonstrated its ability to yield superior solutions, albeit at the cost of being time-consuming due to a high number of iterations. The third algorithm was examined under conditions with and without delays. Even with delays, the algorithm consistently manages disturbances effectively. Conclusions While achieving an exact optimal solution remains challenging due to complexity, the research showed promising improvements in the endurance of the AUVs through the algorithms. The first algorithm was effective in minimizing the distance the AUVs traveled by selecting the most efficient path from numerous potential solutions. The second algorithm was slow due to a large number iterations, but the algorithm was able to find a solution where the operation and waiting time of the AUV could be reduced. The third algorithm was faster, but generally resulted in longer operation times. Also, increasing the number of AUVs resulted in shorter operation times but led to longer waiting times at the depot station, particularly in scenarios that became saturated with too many AUVs. / Bakgrund Undervattensoperationer med autonoma undervattensfarkoster (AUV:er) är beroende av flera faktorer för framgångsrika uppdrag, såsom driftstid, avstånd och väntetider. Dagens metoder och processer för AUV:er har ofta problem med ineffektivitet och bristande optimering av rutter. Dessa utmaningar kan leda till ökade driftkostnader och suboptimal prestanda. Genom att minimera operationstiden och använda ruttplaneringsalgoritmer möjliggörs anpassning till operativa utmaningar, vilket potentiellt kan resultera i kostnadsbesparingar. Syfte Detta examensarbete syftar till att utveckla effektiva och praktiska lösningar för att förbättra systemets prestanda och målet är att optimera rutterna genom suboptimala algoritmer i ett fördefinierat scenario. Arbetet behandlar en primärfråga för att uppnå målet. Frågan var: Hur kan ruttalgoritmer implementeras för att förbättra effektiviteten och minska drifttiden för autonoma undervattensfarkoster? Metod Metoden beskriver tre heuristiska algoritmer för att optimera driften förAUV:er. Den första algoritmen, närmaste granne heuristiken (NNH), syftar till attminimera avståndet en AUV behöver resa för att hämta och placera ut havsbottennoder (OBN) inom en kluster. Den andra algoritmen, inspirerad av tågtrafiken, syftar till att endast en AUV befinner sig vid depåstationen åt gången för att förhindra konflikter och minimera väntetider. Den tredje algoritmen är en lokal optimeringsalgoritm som prioriterar kortaste väntetiden över närmaste avstånd och anpassar sig dynamiskt till tillgängliga depåstationer. Resultat Resultaten i denna uppsats baseras på ett flertal simuleringar med olika scenarier. Förhållandet mellan drifttid och väntetid för olika scenarier erhölls. Den första algoritmen visade sig fungera bra för denna typ av situation. Den andra algoritmen visade sin förmåga att ge bättre lösningar, trots att den var tidskrävande pågrund av ett högt antal iterationer. Den tredje algoritmen undersöktes under förhållanden med och utan förseningar. Trots förseningar lyckades algoritmen konsekvent hantera störningar effektivt. Slutsats Trots komplexiteten med att tillhandahålla en exakt optimal lösning, visade arbetet förbättringar i AUV:ers uthållighet genom olika algoritmer. Den första algoritmen var effektiv för att minimera det avstånd som AUV:er färdades genom att välja en optimal väg bland många potentiella lösningar. Den andra algoritmen var långsam på grund av många iterationer, men algoritmen kunde hitta en lösning där AUV:ens drift- och väntetid kunde minskas. Den tredje algoritmen var snabbare men resulterade i längre drifttider. Vidare resulterade ökningen av antalet AUV:er i en minskning av drifttider men ökade väntetider, särskilt i scenarier som blev mättade med för många AUV:er.

Examensarbetet handlar om att minimera en total servicekostnad för företaget Chargestorm då de skall utföra service på sina laddningscentraler för elbilar. En ruttoptimering har gjorts som resulterar i ett antal rutter som är tänka att användas av en servicetekniker när denne åker runt och utför service på laddningscentralerna. En simulering har också gjorts för att påvisa de bästa tidsintervallen då olika typer av service kan ske, med målet att minimera den totala servicekostnaden.

This thesis deals with solving a real case from one specific part of Operations Research -- Discrete Models. The case can be classified as Vehicle Routing Problem (VRP) which is a subset of classical Travelling Salesman Problem (TSP). The VRP is modified TSP when requirements of customers and capacities of trucks play role. The data needed for calculations were taken from the real situation of Pivovar Svijany a.s. The problem can be defined as VRP with cars with different capacities and split delivery. Even though the mathematic model of the problem is known and described in the thesis, the size of the problem is too big to be optimized. Therefore heuristic was used to solve it. Because of the good computational results in the past the savings algorithm was chosen. Its model was set using Visual Basic for Applications (VBA). The thesis (among others) analyses the sensitivity of the output on the values of the factors that can be chosen by the analyst. At the end of the thesis the best found solution is presented and the initial and the new scheme of the circles are compared.

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.

Agricultural producers consider utilizing multiple machines to reduce field completion times for improving effective field capacity. Using a number of smaller machines rather than a single big machine also has benefits such as sustainability via less compaction risk, redundancy in the event of an equipment failure, and more flexibility in machinery management. However, machinery management is complicated due to logistics issues. In this work, the allocation and ordering of field paths among a number of available machines have been transformed into a solvable Vehicle Routing Problem (VRP). A basic heuristic algorithm (a modified form of the Clarke-Wright algorithm) and a meta-heuristic algorithm, Tabu Search, were employed to solve the VRP. The solution considered optimization of field completion time as well as improving the field efficiency. Both techniques were evaluated through computer simulations with 2, 3, 5, or 10 vehicles working simultaneously to complete the same operation. Furthermore, the parameters of the VRP were changed into a dynamic, multi-depot representation to enable the re-route of vehicles while the operation is ongoing. The results proved both the Clarke-Wright and Tabu Search algorithms always generated feasible solutions. The Tabu Search solutions outperformed the solutions provided by the Clarke-Wright algorithm. As the number of the vehicles increased, or the field shape became more complex, the Tabu Search generated better results in terms of reducing the field completion times. With 10 vehicles working together in a real-world field, the benefit provided by the Tabu Search over the Modified Clarke-Wright solution was 32% reduction in completion time. In addition, changes in the parameters of the VRP resulted in a Dynamic, Multi-Depot VRP (DMDVRP) to reset the routes allocated to each vehicle even as the operation was in progress. In all the scenarios tested, the DMDVRP was able to produce new optimized routes, but the impact of these routes varied for each scenario. The ability of this optimization procedure to reduce field work times were verified through real-world experiments using three tractors during a rotary mowing operation. The time to complete the field work was reduced by 17.3% and the total operating time for all tractors was reduced by 11.5%. The task of a single large machine was also simulated as a task for 2 or 3 smaller machines through computer simulations. Results revealed up to 11% reduction in completion time using three smaller machines. This time reduction improved the effective field capacity.

The transportation phase of solid waste management is highly critical as it may constitute approximately 60 to 75 percent of the total cost. Therefore, even a small amount of improvement in the collection operation can result in a significant saving in the overall cost. Despite the fact that there exist a considerable amount of studies on Vehicle Routing Problem (VRP), a vast majority of the existing studies are not integrated with GIS and hence they do not consider the path constraints of real road networks for waste collection such as one-way roads and U-Turns. This study involves the development of computer software that optimizes the waste collection routes for solid waste transportation considering the path constraints and road gradients. In this study, two different routing models are proposed. The aim of the first model is to minimize the total distance travelled whereas that of the second model is to minimize the total fuel consumption that depends on the loading conditions of the truck and the road gradient. A comparison is made between these two approaches. It is expected that the two approaches generate routes having different characteristics. The obtained results are satisfactory. The distance optimization model generates routes that are shorter in length whereas the fuel consumption optimization model generates routes that are slightly higher in length but provides waste collection on steeply inclined roads with lower truck load. The resultant routes are demonstrated on a 3D terrain view.

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.