This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.

Made available in DSpace on 2016-06-02T19:52:05Z (GMT). No. of bitstreams: 1 6045.pdf: 14667118 bytes, checksum: f13a2c0983ea271f2e60ed298b158806 (MD5) Previous issue date: 2014-05-26 / Agência Nacional de Petróleo / This work studies the ship routing and scheduling problem in oil transportation from offshore platforms to inland terminals. It is motivated by a real situation in a Brazilian oil company. Brazil is one of the world's greatest oil producers and has around 80% of its oil explored in offshore mode. Thus, transportation costs play an important role in achieving operational excellence, and the recent growth trends for oil exploration in Brazil has transformed its operations and demanded agile and effective decision support systems for addressing the oil sector dynamism. This work's goal consists in developing and applying an optimization-based approach using a mixed integer linear programming model in real decision-making situations, along with a solution method based on mathematical programming (MIP-heuristics) in order to solve the model, such as relax-and-fix. The proposed model is inspired in a problem formulation for pickup and delivery with time windows (PDPTW) and heterogeneous fleet, where costs incurred for fuel consumption and fleet contracts is the objective function to be minimized. The pickup and delivery pairs are predetermined and the model's main decision refers to ship allocation to these pairs compounding a route. Furthermore, some additional constraints are modeled and proposed, such as terminal access and platform mooring limitation according to ship types, as well as product blend incompatibility. The model was implemented in a modeling language along with an optimizarion software. Computational experiments with the model and the heuristics are presented for different data sets supplied by the case study company. These experiments show the potential benefits of this approach for finding good solutions for the problem as well as the dificulty in finding solutions for realistic instances due to its NP-hard characteristics. / Este trabalho estuda o problema de roteirização e programação de navios que realizam o escoamento de petróleo das plataformas marítimas para terminais terrestres, motivado por uma situação real de uma empresa brasileira da indústria petrolífera. O Brasil é um dos maiores produtores mundiais de petróleo, e cerca de 80% de seu petróleo é explorado no mar. Dentro deste contexto, os custos de transporte desempenham um papel importante na busca pela excelência operacional e as tendências de crescimento da exploração de petróleo no Brasil têm tornado as operações mais complexas e demandantes de sistemas de apoio à decisão ágeis e eficazes que contemplem o dinamismo do setor petrolífero. O objetivo deste trabalho consiste em desenvolver e aplicar uma abordagem de otimização baseada em um modelo de programação linear inteira mista em situações reais de tomada de decisão, em conjunto com métodos de solução baseados em programação matemática (MIP-Heuristics) para resolver o modelo, como relax-and-fix. O modelo proposto é inspirado em uma formulação de problemas de coleta e entrega com janelas de tempo (pickup and delivery with time windows PDPTW) e frota heterogênea, no qual busca-se minimizar os custos decorrentes do consumo de combustível dos navios e contratos de afretamento. O modelo é do tipo origem-destino, no qual os pares coleta/entrega são pré-determinados e a decisão do modelo refere-se à alocação de navios para os diferentes pares, compondo uma rota. Além disso, são propostas restrições adicionais que contemplam limitações de acesso a terminais e de atracação em plataformas de acordo com os tipos de navio, além da incompatibilidade de mistura de produtos, entre outros. O modelo foi implementado utilizando uma linguagem de modelagem em conjunto com um software de otimização. Experimentos computacionais com o modelo e as heurísticas são apresentados para diferentes conjuntos de dados fornecidos pela empresa e comprovam o potencial das abordagens para encontrar boas soluções para o problema, mas também suas dificuldades para encontrar soluções para exemplares de tamanho realista, por tratar-se de um problema NP-difícil do ponto de vista de teoria de complexidade.

No description available.

This thesis deals with optimization problems with main focus on logistic Vehicle Routing Problem (VRP). In the first part term optimization is established and most important optimization problems are presented. Next section deals with methods, which are capable of solving those problems. Furthermore it is explored how to apply those methods to specific VRP, along with presenting some enhancement of those algorithms. This thesis also introduces learning method capable of using knowledge of previous solutions. At the end of the paper, experiments are performed to tune the parameters of used algorithms and to discuss benefit of suggested improvements.

