Optimização de rotas de veículos - um caso de estudo

Abstract

Nesta tese estudamos o problema da determinação de rotas de veículos, vehicle routing problem (VRP). Apresentamos um breve estudo do problema e efectuamos uma descrição de alguns dos problemas que são extensão deste. Depois apresentamos modelos em programação linear inteira mista para o problema da optimização de rotas. Apresentamos dois modelos que consideram a distribuição de apenas um produto e dois modelos que consideram a existência de vários produtos para distribuir. Efectuamos um estudo computacional do problema. Finalmente apresentamos como caso de estudo o exemplo da optimização das rotas actualmente efectuadas por uma empresa onde a distribuição dos seus produtos representa uma parte importante dos seus custos. Analisamos os custos das rotas actualmente praticados e, usando os modelos em programação linear inteira mista apresentados, optimizamos essas rotas para as quais obtemos significativas melhorias.

In this thesis we study the vehicle routing problem (VRP). We present a brief study of the vehicle routing problem and describe some of the problem extensions. Then we present mixed integer linear programming models to the vehicle routing problem. We present two models that consider the distribution of a single product and two models that consider the distribution of several products. A computational study of the problem is done. Finally, we present a case study for the optimization of the routes currently undertaken by a company where the distribution of its products represents an important part of their costs. We analyze the costs of the routes currently practiced and using the models in mixed integer linear programming presented we optimize those routes for which significant improvements are obtained.