Flashcard FC241301
Qual heurística de PRV aplica o cálculo de economia \(s_{ij}=c_{0i}+c_{0j}-c_{ij}\) e usa inserção por união de rotas?
Programação Linear
CESGRANRIO · 2012
Qual heurística de PRV aplica o cálculo de economia \(s_{ij}=c_{0i}+c_{0j}-c_{ij}\) e usa inserção por união de rotas?
Mostrar resposta e comentário
Resposta
Clark e WrightExplicação:
A heurística de economia (algoritmo de Clark e Wright) começa com cada cliente em rota separada para o depósito, calcula as economias \(s_{ij}=c_{0i}+c_{0j}-c_{ij}\), ordena-as decrescentemente e tenta unir pares de rotas se respeitarem restrições (por exemplo, capacidade e sequência de extremidades).
Exemplo:
Suponha depósito 0 e clientes A, B, C com distâncias: \(c_{0A}=12\), \(c_{0B}=9\), \(c_{0C}=7\), \(c_{AB}=8\), \(c_{AC}=11\), \(c_{BC}=6\).
Calcule economias:
\(s_{AB}=12+9-8=13\)
\(s_{AC}=12+7-11=8\)
\(s_{BC}=9+7-6=10\)
Ordenando: \(s_{AB}=13\), \(s_{BC}=10\), \(s_{AC}=8\).
Escolhe-se primeiro unir A e B (maior economia) formando uma rota 0–A–B–0 se a capacidade permitir; depois avalia-se unir C com a melhor extremidade disponível segundo as economias seguintes.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236117
Conteúdo do catálogo FC Concursos · Atualizado em