Vehicle Routing Problem with Time Windows is a hard optimization problem. Even though it has numerous practical applications, the question of solving it efficiently has not been satisfyingly solved yet. This thesis studies the Vehicle Routing Problem with Time Windows and presents several new algorithms for solving it. There are two heuristics presented here, as well as several more complex algorithms which use those heuristics as their components. The efficiency of presented techniques is evaluated experimentally using a set of test samples. As a part of this thesis, I have also developed a desktop application which implements presented algorithms and provides a few additional features useful for solving routing prob-lems in practice. Among others, there is a generator of pseudo-random problem instances and several visualization methods.

The objective of the thesis is to analyze the company´s expenses associated with relocation of the distribution centre as well as to describe the components of expenses associated with transport between company and customers. An important part of the thesis is comparison of the individual delivery routes. The theoretical part provides a brief description of Vehicle Routing Problem and its modifications as well as the different options how to solve it. The expenses calculations of truck transport are approximated to the reader. The practical part shows the real problem of Nestlé. The decreasing of the expenses is shown on real data. The reason of decreasing is the relocation of the distribution centre. The model routes are compared with the actual ones using MPL. It also shows the potential cost reduction.

The Vehicle Routing Problem has been around for more than 50 years and has been of major interest to the operations research community. The VRP pose a complex problem with major benefits for the industry. In every supply chain transportation occurs between customers and suppliers. In this thesis, we analyze the use of a multiple pheromone trial in using Ant Systems to solve the VRP. The goal is to find a reasonable solution for data environments of derivatives of the basic VRP. An adaptive object model approach is followed to allow for additional constraints and customizable cost functions. A parallel method is used to improve speed and traversing the solution space. The Ant System is applied to the local search operations as well as the data objects. The Tabu Search method is used in the local search part of the solution. The study succeeds in allowing for all of the key performance indicators, i.e. efficiency, effectiveness, alignment, agility and integration for an IT system, where the traditional research on a VRP algorithm only focuses on the first two. / Thesis (PhD)--University of Pretoria, 2010. / Industrial and Systems Engineering / unrestricted

This thesis deals with optimization problems of the parcels distribution. This issue can be solved on the ground of traveling salesman problem whose mathematical and economic model, including their modifications, are presented in the theoretical part of the thesis. We can solve these problems by using exact methods, heuristic and metaheuristic algorithms. In the theoretical part are described traveling salesman problem, traveling salesman problem with time windows, traveling salesman problem with multiple time windows and dynamic traveling salesman problem including possible ways of solution. In the practical part we can find application of problems on the real example, when we are finding the shortest possible route for the PPL's employee under different assumptions. The solution is obtained by using solver Gurobi within the modelling system MPL for Windows. In conclusion of the thesis the results are summarized and models are compared with each other.

The goal of the diploma thesis is to introduce and describe a heuristic method for finding a sub-optimal system of circuits in a generalized vehicle routing problem with time windows and time-dependent unit costs. Proposed method was built up on Clarke and Wright's savings method for the standard vehicle routing problem. Additionally, there has been described an algorithm for improving current solution via finding an optimal time harmonogram for a journey on each circuit within the found sub-optimal system of circuits.

Snow removal is an important optimization problem in countries with snowfall. Bus stops can only be cleared after the adjacent street is cleared. The problem of optimizing snow removal for bus stops in an urban area is a special case of the Travelling Salesman Problem with Time Windows, where each stop only can be cleared after a certain time has passed. The solver Gurobi is used to solve the mathematical model of this problem to optimality. A local search and a tabu search is implemented. The results of the mathematical model are compared to the results of the implemented tabu search method. The results show that if a solution needs to be produced quickly, the tabu search provides better solutions than Gurobi. / Snöröjning är ett viktigt optimeringsproblem i länder med snöfall. Busshållplatsen kan bara röjas efter att den angränsande vägen är röjd. Problemet att optimera snöröjning av busshållplatser i en stad är ett Handelsresandeproblem med tidsfönster, där varje hållplats bara kan röjas efter att en tid har gått. I arbetet har vi implementerat en tabusökning för att hitta snabbt hitta bra tillåtna lösningar till problemet. För att utvärdera prestandan hos tabusökningen har vi också implementerat en matematisk modell och använt Gurobi som lösare. Resultaten visar att tabusökningen är snabbast på att hitta tillåtna lösningar av god kvalité.

No description available.

No description available.

O objetivo deste trabalho é apresentar um novo tipo de sistema de levitação baseado na força de interação magnética entre uma bobina de núcleo não-magnético e um imã permanente, em casos de simetria axial entre os dispositivos, nos moldes do problema 23 proposto no TEAM Workshop. Este tema é bastante atual e vários métodos têm sido estudados e propostos em razão da complexidade na determinação precisa das forças sobre os imãs permanentes imersos em um campo magnético em um circuito magnético aberto. O primeiro grande desafio deste trabalho é obter uma expressão analítica para esta força de interação magnética em casos de simetria axial usando o método de cargas magnéticas ligadas. Para tal, algumas hipóteses simplificadoras foram adotadas como considerar o campo magnético gerado pela bobina aproximadamente uniforme em toda a face do imã permanente e assumir que a magnetização do imã é constante e independente da variação de sua distância para a bobina. Pretende-se aproveitar o sistema implementado neste trabalho como bancada experimental no Laboratório de Controle da Universidade de São Paulo. Foi projetado um controlador PID através de ferramentas gráficas obedecendo a alguns critérios de desempenho, tanto no domínio do tempo como no domínio da freqüência. Uma vez sintonizado, foi utilizado o toolbox Real-Time Windows Target do Simulink e a placa de aquisição PCI 6221 (da National Instruments) para controlar em tempo real a planta de levitação em malha fechada. Os resultados experimentais foram muito satisfatórios de modo que o modelo analítico foi considerado válido. O sistema apresentou boas características como, por exemplo, um bom acompanhamento do sinal de referência, mesmo em grandes excursões, erro de regime nulo, levitação estável em distâncias relativamente grandes e uma boa estabilidade radial. O uso de dois sensores Hall mostrou-se eficiente na determinação da posição do imã permanente. / The objective of this work is to present a new kind of levitation system based on the interaction force between a non-magnetic core coil and a permanent magnet, in the case of axial symmetry between devices, as proposed by TEAM Workshop problem 23. This theme is very current and various methods have been studied and proposed in face of the complexity in determining precisely the force over permanent magnets immersed in a magnetic field in an open magnetic circuit. The first big challenge of this work is to obtain an analytical expression for this interaction magnetic force in the case of axial symmetry using the equivalent magnetic charge method. For this, some simplifying hypothesis have been adopted like considering the magnetic field created by the coil approximately uniform over all the permanent magnets face and assuming that magnets magnetization is constant and independent of the variation of its distance to the coil. The system implemented in this work is intended to be used as an experimental bench for the Laboratory of Control of Sao Paulo University. A PID controller was projected by means of graphical tools according to some criteria for performance, both in the field of time as in the frequency domain. Once tuned, the toolbox Real-Time Windows Target of Simulink and the PCI-6221 acquisition board (of National Instruments) were used to control in real time the levitation plant in closed loop. The experimental results were very satisfactory so that the analytical model was considered valid. The system showed good characteristics as, for instance, a good tracking of reference signal, even in large excursions of it, null stationary error, stable levitation at relatively big gaps and a good radial stability. The use of two Hall-effect sensors proved to be efficient in the determination of permanent magnets position.

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.