Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/5978
Registro completo de metadados
Campo DCValorIdioma
dc.creatorBelotti, Jônatas Trabuco-
dc.date.accessioned2016-12-08T13:03:59Z-
dc.date.available2016-12-08T13:03:59Z-
dc.date.issued2015-11-11-
dc.identifier.citationBELOTTI, Jônatas Trabuco. Modelo de alocação de fluxo em redes para evacuação de população. 2015. 93 f. Trabalho de Conclusão de Curso (Graduação) - Universidade Tecnológica Federal do Paraná, Ponta Grossa, 2015.pt_BR
dc.identifier.urihttp://repositorio.roca.utfpr.edu.br/jspui/handle/1/5978-
dc.description.abstractGiven a directed graph with a vertex representing a source and another one representing a sink, where each edge has a capacity, the Allocation Network Flow Problem consists in allocating flow to the graph edges obeying the following constraints: i) the flow of an edge must not ex-ceed its capacity; and ii) the sum of the flows entering a vertex v must be equal to the sum of the flows exiting the vertex v, except for the source and the sink vertices. The Maximum Flow Problem is a special case of the Allocation Network Flow Problem, where the sum of the flows entering the sink must be maximum. A way to solve the Maximum Flow Problem is using the Ford-Fulkerson Method, which finds the maximum flow in a graph in pseudo-polynomial time. This work presents a study on the problem of determining evacuation routes for a population in risk areas, whose purpose is to transport the population from risk areas to safe places as quickly as possible across roads with limited capacity. As a result, this problem is modelled as an Allo-cation Network Flow Problem. Among the restrictions imposed to the model, the following are considered: the existence of multiple sources and sinks, the entire population must be removed from the risk areas, the existence of a maximum capacity for each safe place with the possibil-ity of the population being greater than these capacities and, finally, there must be no crossing between the evacuation routes to prevent conflict situations. Since the problem of population evacuation imposes a large number of constraints to the Allocation Network Flow Problem, it is relaxed to be solved by the Ford-Fulkerson Method.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectGrafos de ligaçãopt_BR
dc.subjectAlgorítmos computacionaispt_BR
dc.subjectEdifícios - Evacuaçãopt_BR
dc.subjectPreparação para emergênciaspt_BR
dc.subjectBond graphspt_BR
dc.subjectComputer algorithmspt_BR
dc.subjectBuildings - Evacuationpt_BR
dc.subjectEmergency managementpt_BR
dc.titleModelo de alocação de fluxo em redes para evacuação de populaçãopt_BR
dc.typebachelorThesispt_BR
dc.description.resumoDado um grafo orientado com capacidade nas arestas, com um vértice representando uma ori-gem e outro representando um destino, o Problema da Alocação de Fluxo consiste em alocar fluxo nas arestas do grafo obedecendo as seguintes restrições: i) em cada aresta, o fluxo alocado respeita a sua capacidade; e ii) a soma dos fluxos alocados nas arestas que incidem em qualquer vértice v é igual à soma dos fluxos nas arestas que partem de v. O Problema do Fluxo Máximo é o Problema da Alocação de Fluxo, acrescido da restrição de que a soma dos fluxos alocados nas arestas que incidem no vértice de destino é máxima. Uma das maneiras de se resolver esse problema é utilizando o Método de Ford-Fulkerson, que em tempo pseudopolinomial encontra o fluxo máximo em um grafo. Este trabalho apresenta um estudo do Problema de Evacuação de População em Áreas de Risco, cujo objetivo é transportar, no menor tempo possível, a popula- ção presente em áreas de risco para locais seguros, por vias que possuem capacidade limitada. Como resultado, é apresentado um modelo desse problema como um Problema de Alocação de Fluxo. Dentre as restrições impostas ao problema, são consideradas: a existência de múltiplas áreas de risco e de múltiplos abrigos, que toda a população deve ser retirada das áreas de risco, que existe capacidade nos abrigos e essa capacidade pode ser inferior ao tamanho da população e, por fim, que não devem existir cruzamentos entre rotas distintas de evacuação, a fim de evitar situações de conflito. Observa-se então que o Problema de Evacuação de População impõe um grande número de restrições ao Problema de Alocação de Fluxo. Para resolvê-lo, o mesmo será relaxado de forma que o Método de Ford-Fulkerson possa ser aplicado.pt_BR
dc.degree.localPonta Grossapt_BR
dc.publisher.localPonta Grossapt_BR
dc.contributor.advisor1Almeida, Sheila Morais de-
dc.contributor.referee1Almeida, Sheila Morais de-
dc.contributor.referee2Matos, Simone Nasser-
dc.contributor.referee3Alves, Gleifer Vaz-
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentDepartamento Acadêmico de Informáticapt_BR
dc.publisher.programCiência da Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:PG - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
PG_COCIC_2015_2_03.pdf1,82 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.