Publicação
Meta-heurísticas para o problema do carteiro rural orientado com lucros e incompatibilidades
| dc.contributor.advisor | Bernardino, Raquel Costa | |
| dc.contributor.author | Ribeiro, Mariana Ferreira | |
| dc.date.accessioned | 2024-01-12T11:10:14Z | |
| dc.date.available | 2024-01-12T11:10:14Z | |
| dc.date.issued | 2024-01 | |
| dc.description | Mestrado Bolonha em Métodos Quantitativos para a Decisão Económica e Empresarial | pt_PT |
| dc.description.abstract | O presente trabalho aborda o Problema do Carteiro Rural Orientado com Lucros e Incompatibilidades (em ingles, Directed Profitable Rural Postman Problema with Incompatibility Constraints, ou seja, DPRPP-IC). Este generaliza o problema do carteiro rural, adicionando arcos lucrativos e incompatibilidades entre pares de nodos. O DPRPP-IC procura uma rota com início e fim no depósito, que maximize a diferença entre as receitas e os custos totais, que são compostos pelos custos de deslocação e penalizações pagas para eliminar incompatibilidades fracas, satisfazendo as restrições de incompatibilidade. O problema apresentado tem aplicação prática para empresas que partilham serviços de distribuição, transporte ou logística. Uma vez que o DPRPP-IC é um caso particular de um problema NP-difícil, é proposto um algoritmo Tabu Search para encontrar soluções de boa qualidade de forma eficiente. Tabu Search é uma meta-heurística de pesquisa local que procura escapar a ótimos locais usando uma lista tabu, que não permite movimentos para soluções recentes. Algumas instâncias de referência da literatura são utilizadas para avaliar a qualidade da meta-heurística proposta. Após uma análise aos parâmetros da meta-heurística e a fixação dos mesmos, os resultados analisados mostram que a meta-heurística proposta obtém soluções de fraca qualidade, mas em tempos computacionais bastante inferiores aos registados na literatura para obtenção da solução ótima por métodos exatos. | pt_PT |
| dc.description.abstract | This work addresses the Directed Profitable Rural Postman Problem with Incompatibility Constraints (DPRPP-IC). This problem generalizes the rural postman problem by adding profitable arcs and incompatibilities between nodes. The DPRPP-IC searches for a route starting and ending at the depot, that maximizes the difference between the collected profit and the total cost, which is comprised of the travelling costs and the penalties paid to remove weak incompatibilities, while satisfying the incompatibility constraints. The DPRPP-IC has practical application in companies that share shipping, transportation, or logistic services. Since the DPRPP-IC is an NP-hard problem, it is proposed a Tabu Search algorithm to find good quality solutions efficiently. The Tabu Search is a local search based metaheuristic that escapes from local optima using a tabu list, which does not allow movements to recent solutions. Some benchmark instances from the literature are used to evaluate the quality of the proposed metaheuristic. After tuning the parameters of the metaheuristic, the results show that the proposed metaheuristic yields solutions of low quality. However, the computational times required to obtain such solutions are significantly lower than those reported in the literature for obtaining the optimal solutions through exact methods. | pt_PT |
| dc.description.version | info:eu-repo/semantics/publishedVersion | pt_PT |
| dc.identifier.citation | Ribeiro, Mariana Ferreira (2024). “Meta-heurísticas para o problema do carteiro rural orientado com lucros e incompatibilidades”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestão | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10400.5/29796 | |
| dc.language.iso | por | pt_PT |
| dc.publisher | Instituto Superior de Economia e Gestão | pt_PT |
| dc.subject | Problema do Carteiro Rural Orientado | pt_PT |
| dc.subject | incompatibilidades | pt_PT |
| dc.subject | arcos lucrativos | pt_PT |
| dc.subject | Tabu Search | pt_PT |
| dc.subject | pesquisa local | pt_PT |
| dc.subject | Directed Rural Postman Problem | pt_PT |
| dc.subject | Incompatibilities | pt_PT |
| dc.subject | Profitable arcs | pt_PT |
| dc.subject | Tabu Search | pt_PT |
| dc.subject | Local Search. | pt_PT |
| dc.title | Meta-heurísticas para o problema do carteiro rural orientado com lucros e incompatibilidades | pt_PT |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | masterThesis | pt_PT |