1. Problema de Roteamento de Veículos com Restrição de Capacidade (CVRP): Dado um grafo G=(V È { r }, E), custos c(i,j) ³ 0 associados às arestas (i,j) em E, demandas q(v) associadas aos vértices v em V, uma capacidade Q e um número de veículos K. Deseja-se encontrar K ciclos (ou rotas) que iniciam e terminam no vértice r onde a soma das demandas dos vértices na rota não excedam Q, cujo custo total de suas arestas (nas K rotas) seja mínimo.
   
   
   1. Instância 1: cvrp-1-1288.vrp
      
      0.2 para < 1310, 0.5 para < 1300
      
      
   2. Instância 2: cvrp-2-1272.vrp
      
      0.2 para < 1300, 0.5 para < 1290
   
   
2. Problema de Steiner em Grafos (SPG): Dado um grafo G=(V, E), custos c(i,j) ³ 0 associados às arestas (i,j) em E, e um conjunto de terminais T, T Í V. Deseja-se encontrar um conjunto de arestas que conecta todos os vértices em T (entre si) cujo custo total (soma) seja mínimo.
   
   
   1. Instância 1: steiner-1-2353.stp
      
      0.2 para < 2420, 0.5 para < 2390
      
      
   2. Instância 2: steiner-2-3413.stp
      
      0.2 para < 3495, 0.5 para < 3465
   
   
3. Problema de Alocação Generalizado (GAP): Dadas n tarefas, m máquinas, custos c(i,j) ³ 0 e tempos de utilização a(i,j) ³ 0 de alocar a tarefa j à maquina i, e disponibilidades de utilização de cada máquina b(i), i=1,...,m. Deseja-se determinar uma alocação de tarefas às máquinas de modo que: toda tarefa seja executada por alguma máquina; nenhuma máquina é utilizada além da sua disponibilidade; o custo total da alocação seja mínimo.
   
   
   1. Instância 1: d20100-6185.gap
      
      0.2 para < 6290, 0.5 para < 6230
      
      
   2. Instância 2: d10200-12443.gap
      
      0.2 para < 12600, 0.5 para < 12500
   
   
4. Conjunto Dominante Mínimo (DS): Dado um grafo G=(V, E), determinar um conjunto de vértices D, D Í V, tal que qualquer vértice em V esteja em D ou seja adjacente a um vértice em D. Deseja-se que D tenha cardinalidade mínima.
   
   
   1. Instância 1: dom-set-1-73.dat
      
      0.2 para < 80, 0.5 para < 75
      
      
   2. Instância 2: dom-set-2-186.dat
      
      0.2 para < 216, 0.5 para < 199
   
   O arquivo ``mh-insts-desafio-081.zip'' contém as 8 instâncias citadas acima, além de um arquivo, ``Read-Code-P4.txt'', que contém trechos de programas que leem estas instâncias. A descrição dos formatos dos arquivos para o Steiner e CVRP estão descritos dentro dos próprios arquivos, observa-se apenas o cálculo das distâncias entre clientes no CVRP que é feito a partir das coordenadas de cada cliente. Por favor verifique o cálculo no trecho de leitura do arquivo ``.vrp''. O arquivos para o problema GAP contém o número de máquinas e de tarefas no início. Em seguida, todos os custos de alocação e logo depois todos as utilzações das máquinas. As capacidades das máquinas fecham o arquivo. Finalmente, para o DS, observe que cada linha está associada a um vértice e que o vértice correspondente à linha também aparece com seu próprio vizinho. Observe também que o arquivo inicia com o número de vertices de o número de vizinhos, que é constante para todos os vértices e inclui o próprio.

This document was translated from L^AT_EX by H^EV^EA.