A carregar...
Publicação
Otimização de rotas com procuras nos arcos : uma heurística
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 1.53 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Trata-se do estudo de um problema de otimização de rotas nos arcos definido num
grafo misto. As ligações podem ser tarefas, caso em que requerem serviço, ou
apenas constar para assegurar a definição das rotas. Cada ligação tem associado
um custo em vazio e, se for tarefa, um custo de serviço e procura. O serviço é
efetuado por uma frota homogénea de veículos com uma dada capacidade.
Pretende-se determinar um conjunto de rotas, a iniciar e terminar no depósito,
compatíveis com a capacidade dos veículos, que assegurem a execução de todas as
tarefas com um custo total mínimo. O problema, conhecido pela designação de
MCARP (Mixed Capacitated Arc Routing Problem), é comprovadamente NP-difícil.
Uma aplicação prática deste problema é a recolha de resíduos sólidos urbanos. A
motivação para este trabalho surgiu no âmbito da otimização de rotas para a
recolha de resíduos sólidos urbanos no Município do Seixal.
Com o objetivo de determinar soluções admissíveis, apresenta-se uma
matheurística em que se alia a resolução de dois modelos compactos a regras
heurísticas para a fixação de serviços. Esta pode ser decomposta em três fases: (I)
resolução do modelo agregado; (II) afetação de serviços a veículos; (III) resolução
do modelo válido no problema de menor dimensão resultante de (II).
O desempenho da matheurística foi avaliado com um conjunto de instâncias
habitualmente utilizado para testar heurísticas para o MCARP. Os resultados não
foram os mais animadores, pois as instâncias de maior dimensão que simulam
casos reais permanecem com um tempo computacional elevado.
This project is regarding a study of a routes optimization problem in the arcs of a mixed graph. The connections may be tasks, in which case require service, or just to be included to ensure the definition of the routes. Each link has an associated deadheaded cost, and, if it is a task, it has a service cost and a demand. The service is performed by a homogeneous fleet of vehicles with a given capacity. It is intended to determine a set of routes, starting and ending in the depot, consistent with the capacity of the vehicles that perform all tasks at a minimum total cost. The problem, known by the designation of MCARP (Mixed Capacitated Arc Routing Problem), is proven to be NP-hard. A practical application of this problem is the collection of household solid waste. The motivation for this dissertation is the route optimization for the collection of solid waste in the Seixal Municipality. In order to determine feasible solutions, a matheuristic is presented in which we combine the resolution of two compact models with heuristic rules for services setting. This method can be decomposed into three stages: (I) resolution of the aggregate model; (II) allocation of services to vehicles, (III) resolution of the valid model in the problem of smallest dimension resulting from (II). The matheuristic performance was evaluated with a set of instances normally used to test MCARP heuristics. The results on the larger instances, that simulate real cases, remain with a high computational time.
This project is regarding a study of a routes optimization problem in the arcs of a mixed graph. The connections may be tasks, in which case require service, or just to be included to ensure the definition of the routes. Each link has an associated deadheaded cost, and, if it is a task, it has a service cost and a demand. The service is performed by a homogeneous fleet of vehicles with a given capacity. It is intended to determine a set of routes, starting and ending in the depot, consistent with the capacity of the vehicles that perform all tasks at a minimum total cost. The problem, known by the designation of MCARP (Mixed Capacitated Arc Routing Problem), is proven to be NP-hard. A practical application of this problem is the collection of household solid waste. The motivation for this dissertation is the route optimization for the collection of solid waste in the Seixal Municipality. In order to determine feasible solutions, a matheuristic is presented in which we combine the resolution of two compact models with heuristic rules for services setting. This method can be decomposed into three stages: (I) resolution of the aggregate model; (II) allocation of services to vehicles, (III) resolution of the valid model in the problem of smallest dimension resulting from (II). The matheuristic performance was evaluated with a set of instances normally used to test MCARP heuristics. The results on the larger instances, that simulate real cases, remain with a high computational time.
Descrição
Mestrado em Decisão Económica e Empresarial
Palavras-chave
matheurística heurística MCARP matheuristic heuristic
Contexto Educativo
Citação
Martins, Karine André (2013). "Otimização de rotas com procuras nos arcos : uma heurística". Dissertação de Mestrado, Universidade de Lisboa. Instituto Superior de Economia e Gestão.
Editora
Instituto Superior de Economia e Gestão