| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 3.06 MB | Adobe PDF |
Authors
Abstract(s)
Dado um período de planeamento de alguns dias e um conjunto de clientes que devem ser visitados em um ou mais dias no respectivo período, o Problema do Caixeiro Viajante Periódico (PTSP) consiste em determinar uma rota para cada dia, com início e fim num determinado depósito, garantindo que todos os clientes são visitados o número de vezes requeridas. Conhecendo os custos de deslocação entre cada par de clientes e entre cada cliente e o depósito e, sabendo quantas visitas devem ser realizadas a cada cliente, sendo que um cliente só pode ser visitado uma vez por dia, pretende-se que as rotas minimizem o custo total. O PTSP é uma variante do clássico Problema do Caixeiro Viajante (TSP), onde a este é associado o período de planeamento. Caso o período tenha apenas um dia e todos os clientes tenham que ser visitados uma vez, o PTSP reduz-se ao TSP e, portanto, também pertence à classe de problemas NP-difícil, sendo um problema de resolução exata difícil. No problema considerado todas as combinações de dias possíveis para as visitas dos clientes são admissíveis, mas nesta dissertação será também considerada uma variante do problema. Esta consiste em que as visitas de alguns clientes sigam uma determinada política de visitas, fazendo com que o número de combinações de visitas aceites para o cliente, diminuam. Nesta dissertação foram desenvolvidos quatro modelos: três modelos para o PTSP e um modelo para o PTSP relaxado. Destes modelos dois foram baseados no Modelo de Fluxo Agregado (MFA) e os outros dois baseados no Modelo de Fluxo Desagregado(MFD). Pretende-se comparar os modelos em termos de eficiência na obtenção de soluções ótimas bem como na qualidade da respectiva relaxação linear. Para comparar os modelos foram utilizadas tanto instâncias retiradas da literatura como novas instâncias geradas aleatoriamente, com um número de clientes a variar entre 20 e 47. Na experiência computacional consideraram-se matrizes de custos assimétricas e simétricas e variados padrões de visitas. Foram realizados testes para os períodos de dois, três e quatro dias. No caso da variante do problema, consideraram-se também diversas distribuições para as regras de visitas e resolveu-se a mesma, para os períodos de planeamento de três e quatro dias.
Description
Tese de mestrado em Estatística e Investigação Operacional, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, em 2018
Keywords
Problema do Caixeiro Viajante Periódico Modelos exatos Relaxação linear Matrizes assimétricas e simétricas Teses de mestrado - 2018