A carregar...
Publicação
Pesquisa Tabu aplicada a um problema de rotas na Galp
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 8.03 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Hoje, como sempre, as empresas procuram estratégias para otimizar os seus recursos, em
particular na área da logística existem muitas oportunidades para colocar em prática
estas ideias. O foco deste trabalho incide na área da distribuição, mais concretamente na
criação de rotas.
Este desafio foi proposto pela Galp e enquadra-se no projeto de otimização da distribuição
secundária de combustíveis. Este trabalho consiste no desenvolvimento de um
algoritmo eficiente para determinar as rotas diárias de distribuição de combustíveis de
acordo com a necessidade dos clientes.
A Galp sentiu a necessidade de alterar o seu sistema de criação de rotas uma vez que
a partir da publicação do Decreto-Lei n.º 132/2017 os veículos pesados passam a poder
transportar mercadorias até 44 toneladas em vez de 40, neste caso, significa que podem
ser utilizadas cisternas de 36 m3 em vez de 33 m3. Outra alteração recente é relativa à
localização dos clientes, uma vez que foi realizado um levantamento das coordenadas
geográficas de cada um, o que significa que se passou a ter acesso à localização exata dos
mesmos, isso permite determinar com maior exatidão as distâncias de transporte.
O objetivo deste trabalho é criar um conjunto de rotas que minimize a distância total
percorrida e que respeite as restrições do problema, sendo elas a capacidade dos veículos,
a janela temporal dos clientes, o horário dos motoristas e as condições de cada tipo de
cliente. Para a determinação das rotas será utilizada uma metaheurística, a pesquisa tabu,
uma vez que é um método que produz boas soluções e é computacionalmente eficiente.
Para averiguar a qualidade das rotas obtidas pelo algoritmo estas serão comparadas com
as rotas realizadas pela Galp no período em estudo.
Today, as always, companies are looking for strategies to optimise their resources, particularly in the area of logistics there are many opportunities to put these ideas into practice. The focus of this work is in the area of distribution, more specifically, vehicle routing problem. This challenge was proposed by Galp and is part of the secondary fuel distribution optimization project. This work consists of the development of an efficient algorithm to determine the daily fuel distribution routes according to the customers’ needs. Galp felt the need to change its route creation system from the publication of Decree- Law no. 132/2017 heavy vehicles can now transport goods up to 44 tonnes instead of 40, in this case, it means that 36 m3 tanks can be used instead of 33 m3. Another recent change is regarding to the location of the customers, as a survey was carried out of the geographic coordinates of each one, which means that we now have access to their exact location, this allows us to determine more accurately the transport distances. The objective of this work is to create a set of routes that minimizes the total distance and that respects the constraints of the problem, which are the capacity of the vehicles, the time window of the customers, the drivers’ schedule and the conditions of each type of customer. The determination of the routes will be done with a metaheuristic, the tabu search, since it is a method that produces good solutions and is computationally efficient. To ascertain the quality of the routes obtained by the algorithm, these will be compared with the routes taken by Galp during the study period.
Today, as always, companies are looking for strategies to optimise their resources, particularly in the area of logistics there are many opportunities to put these ideas into practice. The focus of this work is in the area of distribution, more specifically, vehicle routing problem. This challenge was proposed by Galp and is part of the secondary fuel distribution optimization project. This work consists of the development of an efficient algorithm to determine the daily fuel distribution routes according to the customers’ needs. Galp felt the need to change its route creation system from the publication of Decree- Law no. 132/2017 heavy vehicles can now transport goods up to 44 tonnes instead of 40, in this case, it means that 36 m3 tanks can be used instead of 33 m3. Another recent change is regarding to the location of the customers, as a survey was carried out of the geographic coordinates of each one, which means that we now have access to their exact location, this allows us to determine more accurately the transport distances. The objective of this work is to create a set of routes that minimizes the total distance and that respects the constraints of the problem, which are the capacity of the vehicles, the time window of the customers, the drivers’ schedule and the conditions of each type of customer. The determination of the routes will be done with a metaheuristic, the tabu search, since it is a method that produces good solutions and is computationally efficient. To ascertain the quality of the routes obtained by the algorithm, these will be compared with the routes taken by Galp during the study period.
Descrição
Palavras-chave
Criação de rotas Heurísticas Pesquisa tabu