Modelo de alocação de fluxo em redes para evacuação de população

Abstract

Given 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.