<p> Orbital Debris is a growing challenge for the Space Industry. The increasing density of derelict objects in high-value orbital regimes is resulting in more conjunction warnings and break-up events with cascading repercussions on active satellites and spacecraft. The recent rapid growth of the commercial space industry, in particular proliferated satellite constellations, has placed orbital debris remediation at the forefront of Space Industry efforts. The need to remove existing debris, combined with a growing demand for active satellite life extension services, has created an emerging market for space logistics, in particular spacecraft capable of rendezvous and docking, orbital refueling, debris deorbiting, or object relocation. This market has seen numerous companies emerge with multi-purpose on-orbit servicing platforms. This ecosystem poses technological, economical, and policy questions to decision-makers looking to acquire platforms or invest in technologies and requires a System-of-Systems approach to determine mission and system concepts of merit. An open-source modeling, analysis, and simulation software toolbox has been developed which enables rapid early-stage analysis and design of diverse fleets of on-orbit servicing platforms, with a specific emphasis on active debris removal applications. The toolbox provides fetching and processing of real-time orbital catalog data, clustering and scoring of high-value debris targets, flexible and efficient multi-vehicle multi-objective time-varying routing optimization, and fleet-level lifecycle cost estimation. The toolbox is applied to a diverse sample of promising commercial platforms to enable government decision-makers to make sound investment and acquisition decisions to support the development of ADR technologies, missions, and companies. </p>

Adaptive Large Neighborhood Search (ALNS) is a fairly recent yet popular single-solution heuristic for solving discrete optimization problems. Even though the heuristic has been a popular choice for researchers in recent times, the parallelization of this algorithm is not widely studied in the literature compared to the other classical metaheuristics. To extend the existing literature, this study proposes several different parallel schemes to parallelize the basic/sequential ALNS algorithm. More specifically, seven different parallel schemes are employed to target different characteristics of the ALNS algorithm and the capability of the local computers. The schemes of this study are implemented in a master-slave architecture to manage and assign loads in processors of the local computers. The overall goal is to simultaneously explore different areas of the search space in an attempt to escape the local minima, taking effective steps toward the optimal solution and, to the end, accelerating the convergence of the ALNS algorithm. The performance of the schemes is tested by solving a capacitated vehicle routing problem (CVRP) with available wellknown test instances. Our computational results indicate that all the parallel schemes are capable of providing a competitive optimality gap in solving CVRP within our investigated test instances. However, the parallel scheme (scheme 1), which runs the ALNS algorithm independently within different slave processors (e.g., without sharing any information with other slave processors) until the synchronization occurs only when one of the processors meets its predefined termination criteria and reports the solution to the master processor, provides the best running time with solving the instances approximately 10.5 times faster than the basic/sequential ALNS algorithm. These findings are applied in a real-life fulfillment process using mixed-mode delivery with trucks and drones. Complex but optimized routes are generated in a short time that is applicable to perform last-mile delivery to customers.

Mit dem Ende des Zweiten Weltkrieges und mit der Proklamierung der DDR im Jahre 1949 wurde ein neues Kapitel in der Geschichte der deutsch-polnischen Beziehungen eröffnet. Die DDR und die Volksrepublik Polen wurden der Regierung der Sowjetunion unterstellt und als „Brüderländer“ aufgefordert, gegenseitige Kontakte in verschiedenen Bereichen zu pflegen. Eines von diesen Gebieten war auch das kulturelle Leben, von dem ein bedeutender Teil der Filmaustausch war. In den Jahren 1949-1990 wurden im Lichtspielwesen der DDR über 300 Spielfilme aus der Volksrepublik Polen verliehen, was zweifelsohne eine imposante Anzahl war. Die große Mehrheit dieser Filme wurde in der DDR-Presse rezensiert. 40 Jahre lang waren die Kritiken in Bezug auf das Filmangebot aus der Volksrepublik Polen im Lichtspielwesen der DDR ein fester Bestandteil der DDR-Alltags- und Kinopresse. Es sind innerhalb von dieser Zeit tausende von Rezensionen zu polnischen Filmen geschrieben worden, von deren ein großer Teil in dieser Arbeit analysiert wurde. Die Analyse der Pressebeiträge stellt ein Bild der Beurteilungen der polnischen Produktionen durch die DDR-Journalisten dar, lässt aber auch ganz genau Änderungen in den Beziehungen zwischen der Volksrepublik Polen und der DDR in den Jahren 1949-1989 erkennen. Dadurch bildet die politische Situation in den beiden Nachbarländern den Hintergrund dieser Arbeit, wobei fünf wichtige geschichtliche Phasen ausgewählt werden, die die Kapitel der Arbeit bilden. Zwei Unterkapitel dieser Arbeit werden der Rezeption der Filme von zwei bedeutendsten polnischen Regisseuren der Nachkriegszeit gewidmet: Andrzej Wajda und Krzysztof Zanussi. / With the end of the Second World War, and the formation of the DDR in 1949, a new chapter in the history of German-Polish relations began. The DDR and the People''s Republic of Poland were placed under the control of the Soviet Union, and as “brother lands” were encouraged to foster a mutual contact and exchange in various areas. One such area of exchange was in cultural life, of which a significant part was the sharing of films from both countries. In the years 1949-1990 over 300 Polish films were distributed in East German cinemas, an indisputably significant figure. The great majority of these films were reviewed in the DDR press, and in fact reviews of the cinematic offerings from the People''s Republic of Poland formed a regular component of East German newspapers during this period of 40 years. Over this time, thousands of reviews of Polish films were written, a large number of which are analysed in this dissertation. The analysis of press articles forms a picture of how Polish film productions were regarded by DDR journalists, but also reveals the changing relationship between the two countries in the period from 1949 to 1989. Thus the political situation in these neighbouring countries forms the background of this dissertation, with each chapter discussing one of five important historical phases. Two sub-chapters of this dissertation are devoted to a discussion of the East German reception of the films of Andrzej Wajda and Krzysztof Zanussi – two of Poland''s most important post-war directors.

