UTL Repository >
ISEG - Instituto Superior de Economia e Gestão / ISEG - School of Economics & Management Lisbon >
Biblioteca Francisco Pereira de Moura / Francisco Pereira de Moura Library >
BISEG - Teses de Doutoramento / Ph.D. Thesis >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10400.5/1252

Title: Sectorização de redes em problemas com procura nos arcos e limitações de capacidade
Authors: Nunes, Ana Catarina de Carvalho
Advisor: Mourão, Maria Cândida
Keywords: 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
Issue Date: May-2009
Publisher: Instituto Superior de Economia e Gestão
Citation: 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
Abstract: 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.
Description: Doutoramento em Matemática Aplicada à Economia e à Gestão
URI: http://hdl.handle.net/10400.5/1252
Appears in Collections:DM - Teses de Doutoramento / Ph.D. Thesis
BISEG - Teses de Doutoramento / Ph.D. Thesis

Files in This Item:

File Description SizeFormat
PhDThesis_AnaCatarinaNunes.pdf1.25 MBAdobe PDFView/Open
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 
Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE