Dissertação

{en_GB=Dynamic Delivery Services for Smart Cities. Solving a Constrained Pickup Delivery Vehicle Routing Problem with Time Windows on a Dynamic Environment} {} EVALUATED

{pt=Nesta tese é proposto um modelo para serviço de estafetas capaz de lidar com o escalonamento de uma frota de veículos. Mais especificamente, é formulado um Capacitated Pickup Delivery Vehicle Routing Problem with Time Windows on a Dynamic Environment. Este problema surge de um caso do mundo real existente na companhia Urban Dynamic Delivery, que executa escalonamento e planeamento para serviços de estafeta. Em vez de se encontrar a solução óptima, independentemente do tempo computacional necessário, procura-se uma boa solução num pequeno intervalo de tempo. Um novo método emparelhando Nearest Neighbourhood Search com Subtractive Clustering é proposto para melhorar as soluções iniciais e acelerar a convergência do algoritmo de optimização. Além disso, um método híbrido combinando Ant Colony Optimization com Local Search é proposto para modelar este problema. Primeiro, um modelo foi desenvolvido para resolver um dado caso estático. Depois, é proposta uma estrutura para coordenar quaisquer mudanças dinâmicas ao longo do tempo. A validação é feita usando referências de 100 clientes para o problema de direccionamento de veículos para recolhas e entregas. Visto que não existem referências para a abordagem dinâmica, estes foram gerados com base nas referências estáticas. O algoritmo de optimização proposto é aplicado ao caso de estudo, que contém pedidos reais de clientes. Foi deduzido um modelo funcional para o problema abordado que apresenta bons resultados para o ambiente dinâmico e é adequado a ser aplicado no contexto do mundo real., en=In this thesis, it is proposed a model for courier services capable of handling the routing of a fleet of vehicles. More specifically, a Capacitated Pickup Delivery Vehicle Routing Problem with Time Windows on a Dynamic Environment is formulated. This problem emerged from a real-world problem existent in the company Urban Dynamic Delivery, which performs scheduling and planning for courier services. A good solution must be found in a small time window, instead of finding the optimal solution independently of the required computational time. A new method pairing Nearest Neighbourhood Search with Subtractive Clustering is proposed to improve initial solutions and to accelerate the convergence of the optimization algorithm. Further, a hybrid method combining Ant Colony Optimization with Local Search is proposed to model this problem. First, a model was developed to solve a given static instance. Then, a framework to coordinate any dynamic changes on the inputs over time is proposed. Validation is made using static benchmarks of 100 customers for the pickup delivery vehicle routing problem. Since no benchmarks exist for the dynamic approach, these were generated based on the static benchmarks. The proposed optimization algorithm to solve Constrained Pickup Delivery Vehicle Routing Problem with Time Windows on a Dynamic Environment is applied to the case study, which contains real customer requests. A functional model for the tackled problem was derived that presents good results for the dynamic environment and is suitable to be applied to the real-world scenario.}
{pt=problema de recolhas e entregas, optimização de colónia de formigas, pesquisa local, janelas de tempo, pedidos dinâmicos, en=pickup delivery problem, ant colony optimization, local search, time windows, dynamic requests}

novembro 17, 2017, 9:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

João Miguel Da Costa Sousa

Departamento de Engenharia Mecânica (DEM)

Professor Catedrático

ORIENTADOR

Susana Margarida da Silva Vieira

Departamento de Engenharia Mecânica (DEM)

Prof Auxiliar Convidado