El sector de servicio de mantenimiento demuestra un crecimiento continuo desde la incorporación de máquinas para el desarrollo de operaciones. En el Perú, este sector tiene un crecimiento lento, a pesar de ello, algunas empresas de mantenimiento han encontrado oportunidades en nichos poco explorados, como los mantenimientos a cajeros automáticos. Sin embargo, el tipo de servicio que brindan no cumplen ciertos aspectos esenciales para satisfacer la demanda, debido al exceso de tiempo en la atención del servicios y llegada a destiempo para la atención. Es por ello, que el objetivo principal del proyecto es reducir el lead time para el cumplimiento del cronograma anual, ya que se presencia una pérdida del 33.44% de la facturación del servicio de mantenimiento en el año 2019. Por esta razón, se diseña un modelo de gestión de servicio de mantenimiento que comprende la asignación de ruta por el vehicle routing problem mediante la distancia euclidiana y la estandarización de procesos mediante el estudio de tiempos que será validado mediante la simulación del software Arena. Asimismo, se analiza un flujo de caja económico del cual se obtiene un índice de rendimiento (RBC) de S/. 2.31. Finalmente, ha sido posible la reducción del lead time y el cumplimiento del cronograma de mantenimiento. / The maintenance service sector shows continuous growth since the incorporation of machines for the development of operations. In Peru, this sector has a slow growth, despite this, some maintenance companies have found opportunities in little-explored niches, such as maintenance of ATMs. However, the type of service they provide does not meet certain essential aspects to satisfy the demand, due to the excess time in the service and arrival at the wrong time for the service. That is why the main objective of the project is to reduce the lead time for compliance with the annual schedule, since there is a 33.44% loss of the maintenance service billing in 2019. For this reason, a Maintenance service management model that includes the route assignment for the vehicle's routing problem using the standard Euclidean distance and the laization of processes through the study of times that will be validated through the simulation of the Arena software. Likewise, an economic cash flow is analyzed from which a performance index (RBC) of S /. 2.31. Finally, it has been possible to reduce lead time and meet the maintenance schedule. / Trabajo de investigación

No description available.

This thesis introduces a new model formulation to solve routing and scheduling problems, with the main applications in answering routing and scheduling problems faced by a sea-cargo shipping company and a railroad company. For the work in sea-cargo routing and scheduling, we focus on the tramp shipping operation. Tramp shipping is a demand-driven type of shipping operation which does not have fixed schedules. The schedules are based on the pickup and download locations of profitable service requests. Given set of products distributed among a set of ports, with each product having pickup and download time windows and a destination port, the problem is to find the schedule for a fleet of ships that maximizes profit over a specified time horizon. The problem is modeled as a Mixed Integer Non-Linear Program and reformulated as an equivalent Mixed Integer Linear Program. Three heuristic methods, along with computational results, are presented. We also exploit the special structure enjoyed by our model and introduce an upper-bounding problem to the model. With a little modification, the model is readily extendable to reflect soft time windows and inter-ship cargo-transfers. The other part of our work deals with train routing and scheduling. A typical train shipment consists of a set of cars having a common origin and destination. To reduce the handling of individual shipments as they travel, shipments are grouped into blocks. The problem is that given sets of blocks to be carried from origins to destinations, construct the most cost effective train routes and schedules and determine block-to-train assignments, such that the number of block transfers (block swaps) between trains, the number of trains used, and some other cost measures are minimized. Incorporating additional precedence requirements, the modeling techniques from the shipping research are employed to formulate a mixed integer nonlinear program for this train routing and scheduling problem. Computational results are presented.