A carregar...
Publicação
Meta-heurísticas para o problema do carteiro rural orientado com lucros e incompatibilidades
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 585.07 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
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.
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.
Descrição
Mestrado Bolonha em Métodos Quantitativos para a Decisão Económica e Empresarial
Palavras-chave
Problema do Carteiro Rural Orientado incompatibilidades arcos lucrativos Tabu Search pesquisa local Directed Rural Postman Problem Incompatibilities Profitable arcs Tabu Search Local Search.
Contexto Educativo
Citação
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
Editora
Instituto Superior de Economia e Gestão