Planeamento e otimização de rotas para veículos

Abstract

A presente dissertação teve como propósito o desenvolvimento de um modelo matemático de Programação Linear Inteira Mista, para determinar um conjunto de rotas para veículos considerando janelas temporais e entregas e recolhas, a implementar numa empresa portuguesa da indústria automóvel, Toyota Caetano Portugal. Do conjunto de fornecedores desta empresa existe uma minoria cujo fluxo de material é realizado em ambos os sentidos. Dado o reduzido número de fornecedores em questão é possível desenvolver um modelo matemático para obtenção de uma solução exata, apesar da complexidade deste. Para tal, implementou-se o modelo matemático no software IBM ILOG CPLEX, para obtenção de uma solução dentro de um tempo computacional reduzido. Após o estudo de caso da empresa e revisão da literatura, foi possível constatar que poderia ser interpretado como um problema de rotas para veículos com janelas temporais, entregas e recolhas e restrição máxima da capacidade do veículo. O modelo matemático e sua implementação no software são apresentados e explicados, assim como a solução obtida. A dissertação finaliza com a realização de uma análise de sensibilidade ao modelo matemático.

This thesis purpose was the development of a mathematical model of mixed integer programming, to determine a set of vehicle routes, with time windows and pickup & delivery, that would be implemented in a Portuguese automotive company, Toyota Caetano Portugal. In the set of this company’s suppliers there is a minority in which the flux of material is carried out in both ways. Given the reduced number of suppliers in question, it is possible to develop a mathematic model to obtain an exact solution, despite its complexity. In order to do that, the mathematical model was implemented on software IBM ILOG CPLEX, to obtain a solution within a reduced computational time. After the company’s case study and literature review, it was possible to verify that it could be interpreted as a vehicle routing problem with time windows, pickups and deliveries and the constraint of the vehicle’s maximum capacity. The mathematical model and its implementation on the software are presented, as well as the obtained solution. The thesis ends with the sensivity analisys of the mathematical model.