Application of the Maximum Flow
Problem to Sensor Placement on Urban
Road Networks for Homeland Security
Lowell Bruce Anderson, Robert J. Atwell, D. Sean Barnett, and Robert L. Bovey
Bruno Rogério
UECE - Universidade Estadual do Ceará
Sumário
1 Introdução ao problema
2 Aplicando teoria de grafos na modelagem do problema
3 Rede de Fluxo
4 Análise do Problema do Artigo
5 Metodologia
6 Resultados e Aplicações
7 Referências
Maximum Flow Problem
UECE
Introdução ao Problema
Iniciemos a apresentação com a seguinte problemática:
• Como posicionar sensores em uma rede de estradas de forma a impedir
uma invasão por terroristas?
• Para isso, o artigo faz uso de fluxo em redes, da teoria dos grafos
Vejamos um mapa da rede de estradas da cidade de Nova York:
Figure 1: Mapa de estradas da região de Nova York
Maximum Flow Problem
UECE
Aplicando teoria de grafos na modelagem do problema
• Primeiro passo a se fazer, é modelar este mapa como um grafo, com:
vértices e arcos direcionados
• O que seriam os nós e os arcos neste grafo gerado?
Maximum Flow Problem
UECE
Aplicando teoria de grafos na modelagem do problema
• Primeiro passo a se fazer, é modelar este mapa como um grafo, com:
vértices e arcos direcionados
• O que seriam os nós e os arcos neste grafo gerado?
• O mapa da rede rodoviária de Nova York apresenta em torno de um milhão
de segmentos de estradas. Seria impraticável colocar tantos sensores para
monitorar essa área, não é mesmo?
Maximum Flow Problem
UECE
Aplicando teoria de grafos na modelagem do problema
• Primeiro passo a se fazer, é modelar este mapa como um grafo, com:
vértices e arcos direcionados
• O que seriam os nós e os arcos neste grafo gerado?
• O mapa da rede rodoviária de Nova York apresenta em torno de um milhão
de segmentos de estradas. Seria impraticável colocar tantos sensores para
monitorar essa área, não é mesmo?
• Mostraremos como resolver este problema usando o conceito de fluxo em
redes!
Maximum Flow Problem
UECE
Rede de Fluxo
• Afinal, o que é uma rede de fluxo?
Maximum Flow Problem
UECE
Rede de Fluxo
• Afinal, o que é uma rede de fluxo?
Uma rede de fluxo G = (V, E) é um grafo dirigido em que cada aresta (u, v) ∈ E
tem um valor (não-negativo) capacidade c(u, v). Se (u, v) ∈
/ E, assume-se que
c(u, v) = 0.
• Uma rede possui dois vértices principais: Uma fonte (s) e um destino (t)
Figure 2: Exemplo de uma rede de fluxo com suas capacidades
Maximum Flow Problem
UECE
Rede de Fluxo
Um fluxo em uma rede de fluxo G é uma função de valor real f : V x V → R que
satisfaz às três propriedades seguintes:
Maximum Flow Problem
UECE
Rede de Fluxo
Um fluxo em uma rede de fluxo G é uma função de valor real f : V x V → R que
satisfaz às três propriedades seguintes:
• Restrição de Capacidade : Afirma que o fluxo de um vértice ao outro não
deve exceder a capacidade dada. Para todo u, v ∈ V, exigimos f (u, v) ≤
c(u, v).
Maximum Flow Problem
UECE
Rede de Fluxo
Um fluxo em uma rede de fluxo G é uma função de valor real f : V x V → R que
satisfaz às três propriedades seguintes:
• Restrição de Capacidade : Afirma que o fluxo de um vértice ao outro não
deve exceder a capacidade dada. Para todo u, v ∈ V, exigimos f (u, v) ≤
c(u, v).
• Anti-simetria : A anti-simetria é uma conveniência de notação que afirma
que o fluxo de um vértice u até um vértice v é o valor negativo do fluxo no
sentido inverso. Para todo u, v ∈ V, exigimos:
f (u, v)=−f (v, u)
Maximum Flow Problem
UECE
Rede de Fluxo
Um fluxo em uma rede de fluxo G é uma função de valor real f : V x V → R que
satisfaz às três propriedades seguintes:
• Restrição de Capacidade : Afirma que o fluxo de um vértice ao outro não
deve exceder a capacidade dada. Para todo u, v ∈ V, exigimos f (u, v) ≤
c(u, v).
• Anti-simetria : A anti-simetria é uma conveniência de notação que afirma
que o fluxo de um vértice u até um vértice v é o valor negativo do fluxo no
sentido inverso. Para todo u, v ∈ V, exigimos:
f (u, v)=−f (v, u)
• Conservação de Fluxo : A propriedade de conservação de fluxo afirma que
o fluxo total para fora de um vértice que não seja a origem ou o destino é 0
(zero). Para todo u ∈ V - {s, t}, exigimos:
P
v ∈V f (u, v) = 0
Maximum Flow Problem
UECE
Rede de Fluxo
• Como já sabemos o que é um fluxo, e a partir da definição, podemos afirmar
que o fluxo nulo consiste no fluxo mı́nimo que podemos ter em uma rede G
• Vejamos o exemplo :
v'
0
0
s
t
0
0
0
v''
Figure 3: Exemplo trivial de fluxo
Maximum Flow Problem
UECE
Rede de Fluxo
• Método de Ford-Fulkerson
FORD-FULKERSON-METHOD(G, s, t)
1 inicializar fluxo f como 0
2 while existir um caminho aumentante p
3
do ampliar fluxo f ao longo de p
4 return f
O método de Ford-Fulkerson depende de três ideias importantes que são
relevantes para muitos algoritmos de fluxo e problemas: redes residuais,
caminhos aumentantes e cortes
Maximum Flow Problem
UECE
Rede de Fluxo
Redes Residuais
• A capacidade residual de (u, v) é dada por:
cf (u, v) = c(u, v) - f (u, v)
Maximum Flow Problem
UECE
Rede de Fluxo
Redes Residuais
• A capacidade residual de (u, v) é dada por:
cf (u, v) = c(u, v) - f (u, v)
• Definição: Dado um fluxo em rede G = (V, E) e um fluxo f , rede residual
de G induzida por f é Gf = (V, Ef ), onde:
Ef = { (u, v) ∈ V x V : cf (u, v) > 0 }
Maximum Flow Problem
UECE
Rede de Fluxo
Redes Residuais
• A capacidade residual de (u, v) é dada por:
cf (u, v) = c(u, v) - f (u, v)
• Definição: Dado um fluxo em rede G = (V, E) e um fluxo f , rede residual
de G induzida por f é Gf = (V, Ef ), onde:
Ef = { (u, v) ∈ V x V : cf (u, v) > 0 }
• A rede residual consiste em arestas que podem admitir mais fluxo. A
quantidade de fluxo adicional que podemos empurrar desde u até v
antes de exceder a capacidade c(u, v) é a capacidade residual de (u, v)
Maximum Flow Problem
UECE
Rede de Fluxo
Redes Residuais
• A capacidade residual de (u, v) é dada por:
cf (u, v) = c(u, v) - f (u, v)
• Definição: Dado um fluxo em rede G = (V, E) e um fluxo f , rede residual
de G induzida por f é Gf = (V, Ef ), onde:
Ef = { (u, v) ∈ V x V : cf (u, v) > 0 }
• A rede residual consiste em arestas que podem admitir mais fluxo. A
quantidade de fluxo adicional que podemos empurrar desde u até v
antes de exceder a capacidade c(u, v) é a capacidade residual de (u, v)
• Qual seria a rede residual e as capacidades residuais de uma rede de fluxo
G?
Maximum Flow Problem
UECE
Rede de Fluxo
Caminhos aumentantes
• Definição: um caminho aumentante p é um caminho simples desde s até t
na rede residual Gf .
Maximum Flow Problem
UECE
Rede de Fluxo
Caminhos aumentantes
• Definição: um caminho aumentante p é um caminho simples desde s até t
na rede residual Gf .
• Chamamos a quantidade máxima pela qual podemos aumentar o fluxo
em cada aresta de um caminho aumentante p de capacidade residual de
p, dada por:
cf (p) = min { cf (u, v) : (u, v) está em p }
• Como podemos achar o caminho aumentante p a partir da rede residual Gf ?
Maximum Flow Problem
UECE
Rede de Fluxo
Teorema. Se f é um fluxo máximo em uma rede de fluxo G, então a rede
residual Gf não possui caminho aumentante.
• Com isso resolvemos o problema do fluxo máximo, por conta do
algoritmo.
• Qual a relação existente entre o problema de fluxo máximo e o problema de
posicionar sensores em estradas para impedir o avanço de terroristas?
Maximum Flow Problem
UECE
Rede de Fluxo
Teorema. Se f é um fluxo máximo em uma rede de fluxo G, então a rede
residual Gf não possui caminho aumentante.
• Com isso resolvemos o problema do fluxo máximo, por conta do
algoritmo.
• Qual a relação existente entre o problema de fluxo máximo e o problema de
posicionar sensores em estradas para impedir o avanço de terroristas?
• Existe uma relação entre o problema de fluxo máximo e o problema de corte
mı́nimo.
Maximum Flow Problem
UECE
Rede de Fluxo
Cortes em uma rede de fluxo
• Um corte (S,T) de uma rede de fluxo G = (V, E) é uma partição de V em
S e T = V-S tal que s ∈ S e t ∈ T.
Parêmetros de um corte (S, T) :
• Fluxo lı́quido: é f(S, T) = f (v1 , v3 ) + f (v2 , v3 ) + f (v2 , v4 ), onde S = {s, v1 , v2 }
e T = {t, v3 , v4 }
• Capacidade do corte: é c(S, T) = c(v1 , v3) + c(v2 , v4 )
• Corte mı́nimo: é um corte cuja capacidade é mı́nima dentre todos os cortes
da rede.
Teorema. O fluxo máximo de uma fonte s até um destino t em um grafo com
capacidade nos arcos é igual a capacidade do corte s − t com menor capacidade
Maximum Flow Problem
UECE
Rede de Fluxo
• Vejamos um exemplo de um corte em uma rede de fluxo e o cálculo do fluxo
lı́quido e a capacidade do corte
Figure 4: O fluxo lı́quido por (S, T) é f(S, T) = 19 e a capacidade é c(S, T) = 26
• O valor de um fluxo máximo é de fato igual à capacidade de um corte
mı́nimo
Maximum Flow Problem
UECE
Análise do Problema do Artigo
• Alvo dos terroristas : Cidade de Nova York, mais precisamente, a Times
Square (centro do alvo).
• Problema proposto : Implantar sensores a fim de detectar invasores e
impedı́-los que cheguem ao seu destino.
Maximum Flow Problem
UECE
Análise do Problema do Artigo
• Alvo dos terroristas : Cidade de Nova York, mais precisamente, a Times
Square (centro do alvo).
• Problema proposto : Implantar sensores a fim de detectar invasores e
impedı́-los que cheguem ao seu destino.
• Qual seria a quantidade de sensores que devem ser alocados?
Maximum Flow Problem
UECE
Metodologia
A metodologia empregada neste artigo foi aplicada a partir da base de dados
JServer
Parâmetros para alocação dos sensores:
• Criação de uma ”super origem” e um ”super destino” (Nós falsos)
• Curvas significativas desenhadas no mapa, se transformam em nós
falsos
• Utilização do banco de dados JServer
• Rotas terrestres fora do mapa
Primeiro Passo : Concepção do sensor de barreira
• Localização do corte mı́nimo: a partir do centro da cidade (Times Square)
• Fixação de dois cı́rculos concêntricos em torno do ponto central
Maximum Flow Problem
UECE
Metodologia
Figure 5: Segmentos das estradas da região de Nova York
Maximum Flow Problem
UECE
Metodologia
Figure 6: Segmentos das estradas de Nova York - Para encontrar o corte mı́nimo
Maximum Flow Problem
UECE
Metodologia
Dados referentes a Figura 6:
• Possui 488.951 segmentos de estradas;
Dos quais:
• 414.640 são bidirecionais;
• 74.311 são de sentido único;
• Na figura, há 722 segmentos que atravessam o anel exterior e 708 que
atravessam o anel interior;
Maximum Flow Problem
UECE
Metodologia
• Os limites dos cı́rculos podem ser selecionados conforme tamanho desejado
• A densidade da rede de estradas diminui à medida que nos afastamos da
cidade
• Obstáculos naturais também são uma forma de diminuir o tamanho do corte
• Uma propriedade importante desses limites visualizados nas figuras, é
que como um anel é expandido, o corte mı́nimo pode ficar menor, mas
não maior
• Segundo Passo : Trabalhar com os segmentos que tem um ou dois nós
entre as linhas de fronteira dos anéis.
Maximum Flow Problem
UECE
Metodologia
Estrutura utilizada para permitir que o algoritmo de fluxo máximo encontre
o corte mı́nimo :
• Um nó ”super-origem” adicionado fora do anel externo e um nó
”super-destino” dentro do anel interno;
• Segmentos que cruzarem o anel externo, seus nós externos serão alterados
para um nó ”super-origem” e serão lhe dados capacidade infinita;
• Segmentos que cruzarem o anel interno, seus nós internos serão alterados
para um nó ”super-destino” e serão lhe dados capacidade infinita;
• Um traço virtual foi adicionado entre o nó ”super-origem” e o nó
”super-destino”, também com capacidade infinita;
• Os segmentos de estradas reais possuem capacidade 1;
Maximum Flow Problem
UECE
Metodologia
• Os 414.640 segmentos bidirecionais foram convertidos cada um em dois
segmentos e dois nós;
• GNET - é um software para solução de problemas de redes capacitadas
• Gera um corte mı́nimo a partir dos dados fornecidos
• Esse programa tem capacidade de lidar com redes com mais de um milhão
de arcos
• A verdadeira rede rodoviária de Nova York e esta representação feita não são
simétricas;
Maximum Flow Problem
UECE
Resultados e Aplicações
• Feito todo esse processo, foi considerado que 89 sensores bastariam
para cobrir todas rotas possı́veis em torno da Times Square
Figure 7: Locais para a alocação dos 89 sensores
Maximum Flow Problem
UECE
Resultados e Aplicações
• O problema foi aplicado partindo da ideia de que a invasão ocorreria de fora
para dentro. Mas se fosse ao contrário, a solução surtiria o mesmo efeito?
Figure 8: Solução para os problemas de fora para dentro e o reverso
Maximum Flow Problem
UECE
Resultados e Aplicações
• O corte mı́nimo possui muito menos segmentos do que a rede como
todo;
• Auxı́lio na criação de um sistema de contra medidas de terrorismo;
• Verificar outras maneiras que o inimigo pode ignorar os segmentos de
corte;
• Análise de custo-benefı́cio, gerenciamento de risco, vulnerabilidade
dos sistemas de sensores;
• Abordar em pesquisas futuras, análise de risco de ataque a outro tipos
de regiões geográficas;
Maximum Flow Problem
UECE
Resultados e Aplicações
Exitem várias aplicações para o problema do fluxo máximo. Abaixo estão
listadas as mais importantes
• Mapas rodoviários, ferroviários ou de metrô
• Transporte de informações - Roteamento
• Transporte de carga - caixeiro viajante
Maximum Flow Problem
UECE
Referências
1 Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. “Maximum Flows: Basic Ideas.”
Chapter 6 of Network Flows Theory, Algorithms, and Applications. Prentice
Hall, 1993.
2 Balakrishnan, V.K. “Graph Theory.” Appendix of Combinatorics Including
Concepts of Graph Theory, Schaum’s Outline Series. McGraw-Hill, 1995.
3 “Flows, Connectivity, and Combinatorics.” Chapter 6 of Graph Theory,
Schaum’s Outline Series. McGraw-Hill, 1997.
4 Ball, M.O. “Design of Survivable Networks.” Chapter 10 of Handbooks in OR
MS, Vol. 7, Network Models, M.O. Ball et al., Eds. Elsevier Science B.V.,
1995.
5 Ball, M.O., C.J. Colbourn, and J.S. Provan. “Network Reliability,” Chapter 11
of Handbooks in OR MS, Vol. 7, Network Models, edited by M.O. Ball et al.
Elsevier Science B.V., 1995.
6 Berge, C. “Transport Networks.” Chapter 8 of The Theory of Graphs. Dover,
1958 (reprint 2001).
Maximum Flow Problem
UECE
Referências
7 Bradley, G.H., G.G. Brown, and G.W. Graves. “Design and Implementation of
Large-Scale Primal Transshipment Algorithms.” Management Science 24, no.
1 (1977): 1-34. (Copy available at www.jstor.org ).
8 Bradley, S.P., A.C. Hax, and T.L. Magnanti. “Network Models.” Chapter 8 of
Applied Mathematical Programming. Addison-Wesley, 1976.
9 Brown, G., M. Carlyle, J. Salmeron, and K. Wood. “Defending Critical
Infrastructure.” Interfaces 36, no. 6 (2006): 530-544.
10
Even, S. “Maximum Flow in a Network,” Chapter 5 of Graph Algorithms.
Computer Science Press, 1979.
11
Gerards, A.M.H. “Matching.” Chapter 3 of Handbooks in OR MS, Vol. 7,
Network Models, edited by M.O. Ball et al. Elsevier Science B.V., 1995.
12
Gondran, M., and M. Minoux. “Flows and Transportation Networks.” Chapter
5 of Graphs and Algorithms. John Wiley Sons, 1984.
13
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to
Algorithms, 2nd edition, MIT Press McGraw-Hill, 2001.
Maximum Flow Problem
UECE
Referências
14
http://www.ic.unicamp.br/ meidanis/courses/mo417/2003s1/aulas/2003-0606.html acessado em 25/11/2014.
15
http://www.dsc.ufcg.edu.br/ abrantes/CursosAnteriores/TG051/fluxorede.pdf
acessado em 25/11/2014.
Maximum Flow Problem
UECE
Obrigado!
Maximum Flow Problem
UECE