Planeamento de Rotas para a Distribuição de Combustível em Veículos Multi-compartimentados: uma Abordagem Exata

Abstract

Over the years, the Vehicle Routing Problem (VRP) has been a study target for several authors, creating several extensions for this problem. An example of these extensions is the Multi-Compartment Vehicle Routing Problem (MC-VRP). However, there are few studies in the literature with high scientific recognition about this problem with time-windows and whose resolution is based on exact approaches. In this way, one intends a mathematical model creates for the Multi-compartment Vehicle Routing Problem with Time-windows (MC-VRPTW). In this case, three types of fuels are distributed to a set of clients using a limited homogeneous fleet. For that, it is necessary to determine, for each vehicle, the route to carry out the deliveries, the scheduling in each client is served, and the attribution of products to the compartments. The main objective is to minimize the total distance travelled, which corresponds to the sum of the distances travelled by each one of the necessary vehicles to the delivery’s realization. So, an exact algorithm is presented for the MC-VRP with explicit consideration of time-windows and the inclusion of the calculation of the CO2 emissions. Additional restrictions of the actual application contexts are also considered, such as rest times for the drivers, time limits for each trip and time limits for the work’s schedules, which are not commonly addressed in the literature. To demonstrate the efficiency of the exact approach there are carried out a set of tests that allow analyzing the impact in the different KPI’s, changing the values of some instances. Finally, additional tests are carried out in real instances to evaluate the performance of the model and to compare the results for the distribution time and for the travelled distance with the results using a heuristics approach proposed in the literature.

Ao longo dos anos, o problema do planeamento de rotas tem sido alvo de estudo por diversos autores, criando várias extensões para esse problema. Um exemplo dessas extensões é o problema do planeamento de rotas em veículos multi-compartimentados. No entanto, existem poucos trabalhos na literatura com elevado reconhecimento científico acerca deste problema com janelas temporais e cuja resolução assente em abordagens exatas. Deste modo, pretende-se criar um modelo matemático para o problema do planeamento de rotas para a distribuição de combustível em veículos multi-compartimentados com janelas temporais. Neste caso, são distribuídos três tipos de combustíveis a um conjunto de clientes, utilizando uma frota homogénea limitada de veículos. Para isso, é necessário determinar, para cada veículo, a rota para realizar as entregas, o horário em que cada cliente é servido e a atribuição dos produtos aos compartimentos. O objetivo principal é minimizar a distância total percorrida, que corresponde à soma das distâncias percorridas por cada um dos veículos necessários à realização das entregas.Assim, apresenta-se uma abordagem exata para o problema do planeamento de rotas em veículos multi-compartimentados com consideração explícita de janelas temporais e a inclusão do cálculo de emissões de Dióxido de Carbono (CO2). Consideram-se ainda restrições adicionais dos contextos reais de aplicação tais como tempos de descanso para os condutores, limites de tempo para cada viagem e limites para o horário de trabalho, que não são comummente abordados na literatura. Para demonstrar a eficiência do modelo exato é realizado um conjunto de testes que permitem analisar o impacto nos diferentes KPI’s (Key Performance Indicators), alterando os valores de algumas instâncias. Testes adicionais foram realizados em instâncias reais para avaliar o desempenho do modelo e comparar os resultados obtidos referentes ao tempo de distribuição e à distância percorrida com os resultados utilizando um algoritmo heurístico proposto na literatura.