Untitled

Funder

Organizational Unit

Publications

Determinação de rotas para um navio de investigação utilizado em campanhas de pesca

Publication . Brito, Katlene Aline Fortes; Paias, Ana Maria Duarte Silva Alves,1963-; Oliveira, Marta Guerreiro Duarte Mesquita de,1961-

O problema de determinação de rotas para navios de investigação para campanhas de pesca, designado como Ship Routing Optimization Problem (SROP), é um problema que até agora não foi muito estudado e explorado. No problema são conhecidos o conjunto de estações de pesca a ser visitadas, o número de circuitos a determinar e o número de dias que no máximo deve durar cada circuito. Também são conhecidas as janelas temporais associadas às visitas às estações que determinam as horas de visita para cada dia e as janelas temporais associadas às visitas aos portos, que garantem que estes sejam visitados com a periodicidade previamente definida. Cada circuito deve começar e terminar no porto origem. Dadas as localizações geográficas das estações de pesca e dos portos, o objetivo do problema é minimizar a distância total percorrida e a duração total de cada circuito, garantindo que todas as estações são visitadas e respeitando as restrições das janelas temporais. Nesta dissertação, apresentam-se três modelos matemáticos em programação linear inteira mista (PLIM) para resolver o problema. Para além dos modelos, sugerem-se também heurísticas que têm como objetivo obter soluções inteiras admissíveis utilizando os modelos propostos e um solver genérico. Pretende-se comparar as três formulações a nível da qualidade dos limites inferiores para o valor ótimo, fornecidos por relaxações lineares totais e parciais e do tempo computacional gasto para obter os mesmos. Através das heurísticas pretende-se obter soluções admissíveis para todas as instâncias e os limites superiores para o valor ótimo associados aos respetivos valores. As instâncias utilizadas são baseadas em campanhas realizadas pelo IPMA (Instituto Português do Mar e da Atmosfera) para estimar a abundância e observar a distribuição geográfica de várias espécies marinhas da costa portuguesa e instâncias disponibilizadas na literatura para o Problema do Caixeiro Viajante com Seleção de Hotéis. Os resultados obtidos confirmam a complexidade do problema e a dificuldade em resolve-lo usando um solver genérico, tendo existido instâncias para as quais não foi possível encontrar uma solução admissível.

2018Master thesis

Open access

The family traveling salesman problem

Publication . Bernardino, Raquel; Paias, Ana Maria Duarte Silva Alves

Consider a depot, a partition of the set of nodes into subsets, called families, and a cost matrix. The objective of the family traveling salesman problem (FTSP) is to find the minimum cost circuit that starts and ends at the depot and visits a given number of nodes per family. The FTSP was motivated by the order picking problem in warehouses where products of the same type are stored in different places and it is a recent problem. Nevertheless, the FTSP is an extension of well-known problems, such as the traveling salesman problem. Since the benchmark instances available are in small number we developed a generator, which given a cost matrix creates an FTSP instance with the same cost matrix. We generated several test instances that are available in a site dedicated to the FTSP. We propose several mixed integer linear programming models for the FTSP. Additionally, we establish a theoretical and a practical comparison between them. Some of the proposed models have exponentially many constraints, therefore we developed a branch-and-cut (B&C) algorithm to solve them. With the B&C algorithm we were able to obtain the optimal value of open benchmark instances and of the majority of the generated instances. As the FTSP is an NP-hard problem we develop three distinct heuristic methods: a genetic algorithm, an iterated local search algorithm and a hybrid algorithm. With all of them we were able to improve the best upper bounds available in the literature for the benchmark instances that still have an unknown optimal value. We created a new variant of the FTSP, called the restricted family traveling salesman problem (RFTSP), in which nodes from the same family must be visited consecutively. We apply to the RFTSP the methods proposed for the FTSP and develop a new formulation based on the interfamily and the intrafamily relationships

2019-04Doctoral thesis

Open access

Modelos para o Problema do Caixeiro Viajante Periódico

Publication . Crespo, Ana Margarida Garcia,; Gouveia, Luís,1957-; Paias, Ana Maria Duarte Silva Alves,1963-

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.

2018Master thesis

Open access