{pt=Construção de uma Metaheurística de Optimização de Rotas de Veículos: Aplicação na Indústria de Distribuição} {pt=Aplicação na Indústria de Distribuição} EVALUATED

Detalhes: {pt=Nesta dissertação é apresentada uma aplicação de um problema de estabelecimento de rotas de veículos a um caso real de uma empresa de distribuição. Pretende-se utilizar um método aproximado de optimização combinatória baseado numa heurística orientada por um conjunto de regras hierarquicamente superior ? uma metaheurística ? para obtenção de resultados práticos e posterior comparação com o planeamento real utilizado no dia-a-dia da empresa. A variante do problema é designada na literatura por Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (HFVRPTWSD). O objectivo é, tendo em conta as restrições do problema, elaborar um conjunto de rotas que minimize a distância percorrida, o número de veículos utilizados e o tempo de viagem necessários para satisfazer os pedidos de todos os clientes para o horizonte temporal estabelecido. Entre estas, destacam-se as restrições de capacidade e acessibilidade da frota heterogénea de veículos e a calendarização das visitas aos clientes segundo janelas temporais de entrega. Sempre que isso causar uma melhoria na qualidade da solução obtida permite-se a divisão de carga, o que constitui uma relaxação do problema original. Além da comparação com o planeamento real, são comparados os resultados com os obtidos por um método de resolução exacto aplicado a um sub-problema de dimensão menor, permitindo assim medir o desvio relativo da função objectivo face à solução óptima para posteriormente se aplicar o algoritmo implementado ao problema na sua generalidade. , en=In this paper, it is evaluated a vehicle routing problem model applied to a real case of a distribution company. A combinatorial optimization method was implemented based on a rule-guided heuristic ? a metaheuristic ? in order to obtain practical results and to compare them with the real plan used daily by the company. The problem?s extension is referred in the literature as Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (HFVRPTWSD). The objective is to minimize the total travelled distance, the necessary number of vehicles and the sum of travel time through the establishment of a set of routes between all clients and a central depot for the time horizon. The main purpose is to satisfy all clients? requests while complying with a visit schedule. A number of constraints define the problem working environment, with special attention to time windows constraints, truck capacity and accessibility constraints. A relaxation of the original problem ? split delivery ? is allowed whenever it improves the solution. The output provided by an implementation of a VRP-solving algorithm will be compared with the results obtained from an exact method applied to a smaller part of the problem. After comparison with the global optimum, we may capture the algorithm?s power and therefore apply it to the overall problem. }

Discussão: dezembro 11, 2009, 10:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

AUTOR

André Filipe Maio Guerreiro (ist153316)

ORIENTADOR

Susana Isabel Carvalho Relvas

Departamento de Engenharia e Gestão (DEG)

Professor Auxiliar