Dissertação

{pt_PT=Site-Dependent Vehicle Routing Problem with Hard Time Windows} {} EVALUATED

{pt=Esta tese resolve uma variante do problema clássico "Vehicle Routing Problem (VRP)", que surgiu de um problema real específico, ainda não resolvido, proposto pela empresa Worten. O problema foi formulado matematicamente e analisado para ser otimizado. O problema pode ser classificado como "Site-Dependent Vehicle Routing Problem With Hard Time Windows (SDVRTHTW)", e precisa de ser resolvido diariamente em duas ou três horas. Para resolver essa variante, foram propostos, testados e modificados dois algoritmos diferentes: a Pesquisa Local e um Algoritmo Genético Híbrido com a Pesquisa Local. Uma adaptação das técnicas de Clarke and Wright Heuristic foi usada para inicializar os algoritmos de pesquisa local e híbrido. O objetivo é encontrar a melhor combinação de rotas que permita reduzir os custo, servindo todos os clientes da empresa sempre garantido que as restrições do problema real, como as restrições rodoviárias da UE, não sejam violadas.Os algoritmos foram testados e implementados em três semanas diferentes do ano em que as quantidades dos diferentes clientes da Worten são baseadas em previsões e onde algumas rotas são sugeridas e analisadas pela empresa trasportadora sendo possível fazer uma comparação entre as rotas feitas pela empresa e as rotas feitas pelos algoritmos propostos. Ambos os algoritmos apresentam melhores resultados do que o conjunto de rotas proposto pela empresa, o que sugere que o uso de algoritmos de planejamento de rotas para o problema da Worten diminui substancialmente os custos de entrega sem violar os constrangimentos., en=This thesis solves a variant of the classic Vehicle Routing Problem (VRP), a variant which emerged from a specific and not yet solved real-world problem proposed by the company Worten. This problem has been analyzed and formulated mathematically so that it can be optimized. The problem can be calledSite-Dependent Vehicle Routing With Hard Time Windows (SDVRPHTW), and needs to be solved in two or three hours every day. In order to solve this variant two different algorithms were proposed, tested and modified: a Local Search and a Hybrid Genetic algorithm with Local Search. An adaptation of the Clarke and Wright Heuristic was used to start both the Local Search and the Hybrid Algorithms.The goal is to find the best combination of routes that allows to spend the least amount of money to supply all the customers of the company, whilst always guaranteeing that the restrictions of the real problem, such as the EU road restrictions, are not violated. The algorithms were tested and implemented in three different weeks of the year where the demands of the different customers of Worten are forecast and where some routes are suggested and analyzed by the shipping company in order to make a comparison between the routes made by the company and the ones given by the algorithms.Both algorithms give better results than the set of routes proposed by the company. This suggests that the use of route planning algorithms for the Worten problem substantially decreases delivery costs without violating the constraints.}
{pt=Problema De Roteamento De Veículos, Local Dependente, Janela Temporal Fixa, Algoritmo Genetico, Pesquisa Local, en=Vehicles Routing Problem, Hard Time Window, Site Depended, Genetic Algorithm, Local Search}

Novembro 27, 2019, 9:0

Orientação

ORIENTADOR

Susana Margarida da Silva Vieira

Departamento de Engenharia Mecânica (DEM)

Professor Auxiliar

ORIENTADOR

Joaquim Paul Laurens Viegas

Departamento de Engenharia Mecânica (DEM)

Professor Auxiliar Convidado