Relaxação Lagrangeana com Geração de Desigualdades Válidas Aplicada ao Problema de Roteamento de Veículos

Trabalhamos na construção de um método exato que busca a combinação de relaxação lagrangeana com resultados de combinatória poliédrica, direcionados, especificamente, para o problema clássico de roteamento de veículos. Neste problema, dispomos de uma frota de K veículos idênticos e desejamos atender um conjunto de n clientes, cada um com uma demanda específica. Todos os veículos devem partir e retornar a uma mesma origem (depósito) e cada cliente deve ser visitado uma única vez. O objetivo será minimizar o "custo total" de transporte no atendimento aos clientes sem violar a capacidade de cada veículo.  Dado um grafo G com n+l vértices, uma K-árvore, é definida como sendo um sub-grafo conexo de G com n+l vórtices e n+K arestas. Pode-se mostrar facilmente (Fisher[94.b]), que o problema de roteamento de veículos pode ser modelado como o problema da K-árvore mínima com 2K arestas incidentes ao depósito, juntamente com restrições adicionais de capacidade (imposta aos veículos) e restrições que indiquem que cada cliente deva ser visitado uma única vez. Estas restrições adicionais são dualizadas e um problema lagrangeano é obtido para geração de limites inferiores para o problema de roteamento.  Fazemos uma análise da abordagem utilizada por Fisher[94.bl que emprega K-árvores mínimas com a geração de desigualdades violadas (particularmente sub-rotas violadas). Este trabalho de Fisher[94.b], nos serviu de base para a adoção de novas estratégias na identificação de restrições violadas. Introduzimos as desigualdades comb e multistars (formulações de Cornuejouls e Harche[93] e Araque et al.[90] respectivamente) e desenvolvemos um procedimento para fixação de variáveis.  Uma nova heurística lagrangeana é também apresentada na determinação dos limites superiores para o valor de uma solução ótima do problema de roteamento.  São apresentados resultados computacionais para instâncias de até 199 clientes (na geração dos limites inferiores), e de até 100 clientes, na busca em árvore implementada.  Fazemos contrações de nossa abordagem com as abordagens apresentadas por Fisher[94.b] (K-árvores mínimas) e Miller[95] (b-matching) na geração dos limites inferiores.