| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| DM_JoseVeloso_MEI_2014 | 21.93 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
A vasta aplicabilidade dos Problemas de Localização de Instalações em variados cenários
do mundo real (como a escolha da localização de um hospital ou armazém) associada à
complexidade de resolução caraterística destes problemas, atrai grande atenção por parte
da comunidade científica, que procura continuamente novos métodos de resolução, mais
eficazes e eficientes.
O presente trabalho incide naquele que é considerado um dos Problemas de Localização de
Instalações mais estudado: o problema P-Median. Este problema tem por finalidade a
escolha de um conjunto de p instalações (medianas) de entre um conjunto de instalações
candidatas, de modo a minimizar o somatório da distância de cada cliente à respetiva
mediana mais próxima. Uma vez que a resolução deste problema através de métodos
exatos implica recursos computacionais elevados, com alguma naturalidade surgem
abordagens heurísticas, que garantem boas soluções com recursos computacionais
reduzidos.
Neste estudo são apresentados dois novos algoritmos para a resolução do problema PMedian
baseados na metaheurística RAMP (Relaxation Adaptive Memory Programming),
caraterizada pela sua eficiente exploração dos espaços primal e dual de um problema.
Os novos algoritmos propostos, Dual-RAMP e PD-RAMP, produzem resultados de
qualidade que demonstram o sucesso da abordagem RAMP na resolução do problema PMedian.
The wide applicability of Facility Location Problems in various real-world scenarios (such as determining the location of an hospital or a warehouse) associated with the well-known resolution complexity, attracts great attention from the scientific community, that persistently seeks more capable and efficient methods. This work focuses on what is considered one of the most studied Facilitiy Location Problem: the P-Median problem. The goal is to choose the set of p facilities (medians) from a set of candidate facilities, that minimizes the sum of the distance of each customer to the closest respective median. Solving this problem using exact methods implies high computational resources, hence heuristic approaches arise naturally, since they ensure good solutions with reduced computational resources. In this study we present two new algorithms for solving the P-Median problem, based on the metaheuristic RAMP (Relaxation Adaptive Memory Programming), which allows an efficient exploitation of primal and dual spaces of the problem. The new proposed algorithms, Dual-RAMP and PD-RAMP, yield high quality results that demonstrate the success of the RAMP approach for solving the P-Median problem.
The wide applicability of Facility Location Problems in various real-world scenarios (such as determining the location of an hospital or a warehouse) associated with the well-known resolution complexity, attracts great attention from the scientific community, that persistently seeks more capable and efficient methods. This work focuses on what is considered one of the most studied Facilitiy Location Problem: the P-Median problem. The goal is to choose the set of p facilities (medians) from a set of candidate facilities, that minimizes the sum of the distance of each customer to the closest respective median. Solving this problem using exact methods implies high computational resources, hence heuristic approaches arise naturally, since they ensure good solutions with reduced computational resources. In this study we present two new algorithms for solving the P-Median problem, based on the metaheuristic RAMP (Relaxation Adaptive Memory Programming), which allows an efficient exploitation of primal and dual spaces of the problem. The new proposed algorithms, Dual-RAMP and PD-RAMP, yield high quality results that demonstrate the success of the RAMP approach for solving the P-Median problem.
Description
Keywords
Problemas de localização RAMP problema P-Median Metaheurísticas