Author(s):
Nunes, Ana Catarina de Carvalho
Date: 2009
Persistent ID: http://hdl.handle.net/10400.5/1252
Origin: Repositório da UTL
Subject(s): sectorização; problema de rotas com procura nos arcos e restrições de capacidade; grafo misto; formulações; limites inferiores; heurísticas; districting; capacitated arc routing problem; mixed graph; formulations; lower bounds; heuristics
Description
Doutoramento em Matemática Aplicada à Economia e à Gestão
O problema de sectorização e rotas nos arcos (SARP) e definido para modelar as actividades associadas as ruas de zonas urbanas, como sendo o caso da recolha municipal de resíduos sólidos. Com o SARP pretende obter-se uma partição da rede de ruas em sectores e construir um conjunto de viagens em cada sector, minimizando a duração total das viagens. São apresentadas formulações para o SARP, conhecidas por formulações de fluxos por utilizarem variáveis de fluxo. Estas formulações tem a vantagem de impedir a formação de viagens ilegais usando um número polinomial de restrições, em alternativa as habituais restrições de eliminação de subcircuitos, que são em número exponencial. Com base nestas formulações são determinados limites inferiores para o valor óptimo do SARP e, para instancias de baixa dimensão, são obtidas soluções óptimas. São propostas duas heurísticas em duas fases e uma heurística de melhor inserção, com várias versões cada. Nas heurísticas em duas fases, na fase 1 constroem-se os sectores usando duas heurísticas possíveis, enquanto que na fase 2 e resolvido um problema de rotas com procura nos arcos e restrições de capacidade num grafo misto (MCARP) para determinar as viagens em cada sector. A heurística de melhor inserção determina os sectores e as viagens em simultâneo. Para alem do custo da solução, os algoritmos são comparados usando outros critérios de avaliação, tais como o desequilíbrio, o diâmetro e medidas da dispersão. São mostrados e analisados os resultados obtidos para três conjuntos de instâncias, incluindo instâncias de grandes dimensões com ate 401 nodos e 1056 ligacões (arcos ou arestas).
The Sectoring-Arc Routing Problem (SARP) is introduced to model activities associated with the streets of large urban areas, like municipal waste collection. The aim is to partition the street network into a given number of sectors and to build a set of vehicle trips in each sector, to minimize the total duration of the trips. SARP formulations using flow variables, known as flow formulations, are given. One of the advantages of this type of formulation is that it involves a polynomial number of constraints to eliminate illegal trips, instead of the usual subtour elimination constraints, which are in exponential number. From these formulations lower bounds for the SARP are derived and, for small instances, optimal solutions are obtained. Two two-phase heuristics and one best insertion method are proposed. In the two-phase methods, phase 1 constructs the sectors using two possible heuristics, while phase 2 solves a Mixed Capacitated Arc Routing Problem (MCARP) to compute the trips in each sector. The best insertion method determines sectors and trips simultaneously. In addition to solution cost, some evaluation criteria such as imbalance, diameter and dispersion measures are used to compare algorithms. Numerical results on large instances with up to 401 nodes and 1056 links (arcs or edges) are reported and analysed.