AULA 6 CONTEÚDO ON-LINE - OTIM DE SISTEMAS DE TRANS GST0311

Prévia do material em texto

Um exemplo clássico aparece nos problemas de distribuição/coleta de mercadorias, onde cada cliente possui uma demanda específica e os veículos apresentam capacidade limitada.
Busca-se a configuração das rotas dos veículos de modo que cada cliente seja servido por um e somente um veículo, minimizando-se o custo/comprimento do percurso total.
Dado um conjunto de cidades e conhecidas as distâncias entre cada uma delas, pretende-se determinar o circuito de menor comprimento que passa por todas as cidades, exatamente uma vez, e que termina na cidade de onde partiu.