| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 725.43 KB | Adobe PDF |
Authors
Abstract(s)
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.
The problem of determining routes for vessels in fisheries research, called the Ship Routing Optimization Problem (SROP), has not been much studied and explored. The set of fishing stations to be visited, the number of circuits to establish and the maximum number of days that each circuit should last are known, as well as the time windows associated with station visits which determine the visiting hours for each day and the windows associated with visits to the seaports assuring a predefined periodicity. Each circuit must start and end at the home seaport. Given the geographical locations of the fishing stations and seaports, the objective is to minimize the total traveled distance and the total duration of each circuit, ensuring that all stations are visited and time windows constraints are satisfied. In this dissertation, three mixed integer linear programming mathematical models are presented for the problem. Furthermore, heuristics that aim to obtain feasible integer solutions using the proposed models and a generic solver are suggested . It is intended to compare the three models in what concerns the quality of the lower bounds for the optimal value provided by partial or total linear programming relaxations and the computational time spent to obtain them. By using the heuristics, it is intended to obtain feasible solutions that provide upper bounds for all instances. The instances used are based in the campaigns realized by IPMA (Portuguese Sea and Atmosphere Institute) to estimate the abundance and observe the geographical distribution of several demersal fish species from the Portuguese continental coast and instances available in literature for the Traveling Salesman Problem with Hotel Selection. The results obtained confirm the complexity of the problem and the difficulty to solve it using a generic solver. There have been instances for which it was not possible to obtain a feasible solution.
The problem of determining routes for vessels in fisheries research, called the Ship Routing Optimization Problem (SROP), has not been much studied and explored. The set of fishing stations to be visited, the number of circuits to establish and the maximum number of days that each circuit should last are known, as well as the time windows associated with station visits which determine the visiting hours for each day and the windows associated with visits to the seaports assuring a predefined periodicity. Each circuit must start and end at the home seaport. Given the geographical locations of the fishing stations and seaports, the objective is to minimize the total traveled distance and the total duration of each circuit, ensuring that all stations are visited and time windows constraints are satisfied. In this dissertation, three mixed integer linear programming mathematical models are presented for the problem. Furthermore, heuristics that aim to obtain feasible integer solutions using the proposed models and a generic solver are suggested . It is intended to compare the three models in what concerns the quality of the lower bounds for the optimal value provided by partial or total linear programming relaxations and the computational time spent to obtain them. By using the heuristics, it is intended to obtain feasible solutions that provide upper bounds for all instances. The instances used are based in the campaigns realized by IPMA (Portuguese Sea and Atmosphere Institute) to estimate the abundance and observe the geographical distribution of several demersal fish species from the Portuguese continental coast and instances available in literature for the Traveling Salesman Problem with Hotel Selection. The results obtained confirm the complexity of the problem and the difficulty to solve it using a generic solver. There have been instances for which it was not possible to obtain a feasible solution.
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
Otimização de rotas de navios Programação Linear Inteira Mista (PLIM), Heurísticas Teses de mestrado - 2018