Simulated annealing aplicado a um problema de roteamento real do tipo vehicle routing problem with time windows

O tema desta dissertação consiste em desenvolver um modelo matemático de otimização e analisar o seu impacto num problema real aplicado a rotas de camiões. Quanto à metodologia adotada, recolheu-se os dados disponibilizados pela empresa Metalogalva no sentido de apurar da maneira mais eficaz os valores reais para conseguir obter resultados expressivos. Após levantamento dos dados é necessário incorporar as diversas variáveis que compõem o problema real em análise. Isto é, o número de clientes, sua localização, custo de transporte e as janelas temporais afetas aos clientes. De modo a proceder a este estudo, foi adotada uma formulação matemática onde foram definidos todos os parâmetros que englobam um VRPTW (Vehicle Routing Problem with Time Windows). O problema foi formulado para ser usado como um programa MIP (Mixed integer programming). Foi concluído que a utilização de este modelo traz grandes vantagens à empresa, diminuindo o custo de transporte em 35% tendo em conta a média atual da empresa caso de estudo. Ainda, pode ajudar a empresa a tomar uma decisão no futuro para a implementação de um software para gestão e otimização de rotas.The subject of this dissertation consists in developing a mathematical optimisation model and analysing its impact on a real problem applied to truck routing. For the methodology adopted, it was retrieved the data put available by the company Metalogalva so that the data correspond to the reality and so that the result shave the best reliability. In order to carry out this study and after surveying the problem it is necessary to incorporate the various variables that make up the real problem under analysis. That is, the number of customers, their location, transport costs and the time windows allocated to customers. In order to proceed with this study, a mathematical formulation was adopted in which all the parameters that comprise a VRPTW (Vehicle Routing Problem with Time Windows) were defined. The problem was formulated to be used as a MIP (Mixed integer programming) program. It was concluded that the use of this model brings great advantages to the company, decreasing the transport cost by 35% considering the current average of the case study company. Still, it can help the company to make a decision in the future to implement a software for route management and optimisation