luc

MO 417 - QUESTÃO PARA A PROVA ORAL - 1ª QUESTÃO

Número:

Enunciado: Uma empresa de produtos alimentícios possui uma frota de veículos que realizam entregas por diversas cidades. Os veículos de transporte de mercadoria possuem uma capacidade limitada de carga e devem realizar entregas em diferentes cidades distribuídas em um mapa. O gerente desta empresa deseja minimizar os custos no processo de entrega de mercadorias determinando rotas que minimizem a distância total percorrida e atenda a todas as demandas das cidades do mapa. Os veículos devem partir do depósito e retornar para o mesmo e cada cidade só deve ser visitada uma vez.
A figura abaixo ilustra uma possível solução do problema:

O problema descrito acima pode ser reduzido ao:

a) Ciclo Hamiltoniano
b) Clique
c) Fluxo máximo
d) Caxeiro Viajante
e) NDA

Ideia original de: Lucas Oliveira Batista