MC 202 - EF - Atividade de Laboratório no. 9

Última alteração: 17/10/08

Descrição do Problema: Localização de Centro de Distribuição

Atualmente no Brasil, "logística de distribuição" é uma atividade de grande importância econômica. Existem no país muitas empresas dedicadas a essa atividade que consiste em manter depósitos, ou centros de distribuição que armazenam mercadorias oriundas dos centros de produção para posterior distribuição aos centros de consumo. Como os custos de transporte representam a maior fatia das despesas nessa atividade, é importante que o centro de distribuição se localize num local que minimize esses custos.
O algoritmo dos caminhos mínimos, dado em sala (veja a apresentação correspondente) pode ser usado para definir a localização ótima do centro de distribuição para uma certa região.
A forma de se definir essa localização, utilizando o conceito de 'caminho mínimo', é a seguinte: 
   Determinar os caminhos mínimos entre todos os pares de cidades usando
   o algoritmo de Floyd-Warshall dado em sala;
   para cada cidade C da região {
      calcular a 'distância média' de C para as demais cidades,
      usando os resultados do algoritmo de Floyd-Warshall;
   }
   selecionar a cidade com a menor 'distância média' para implantar o 
   Centro de Distribuição;
Essa solução pode ainda ser refinada usando, por exemplo, a capacidade de consumo de cada cidade como um fator multiplicativo (custo= distância*fator) . Esse fator é proporcional à freqüência das viagens a essa cidade e deve ser considerado ao se calcular o 'custo médio' do centro de de distribuição a cada cidade destino. Uma cidade pode ser representada por uma estrutura como: 
typedef struct cidade
   {
     int idx;                /* índice da cidade                  */
     char *name;             /* nome da cidade                    */
     int factor;             /* fator (ou capacidade) de consumo  */
     int w;                  /* peso 'final'                      */
   } cidade; 

int nCidades;          /* número de cidades */
Nessa estrutura, o índice da cidade, representado pelo campo idx, pode ser utilizado para se referir ao índice do vértice correspondente no grafo. A tabela de cidades pode ser um vetor onde cada elemento é uma estrutura do tipo descrito acima.

O que deve ser feito

Dado um conjunto de cidades e as distâncias entre elas, determinar a melhor localização para o centro de distribuição. Cada cidade terá associado um fator de consumo para uma categoria de produtos que deve ser considerado.
Isso deverá ser feito com base no algoritmo de Floyd-Warshall dado em sala (ver apresentação). A implementação do algoritmo deve ser usando a matriz dimensionada para o número de cidades lido
do arquivo de entrada (o gcc permite que se defina o tamanho de um vetor a partir do valor de uma
variável, que neste caso será lido do arquivo). 

A região escolhida

A região escolhida para o nosso problema consiste no estado de São Paulo, considerando-se apenas as cidades significativas para a categoria de produtos considerada nesta aplicação.

Dados de entrada

O arquivo de entrada terá duas partes:
  1. número de cidades (primeira linha)
  2. tabela das cidades
  3. tabela das distâncias
A tabela de cidades tem, para cada cidade:
  1. número da cidade (1,2,3,etc)
  2. fator de consumo (inteiro)
  3. nome da cidade (string)
Essa tabela é delimitada pelos valores "-1 -1 xx".
A tabela de distâncias, contém para cada par de cidades conectada diretamente por uma rodovia
  1. o número de cada uma das cidades
  2. a distância entre elas, em quilometros
Essa tabela é delimitada pelos valores "-1 -1 -1".

Importante: As rodovias podem ser utilizadas nos dois sentidos portanto para cada par (A,B) de cidades conectadas por rodovia, devem ser criadas duas arestas no grafo, uma de A para B e outra de B para A.

A partir do arquivo de entrada deve se construir
  1. Uma tabela de cidades contendo p/ cada uma nome e fator de consumo
  2. O grafo correspondente à malha rodoviária que liga as cidades, onde cada nó é uma cidade (referenciada pelo seu índice na tabela de cidades) e cada rodovia é mapeada num par de arestas.

Exemplo de entrada

A seguir o conteúdo do arquivo de entrada a ser utilizado como exemplo: 
31
1 25 Americana
2 35 Campinas
3 10 Rio Claro
4 10 Ribeirao Preto
5 5 Catanduva
6 15 Sao Carlos
7 15 Piracicaba
8 10 Botucatu
9 20 Jundiai
10 30 Sorocaba
11 15 Bauru
12 10 Itu
13 5  Itapetininga
14 50 Sao Paulo
15 10 Avare
16 8 Ourinhos
17 5 Capao Bonito
18 8 Marilia
19 5 Assis
20 8 Presidente Prudente
21 11 Araraquara
22 8 Aracatuba
23 5 Sao Jose do Rio Preto
24 8 Barretos
25 10 Franca
26 8 Votuporanga
27 10 Mogi das Cruzes
28 15 Sao Jose dos Campos
29 20 Santos
30 8 Taubate
31 5 Guaratingueta
-1 -1 xx
1 2 36 
1 7 34 
1 3 55 
6 3 72 
6 4 113
6 5 166
6 7 111
6 8 175 
8 7 104 
8 9 206 
8 10 152 
8 11 108 
10 12 39
10 13 74
10 14 107
8 13 131 
8 15 64 
16 15 108
2 9 36 
14 9 70 
12 9 49 
12 7 84 
13 17 57 
16 11 131 
16 18 97 
16 19 65 
20 19 133 
18 21 226 
18 22 165 
18 23 198 
18 5 200 
18 11 103 
5 11 167 
5 24 100 
5 25 202 
24 25 133 
24 23 95 
5 23 56 
22 23 137 
26 23 90 
26 22 129 
14 27 63 
14 28 87 
14 29 72 
28 30 49 
31 30 43 
-1 -1 -1
Esse arquivo está disponível em distancias.txt.

Nesse arquivo, nomes de cidades como 'Sao Jose dos Campos' aparecem como 'Sao_Jose_dos_Campos', de forma que é possível usar um único especificador de formato '%s' para sua leitura.

O resultado esperado pode ser encontrado em solucao9.txt. 

Data de Entrega: 27/10/08