\nonstopmode
\documentclass[12pt]{article}
\newcommand{\lastedit}{2001-10-25 14:19:48 by stolfi}

\usepackage{largepages}
\usepackage[brazil]{babel}
\usepackage{isolatin1}
\usepackage{amsmath}
\usepackage{amssymb}

\input{macros-epsbox}
\input{macros-captionbox}
\input{macros-loctel}

\begin{document}

\begin{center}
{\bf {\Large
Consultoria {\ic}--{\cpqd} para o desenvolvimento de \\
algoritmos para instalação de {\tup}s }\\
\ \\
Abordagem Geométrica e Abordagem Combinatória: \\
Comparação de Eficiência}
\end{center}

\section{Introdução}

  Como nos relatórios anteriores, consideramos aqui o problema de
  escolher as localizações de TUPs adicionais dentro de uma área
  urbana, de forma a satisfazer o critério de distância máxima $D$
  estabelecida pela ANATEL.
  
  Idealmente, a solução deste problema deveria levar em conta a
  geometria e topologia da rede viária contida na região de interesse.
  Nessas condições, a tarefa pode ser satisfatoriamente reduzida a um
  problema de otimização discreta em grafos. Nesta abordagem, que
  denominaremos \emph{combinatória}, a rede é representada por um
  grafo no plano, onde cada aresta corresponde a um pequeno trecho de
  rua. Nesta abordagem, consideram-se apenas soluções onde cada TUP
  está localizado num vértice do grafo; e a condição de distância
  máxima é imposta apenas para os vértices do grafo, em vez de para
  todos os pontos da rede. Conforme discutimos mais adiante, se os
  trechos forem suficientemente pequenos (digamos, menores que
  $10\,\m$), esta discretização do problema terá efeito desprezível na
  qualidade da solução ótima.
  
  A abordagem atual, que chamaremos de \emph{geométrica}, leva em
  conta apenas o contorno da mancha urbana, sem considerar a rede
  viária. Nessa abordagem, supõe-se que, se o programa indicar a
  instalação de um TUP num determinado ponto $p$, este TUP, mesmo que
  venha a ser instalado num ponto $p'\neq p$, atenderá pelo menos uma
  área de determinado raio $R$ centrada no ponto $p$. Sob esta
  hipótese, uma solução poderia ser considerada correta se a mancha
  urbana for inteiramente coberta pela união dos círculos de todos os
  TUPs (existentes e propostos).
  
  Por usar mais informações, a abordagem combinatória tem potencial
  de produzir soluções melhores que a geométrica, em vários aspectos.
  Em primeiro lugar, uma vez que o círculo de raio $R$ é quase sempre
  menor que a área efetivamente coberta pelo TUP instalado, a solução
  geométrica ótima geralmente usa mais TUPs do que a solução combinatória
  ótima. Além disso, por menor que seja o raio $R$, uma solução que,
  cobre completamente a mancha urbana no critério geométrico pode
  na realidade deixar áreas descobertas.  Finalmente, a abordagem
  geométrica é mais trabalhosa de implementar, e está sujeita a 
  falhas devidas a erros de arredondamento.
  Estas comparações são detalhadas nas próximas seções.
  
  A abordagem geométrica é provavelmente a mais indicada quando 
  os dados da rede viária não estão disponíveis. (A abordagem
  combinatória poderia ser aplicada mesmo nesse caso, usando-se
  uma rede viária fictícia com $D$ reduzido; entretanto, 
  esta alternativa provavelmente seria mais cara, e não produziria 
  melhores resultados do que a abordagem geométrica.)
  
\section{Número de TUPs}

  Para uma cidade grande, a solução produzida pela abordagem
  geométrica tipicamente consiste de duas partes. No interior de
  regiões, é usada uma \emph{colmeia} --- uma grade hexagonal
  regular de TUPs, que é a cobertura mais econômica possível do plano
  por círculos iguais. 
  
  
  O raio $R$ desses círculos deveria ser tal que todos os pontos do
  interior de um círculo estejam a distância no máximo $D$ do TUP,
  medida ao longo da rede viária.  Obviamente, se a rede viária 
  é desconhecida, esta condição não pode ser garantida, para qualquer
  valor positivo de $R$. Para superar este obstáculo, supõe-se
  geralmente que a rede viária é aproximadamete regular, com
  quarteirões retangulares. Nesse caso, um TUP instalado numa esquina
  serviria toda a parte da rede contida numa área quadrada com lado
  $D\sqrt{2}$, centrada nessa esquina. O maior círculo contido nessa
  área tem raio $D/\sqrt{2}$; portanto, este é um limite superior para
  o raio $R$, e é o valor geralmente adotado na prática.
  
  .
  
  
  
  
  Como 
  a malha viária é desconhecida, o raio $R$ deve ser menor ou igual
  a 

\newpage

\begin{center}
  ${}$%
  \captionbox%
    {%
      \figbox{\epsbox{bahia-hc}{1.0}}
    }
    {figure}
    {f-bah-hc}
    { Rede viária \texttt{bahia}, com quatro TUPs dispostos 
      em colmeia hexagonal.  As linhas em azul são as partes da 
      rede que distam no máximo $D = 400\,\m$ de algum TUP.
      Os círculos geométricos têm raio $R = 400/\sqrt{2} = 290\,\m$.%
    }
\end{center}

\newpage

\begin{center}
  ${}$%
  \captionbox%
    {%
      \figbox{\epsbox{bahia-sq}{1.0}}
    }
    {figure}
    {f-bah-sq}
    { Rede viária \texttt{bahia}, com quatro TUPs dispostos 
      em grade retangular ótima.  As linhas em azul são as partes da 
      rede que distam no máximo $D = 400\,\m$ de algum TUP.
      Os círculos geométricos têm raio $R = 400/\sqrt{2} = 290\,\m$.%
    }
\end{center}

\newpage

\begin{center}
  ${}$%
  \captionbox%
    {%
      \figbox{\epsbox{itajobi}{1.0}}
    }
    {figure}
    {f-bah-hc}
    { Rede viária \texttt{itajobi}, com 17 TUPs dispostos 
      em colmeia hexagonal.  As linhas em azul são as partes da 
      rede que distam no máximo $D = 300\,\m$ de algum TUP.
      Os círculos geométricos têm raio $R = 300/\sqrt{2} = 212\,\m$.%
    }
\end{center}


\end{document}

