Uma heurística interativa para geração de caminhos em grafos com restrição de grau: aplicação ao projeto de sistemas metroviários

O trabalho discute o projeto de uma rede metroviária através de um modelo de grafos, no qual os vértices são estações unidas por trechos de linhas representados por arestas. Define-se um grafo-suporte planar triangulado como o universo das alternativas de ligações entre estações e se procuram coberturas do conjunto de vértices por conjuntos de percursos elementares unindo pares de vértices periféricos. Uma restrição de grau máximo 4 para o grafo parcial assim obtido é adotada num primeiro momento. O grafo é valorado por dados de custo de construção e de demanda de passageir...

• Assuntos:

  • transporte urbano
  • metrô
  • grafos