Otimização de rotas com procuras nos arcos : uma heurística

Mestrado em Decisão Económica e EmpresarialTrata-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