Optimização de processos na cadeia de abastecimento : o caso do transporte de mercadorias

Abstract

Num passado recente, tem-se verificado uma melhoria contínua das condições de transporte. As infraestruturas construídas, desde estradas a linhas ferroviárias tiveram como objectivo melhorar a qualidade de vida da população, diminuir o tempo e custos associados ao transporte e distribuição, quer de pessoas quer de mercadorias. Para que esta qualidade exista é necessário criar condições para tal, e assim é essencial optimizar as rotas dos veículos e a disposição das cargas transportadas. É nesta área que o presente trabalho se enquadra e de forma a contextualizar o problema e perceber o trabalho realizado na área até ao momento, é apresentado um resumo dos vários estudos desenvolvidos na área num capítulo de revisão de literatura. A realização desta dissertação foi constituída por duas fases distintas. Uma primeira fase de pesquisa de aplicações internacionais e nacionais que permitem optimizar rotas, na qual para as aplicações internacionais só foram analisadas aquelas que consideram restrições dos produtos transportados como o peso, altura, comprimento, largura e volume. Na análise das aplicações são descritas as suas funcionalidades e os principais clientes. Adicionalmente, e caso as aplicações tenham um módulo que trata do carregamento dos veículos, é feita a sua descrição. No fim dessa fase, é apresentada uma análise crítica das aplicações e uma tabela de síntese onde são apresentadas as suas principais características. O objectivo da segunda fase foi desenvolver e testar várias abordagens heurísticas para o problema de encaminhamento de veículos com restrições de carga a duas dimensões (2L-CVRP). Os testes de desempenho dessas heurísticas foram realizados sobre as mesmas instâncias usadas no trabalho desenvolvido por Iori (Iori, Salazar-Gonzalez, & Vigo, 2007) na qual garante resultados óptimos recorrendo a um algoritmo exacto. O problema em estudo é caracterizado por um depósito central onde estão colocados diversos veículos que têm a função de transportar encomendas efectuadas por clientes. O objectivo é minimizar tanto a distância total percorrida pelos veículos assim como o número de veículos utilizados. No final, temos uma série de veículos, em que cada um tem uma rota ordenada de clientes. Comparando os resultados das heurísticas com o algoritmo exacto, é natural que os resultados das heurísticas sejam piores no que diz respeito ao número de veículos utilizados e às distâncias percorridas. Contudo, a motivação esteve em tentar aproximar-se da qualidade dos resultados do algoritmo exacto em tempos computacionais bem menores. Nos três algoritmos desenvolvidos foram identificadas três zonas críticas, as estratégias de selecção dos clientes, a estratégia de colocação de itens nos veículos e a estratégia para controlar a distância percorrida – raio de movimentação dos veículos.

In the recent past, there has been a continuous improvement of transport conditions. The infrastructures built, from roads to railways lines, were aimed to improve the population life quality, decrease the time and costs associated to the transport and distribution of people and goods. For this quality to exist, it is necessary to create conditions for that, and so it is essential to optimise the vehicle routing and the arrangement of the cargoes. This is the context of the current work and in order to understand what was done, a summary of several studies is presented in a state of art chapter. The development of this dissertation was composed by two distinct phases. An initial research phase of international and national software that allows routing optimization was made and, in the case of international software, we only analysed those who consider cargoes restrictions like, weight, height, length, width and volume. In the software analysis are described their main features and major customers and, if they have a module that deals with the vehicle loading, its description is made. At the end of this phase, a critical analysis and a summary table with the software main features are presented. The aim of the second stage was to develop and test heuristic approaches to the vehicle routing problem with two-dimensional loading constraints (2L-CVRP). Performance tests on this heuristics were performed on the same instances presented in Iori´s work (Iori, Salazar-Gonzalez, & Vigo, 2007), in which an exact algorithm was used to ensure optimal results. The problem features a central depot, where various vehicles are placed and each has the function of transporting orders placed by customers. The main objective is to minimize the total travelled distance and the number of vehicles used. In the end, we have a set of vehicles, in which, each has an ordered rout of clients. Following this approach and to provide a basis for comparison, three constructive heuristics were developed in order to have access to a range of different outcomes and so, in addition of being compared with the exact algorithm, the developed algorithms can be compared between them. The items that are used for analysis are, the number of vehicles used in an instance, the total distance travelled and the runtime. When compared with the exact algorithm, it is natural that the heuristics present worse results in terms of number of vehicles used and total distance travelled. However, the motivation was to try to approach the quality of the results presented by the exact algorithm, in less time. In the three algorithms developed, we identified three critical areas, the customers selection strategy, the placement of items in vehicles strategy and the control of distance strategy - radius of movement by vehicles between clients.