Orientador: Eduardo Candido Xavier / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:15:42Z (GMT). No. of bitstreams: 1 Silveira_JeffersonLuizMoisesda_D.pdf: 2236708 bytes, checksum: 8e569408c2f068347058e36031689c3a (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos / Abstract: In this work we are interested in packing and routing problems. Assuming P ? NP, we have that there are no efficient algorithms to deal with such problems. Besides exact algorithms, two approaches to solve such problems are Approximation Algorithms and Heuristics. In this thesis we show algorithms using these three approaches for both packing and routing problems. The first two addressed problems are generalizations of classical packing problems: The Two Dimensional Knapsack problem and the Strip Packing problem. These problems were generalized by adding constraints on the way the items can be inserted/removed into/from the bin (These constraints appear in the context of routing problems). The third problem is combination of packing and routing problems. It is a generalization of the classical Pickup and Delivery problem. We propose the first approximation results for some packing problems. Besides that, we present some practical algorithms for the third problem. The heuristics were assessed through computational experiments by comparing their results with exact algorithms / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

This thesis demonstrates practical using of vehicle routing problem with time windows (VRPTW) and its solution by heuristic method. There are described teoretical principles of integer models, mathematical definitions of VRP with one or more vehicles, VRPTW and some heuristics for VRP. The practical part is solution of VRP by heuristic nearest neighbor. Product distribution is planed according to the firm settings in Prague. I compare existing situation and computed solution that show benefits of using described methods in conclusion.

This diploma thesis deals with Ant Colony algorithms and their usage for solving Travelling Salesman Problems and Vehicle Routing Problems. These algorithms are metaheuristics offering new approach to solving NP-hard problems. Work begins with a description of the forementioned tasks including ways to tackle them. Next chapter analyses Ant Colony metaheuristic and its possible usage and variations. The most important part of the thesis is practical and is represented by application Ant Colony Optimization Framework. It is easily extensible application written in Java that is able to solve introduced problems. In conclusion this work presents analysis of solutions on test data.

This thesis focuses on a description of the split delivery vehicle routing problem (SDVRP), in which the restriction that each customer has to be visited exactly once is not assumed, contrary to the classical vehicle routing problem, and split deliveries are allowed. Considering the fact that the split delivery vehicle routing problem in NP-hard, a number of heuristic algorithms proposed in the literature are presented. Computational experiments are reported and the results show that the largest benefits of split deliveries are obtained in case of instances with fairly specific characteristics and also several drawbacks of implemented Tabu Search algorithm (SPLITABU) are point out.

There are many distribution tasks, that vary in a number of vehicles, time windows, dividend or undivided delivery or if it is static problems or dynamic problems. In this essay I focus just on few of them. At first I put my mind to simple statistic distribution task with one vehicle. Later I extend it with time windows, when the point can be served by one car and by many cars. In the essay it will be solved the real task of distribution and delivery transportation of infusion in the hospitals. Because of the difficulty of solution I have to use the heuristic methods - Method of nearest neighbour, Savings method and Insert method. All these methods are modified by capacity requirements, time windows and also observence of the rules, which the drivers have to keep during a distribution. The aim is to minimize the distance travelled by the vehicles. And at least the company could be recommended the best solution.

This thesis deals with the optimization of distribution of products to consumers based on a real case study of a particular company from Opava. For this purpose, a mathematical optimization model is used to illustrate the vehicle routing problem. The study will also offer an explanation on the relevancy of heuristic methods, mainly with respect to their application in solving real life situations analogous to the one surveyed. On the basis of chosen heuristic methods (i.e. the nearest neighbour algorithm and the savings algorithm) and having taken into account the restricting conditions of the company, four algorithms were designed. These four algorithms are programmed in Visual Basic for Applications MS Excel 2007. They are aimed at solving the real problems with the distribution of ordered products that the particular company must deal with. The thesis compares the results provided by an employee of this company, and the results presented by the designed algorithms.

Traditionally, route planning in the transportation sector has only focused on minimizing the total distance driven when transporting goods or people. This is often done using software tools since planning the optimal route is a complex task that is hard to solve by hand. While driving the shortest distance possible is an effort towards lowering fuel costs, which is one of the largest operating costs for truck transportation companies, it is not necessarily the most fuel efficient route. Recently, research has emerged regarding fuel minimizing route planning in order to perform transport operations at the lowest fuel cost possible. One factor contributing to fuel consumption is vehicle speed, since high speed means high wind resistance. Fuel can therefore be conserved by driving at lower speeds. Though lower speeds means longer travelling time, meaning that if the route is disrupted, causing a delay, there is an increased risk that all tasks cannot be performed during the started working day. The purpose of this thesis is to determine how to plan fuel efficient routes in a transportation system prone to disruptions. It was conducted at Scania to further understand how their truck customers can increase profitability in their businesses by planning fuel efficient routes. The truck transportation business is under heavy pressure with low margins. It is therefore valuable to plan fuel efficient routes. The outcome of this thesis is two linear programming models for route planning that take truck capacity, customer demand and time windows for delivery into account. The first model can be used during planning to find a fuel efficient route in order to deliver to all customers to the lowest fuel cost possible. The model gives a route with predetermined average speeds between the customers, as well as arrival time at each customer. When appropriate, the truck is proposed to drive at a slightly decreased speed, to lower wind resistance and thereby fuel consumption. By also taking load weight into account, the route can be planned such that a heavy part of the load is delivered early, reducing the weight carried for the rest of the route. The proposed model accomplishes on average 6.3 % lower fuel cost, compared to the most commonly used route planning model, where the shortest total driving distance is sought. If something would happen that disrupts the route, it might be impossible to deliver all customers before the day ends. To handle those situations, a second model is proposed. Once the transport is delayed, the model will revise the initial route and propose a new route based on a cost of delaying a delivery. The goal is then to deliver as much as possible to the lowest possible cost. The new route will still consist of predetermined average speeds and arrival times. The proposed model is a tool for handling the complex task of recalculating routes once a disruption occurs. In summary, the first model provides support to plan a route that potentially lowers the operational costs for truck transportation companies. If the planned route is disrupted, the second model will revise it and give a new route with new speeds and arrival times. If possible, the revised route will still result in making all deliveries, otherwise the model will postpone the smallest deliveries to the next day. Together, the two models serve as a valuable support for truck transport companies that want to increase their profitability by lowering their operational costs. / Traditionellt har ruttplanering inom transportsektorn endast fokuserat på att minimera den totala körsträckan vid transport av gods eller människor. Detta görs ofta med hjälp av mjukvaruverktyg, eftersom optimal ruttplanering är en komplex uppgift som är svår att lösa för hand. Att köra den kortaste totalsträckan är ett sätt att sänka bränslekostnaderna, vilket är en av de största driftskostnaderna för lastbilstransportföretag, men det är inte nödvändigtvis den mest bränsleeffektiva rutten. Den senaste tiden har allt mer forskning bedrivits inom bränsleminimering för att kunna utföra transportuppdrag till lägsta möjliga bränslekostnad. En faktor som bidrar till bränsleförbrukningen är fordonets hastighet, eftersom hög hastighet innebär högt luftmotstånd. Bränsleförbrukningen kan därför minskas genom att köra i lägre hastigheter. Även om lägre hastigheter betyder längre körtid, vilket innebär att om rutten störs och lastbilen blir försenad, finns det en ökad risk att allt inte kan levereras under den påbörjade arbetsdagen. Syftet med detta arbete är att bestämma hur bränsleeffektiva rutter kan planeras i ett transportsystem benäget för störningar. Arbetet genomfördes på Scania för att förstå hur deras lastbilskunder kan öka lönsamheten i sina företag genom att planera bränsleeffektivare rutter. Lastbilstransportbranschen är under hög press med låga marginaler. Det är därför värdefullt för Scanias lastbilskunder att planera bränsleeffektiva rutter. Arbetet resulterade i två ruteplaneringsmodeller som tar hänsyn till lastkapacitet, kundbehov och tidsfönster för leverans. Den första modellen kan användas vid planering för att hitta en bränsleeffektiv rutt så att alla kunder levereras till lägsta möjliga bränslekostnad. Modellen ger en rutt med förbestämda genomsnittshastigheter mellan kunderna, såväl som ankomsttid hos varje kund. När det anses lämpligt föreslås något minskade hastigheter, för att minska luftmotståndet och därigenom bränsleförbrukningen. Genom att även ta hänsyn till vikt, kan rutten planeras så att en tung del av lasten levereras tidigt, vilket minskar den vikt som transporteras på resterande sträckor. Den föreslagna modellen uppnår i genomsnitt 6,3% lägre bränslekostnad jämfört med den vanligaste ruteplaneringsmodellen, som ger den kortaste totala körsträckan. Om något skulle hända som stör rutten kan det vara omöjligt att leverera alla kunder innan dagen slutar. För att hantera dessa situationer föreslås en andra modell. När transporten är försenad planerar modellen om den ursprungliga rutten och föreslår en ny rutt baserat på kostnaden för att skjuta upp en leverans. Målet är då att leverera så mycket som möjligt till lägsta möjliga kostnad. Den nya rutten består fortfarande av förbestämda medelhastigheter och ankomsttider. Genom att använda den föreslagna modellen tillhandahålls ett verktyg för att hantera den komplexa uppgiften att planera om rutten vid en störning. Sammanfattningsvis ger den första modellen stöd för att planera en rutt som potentiellt sänker driftskostnaderna för lastbilstransportföretag. Om den planerade rutten utsätts för en störning, föreslår den andra modellen en ny rutt med nya hastigheter och ankomsttider. Om det är möjligt innebär den nya rutten fortfarande att lastbilen levererar till alla kunder, om inte skjuts de minsta leveranserna upp till nästa dag. Tillsammans är de två modellerna ett värdefullt stöd för lastbilstransportföretag som vill öka lönsamheten genom att sänka sina driftskostnader.

The diploma thesis deals with the use of heuristic methods for solving messenger problems. The first part focuses on the proposed vehicle routing problems, especially on travelling salesman problems and the messenger problems. For individual problems are theoretically discussed mathematical models for variants with one or more vehicles and the expansion of the use of time windows and capacity constraints. The second part introduces heuristic algorithms for the method of nearest neighbour, savings method, insertion method and the exchange method on the travelling salesman problems. Then all of the mentioned algorithms are modified for use in three variants of messenger problem. First, the disposition of one vehicle, the second allows more messengers in the same starting point and the last option is more messengers at different starting points. The last part describes computational experiments and comparison of results provided by different methods. The diploma thesis includes application for solving messenger problems using savings methods programmed in Visual Basic for Application in MS Excel.

At the basic there is a connection between operation research and automotive logistics. The supply chain in this type of industry is hard to coordinate and flexibility is considered as a main key indicator. Companies increase their competitiveness through the optimization of supply chain and try to take control of every flow or a process. This idea goes throughout the departments. The main concept, which is about a connection of whole supply chain with information flow means, that there isn't need of stock and every input is highly available on time and in requested quantity and quality. This thesis describes inbound logistics and introduces some of the methods used for planning vehicle routes. In our situation which is based on car maker data set was chosen a group of a suppliers for the analysis. We used vehicle routing problem with some modifications, heuristics based on the covering problem. Founded solution was compared with the present state.

Nowadays, when great emphasis is put on cost savings, transport optimization is necessary part of every company life in which transportation costs produce significant part. There are optimization methods and possibilities presented in this thesis. In the first chapter there are explained methods such as the travelling salesman problem, the vehicle routing problem, the multiple vehicle routing problem and the split delivery vehicle routing problem and then the reader gets to know the heuristics methods in the chapter two where description of the nearest neighbour method, Clarke-Wright method and split delivery heuristic is mentioned. In the last but one chapter author applies previous methods on concrete distribution arranged by Movianto Česká republika s.r.o. on 5th September, 2013. Based on gained outputs, analysis and comparison of results (including the original distribution) are provided in the fourth chapter. Obtained results of analysis lead to recommendation on how the company should plan its future distribution.