Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/1252
Título: Sectorização de redes em problemas com procura nos arcos e limitações de capacidade
Autor: Nunes, Ana Catarina de Carvalho
Orientador: Mourão, Maria Cândida
Palavras-chave: 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
Data de Defesa: Mai-2009
Editora: Instituto Superior de Economia e Gestão
Citação: Nunes, Ana Catarina de Carvalho. 2009. "Sectorização de redes em problemas com procura nos arcos e limitações de capacidade". Tese de Doutoramento. Universidade Técnica de Lisboa. Instituto Superior de Economia e Gestão
Resumo: 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.
Descrição: Doutoramento em Matemática Aplicada à Economia e à Gestão
URI: http://hdl.handle.net/10400.5/1252
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
PhDThesis_AnaCatarinaNunes.pdf1,25 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.